Search found 27 matches

by kalinov
Sun Sep 09, 2007 9:48 pm
Forum: Bugs and suggestions
Topic: List of solved problems
Replies: 4
Views: 2164

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.
by kalinov
Sat Sep 08, 2007 1:06 pm
Forum: Bugs and suggestions
Topic: List of solved problems
Replies: 4
Views: 2164

List of solved problems

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.
by kalinov
Sun Sep 02, 2007 9:39 am
Forum: Volume 112 (11200-11299)
Topic: 11264 - Coin Collector
Replies: 14
Views: 5283

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
by kalinov
Sun Oct 15, 2006 7:29 pm
Forum: Volume 111 (11100-11199)
Topic: 11124 - Troubles for Modern Days Problemsetters
Replies: 7
Views: 4699

Watch out for overflow... Try this:

Code: Select all

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

output:
Case 1: 2139940657
by kalinov
Sun Oct 15, 2006 3:13 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 8673

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
by kalinov
Sun Oct 15, 2006 2:34 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 8673

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! :)
by kalinov
Sat Oct 14, 2006 9:12 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 8673

Re: 11122 - Tri Tri

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
by kalinov
Mon Sep 25, 2006 11:25 am
Forum: Volume 110 (11000-11099)
Topic: 11098 - Battle II
Replies: 11
Views: 5908

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' for...
by kalinov
Mon Sep 11, 2006 11:49 pm
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13491

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.
by kalinov
Mon Sep 11, 2006 11:28 pm
Forum: Volume 110 (11000-11099)
Topic: 11084 - Anagram Division
Replies: 19
Views: 9237

next_permutation

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.
by kalinov
Sat Mar 25, 2006 12:40 pm
Forum: Volume 110 (11000-11099)
Topic: 11017 - A Greener World
Replies: 11
Views: 3676

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* poi...
by kalinov
Thu Mar 23, 2006 2:30 am
Forum: Volume 110 (11000-11099)
Topic: 11017 - A Greener World
Replies: 11
Views: 3676

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, ...
by kalinov
Wed Mar 22, 2006 4:20 pm
Forum: Volume 110 (11000-11099)
Topic: 11014 - Make a Crystal
Replies: 16
Views: 6740

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. It'...
by kalinov
Wed Mar 22, 2006 3:48 pm
Forum: Volume 110 (11000-11099)
Topic: 11017 - A Greener World
Replies: 11
Views: 3676

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 be...
by kalinov
Wed Mar 22, 2006 3:27 pm
Forum: Volume 110 (11000-11099)
Topic: 11020 - Efficient Solutions
Replies: 14
Views: 5573

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 w...

Go to advanced search