OJ Board

kalinov

Well, there is a way to check if you have solved particular problem or not. Click on the problem stats (third icon in the upper right corner) and if you solved the problem there should be "Your best solved try" table.

kalinov

At the moment there is no easy way to see what problems I have solved.

I would like to suggest that you add a checkmark on each solved problem (next to submissions/solving% statistics of a problem) while browsing the problemset.

kalinov

Wei-Ming Chen, your output is incorrect.
My program outputs 14 for this input:
16
1 2 4 17 58 69 125 254 478 1023 10000 145236 172589 172590 1000000 10000000

kalinov

Watch out for overflow... Try this:

Code: Select all

input:
5
RList(10,-2147483648,2147483647,4294967295)
0

output:
Case 1: 2139940657

kalinov

david wrote:Anyway here's my code, in case someone wants to test it.

Your program fails on this case:

Code: Select all

input:
1

0 0 5 0 2 4
4 0 6 0 -4 16

output:
pair 1: yes

kalinov

david wrote:My program passes all those cases, but I keep getting WA. Can anyone supply more tricky examples?

Make sure you don't overflow if you use integer arithmetics. And if you use floating point numbers make sure you make your comparisons are good (use epsilon).

Good luck!

kalinov

fpavetic wrote:can anybody provide some tricky cases for this task? thanks

This one was tricky for me:

Code: Select all

input:
1

0 0 5 0 2 4
4 0 5 0 -4 16

output:
pair 1: yes

kalinov

Is the following algorithm correct?

The algorithm is correct.
What algorithm for finding SCCs are you using? Tarjan's DFS-based algorithm is great for this problem because it generates components in topologicaly sorted order, but (I think) many people make bugs when calculating 'lowlink number ...

kalinov

A bit faster algorithm exists.
There is a way to check for some mean M if there is a cycle with mean at least M in O(n*m). So you can do a binary search on the mean to find the result.

kalinov

fh wrote:the first thing i did was next_permutation(), but TLE

I got accepted in 5 sec by writing my own next_permutation procedure that calculates new remainder on the fly.

Also you can precalculate mod[x] = x mod d; up to 1000000 or so, to get rid of expensive mod operation.

kalinov

I have failed to compute # of green + red points using pick theorem. I have multiplied all xs, ys by 2, then divide result by 2, but this gives only approximation. I need a hint please!
What about rotation? :) The reason why you do these transformations is to put a red or green point on *every ...

kalinov

I am aware of everything you said. Actually there is no scaling, rotating or shearing in my program. But there was a lot of that in my mind while I was solving (thinking about) the problem. All calculations are done with integers, except for multiplying area with d*d*sin(theta) in the end. :)
Well ...

kalinov

I used principle of inclusion-exclusion.

To solve 3D problem (x>0, y>0, z>0) I do this:

Let f(k) be the number points (x,y,z) such that 0<x<=N, 0<y<=N, 0<z<=N and such that x, y, and z are multiples of k.

f(k) = (N/k)*(N/k)*(N/k) (it's integer division)

First, let's count total number of points ...

kalinov

Yes, Pick's theorem is the key. I used it twice. To count green points and to count green+red points.

But you'll also have to do some scaling, rotating, and shearing. These transformations are "affine" and they preserve collinearity. It's important because that guarantees us that same points will ...

kalinov

It's necessary to notice that if you, at any time, sort the list of efficient grooms decreasingly by L, the list will also be sorted increasingly by C (because of its nature).

To get better percepcion, think of grooms as points in x-y plane.

Now think what points are to be deleted from the list if ...

OJ Board

Search found 27 matches

List of solved problems

Re: 11122 - Tri Tri

next_permutation