Search found 27 matches

by kalinov
Wed Mar 22, 2006 2:36 pm
Forum: Volume 110 (11000-11099)
Topic: 11016 - Square Counting
Replies: 19
Views: 7875

How about think of Divide and Conquer? Divide a large rectangle into four smaller rectangles. Coordinates are lower than 10000, therefore at the worst cases time complexity is about O(10000 * 10000 * lg(10000) ). But this rarely happens. In fact, N is quite small (N ≤ 100), so it will fit in the ti...
by kalinov
Wed Mar 22, 2006 2:24 pm
Forum: Volume 110 (11000-11099)
Topic: 11016 - Square Counting
Replies: 19
Views: 7875

Since the square in the first row and first column is dark (from the figure), I couldn't understand why the second sample output is "1 0". Do I mis-understand something? Btw, I think plane-sweep will do. "For each test case, output a line containing two space separated integers, the ...
by kalinov
Tue Mar 21, 2006 6:38 pm
Forum: Volume 110 (11000-11099)
Topic: 11020 - Efficient Solutions
Replies: 14
Views: 6035

My accepted solution is N lg N and I use STL set also, so that should work. Make sure that your implemented solution really is N lg N.
by kalinov
Mon Mar 20, 2006 2:28 am
Forum: Volume 6 (600-699)
Topic: 635 - Clock solitaire
Replies: 8
Views: 4041

Check if you convert characters in the input to numbers correctly. 'A' is considered 11 o'clock, and 'J' is 1 o'clock, although I think it would be more logical otherwise. Also there is no mention of character 'T' in the problem statement while there is 'T' in the sample input, not "10". W...
by kalinov
Mon Mar 20, 2006 2:09 am
Forum: Volume 110 (11000-11099)
Topic: 11012 - Cosmic Cabbages
Replies: 29
Views: 9515

To maximize |xi-xj| + |yi-yj| + |zi-zj| you can choose if 1. (xi-xj) will be positive or negative 2. (yi-yj) will be positive or negative 3. (zi-zj) will be positive or negative You can do it in 8 ways. For example if you choose (xi-xj) to be positive, (yi-yj) to be negative, and (zi-zj) to be posit...
by kalinov
Thu Mar 09, 2006 1:57 pm
Forum: Volume 110 (11000-11099)
Topic: 11007 - Mini Cube
Replies: 11
Views: 7667

Try searching from both initial and final state. The technique is called meet-in-the-middle. Let A[X] be distance from initial state to state X and B[X] be distance from final state to state X. If you can find some state X that is reachable from both initial and final state then you can get from ini...
by kalinov
Thu Mar 09, 2006 12:36 am
Forum: Volume 110 (11000-11099)
Topic: 11007 - Mini Cube
Replies: 11
Views: 7667

3674160 is indeed the number of states, but don't try to generate all of them. The key observation is that the distance between two most distant states is 14. To get it within 2 secs you also have to think of the best way to represent the cube in your program so that rotations are performed easily. ...
by kalinov
Mon Mar 06, 2006 3:10 pm
Forum: Volume 110 (11000-11099)
Topic: 11008 - Antimatter Ray Clearcutting
Replies: 81
Views: 46468

output

Case #1: 1 Case #2: 7 Case #3: 2 Case #4: 1 Case #5: 2 Case #6: 2 Case #7: 1 Case #8: 1 Case #9: 3 Case #10: 3 Case #11: 5 Case #12: 2 Case #13: 3 Case #14: 3 Case #15: 1 Case #16: 3 Case #17: 1 Case #18: 2 Case #19: 1 Case #20: 2 Case #21: 2 Case #22: 5 Case #23: 7 Case #24: 2 Case #25: 1 Case #26...
by kalinov
Thu Dec 29, 2005 5:29 pm
Forum: Volume 109 (10900-10999)
Topic: 10979 - How Many Triangles?
Replies: 15
Views: 6634

Not very tricky, but try these:

Code: Select all

input:
4
1 1 3 3
2 1 2 3
3 1 1 3
1 2 3 2

6
1 1 3 3
2 1 2 3
3 1 1 3
1 2 3 2
1 3 2 3
2 3 3 3

4
1 1 4 4
3 3 6 6
5 6 5 1
1 2 6 2

4
1 6 4 3
3 4 6 1
5 1 5 6
1 5 6 5


output:
0
3
1
1
by kalinov
Thu Dec 22, 2005 11:42 pm
Forum: Volume 103 (10300-10399)
Topic: 10332 - The Absent Minded Professor
Replies: 22
Views: 7193

multiple outputs

What about this:

Code: Select all

input:
6
1 2 2 3 4 5 6 7 7 8 9 10 11 13 14
 
output 1:
0 4 6 11 13 14

output 2:
0 3 5 7 13 14
Note that output 2 is NOT an image of output 1, and they are both correct outputs.

I hope there is no such examples in the test data.
by kalinov
Sun Dec 18, 2005 3:04 pm
Forum: Volume 109 (10900-10999)
Topic: 10975 - Dueue's Quiz
Replies: 39
Views: 18255

Wrong input

I believe the input file is wrong. I think there are some lines shorter than N characters. I've tested it with this code: #include <cassert> #include <cstdio> #include <cstring> using namespace std; int main( void ) { int T, D, Q, M, N; char buff[10000]; scanf( "%d", &T ); for( int tt ...
by kalinov
Tue Mar 29, 2005 3:13 pm
Forum: Off topic (General chit-chat)
Topic: I win !!
Replies: 361
Views: 129973

aaa

aaa

Go to advanced search