Codechef 2012 March Long contest feedback

general
,
1

Hi,

I would like to give some feedback in my aspect and of course I’m interested others opinions too :slight_smile:

So when I read the problems I feel the problems are hard, I just saw one easy problem ‘Spoon in Matrix’. I haven’t got too much problem with ‘Home Delivery’, ‘Lucky Number’, ‘Cosine Partition Function’, ‘Free Shuttle Service’, ‘Xor it’ this means my first idea worked. Of course it takes sometime when I had any idea :)…
The other problems:

‘Longest Weird Sequence’: I felt I should solve this problem, because I felt this is an dp, and I’m weak in this area… I saw lot of contestant solve this problem quickly that is bother me, I have to wait days for to the idea. So that problem was tricky for me…

‘Evil Book’: I have some idea quickly, so I made some implementation, and I’ve got WA. Hmmm… I found some bugs… but I still didn’t understand why I got WA… Lot of thinking I left the double and calculate just long long integers to avoid precision problem, of course this no sense here but I didn’t have any idea…still WA. I write a brute force tester to find where my code make a mistake, but don’t find any… So lot of debugging I feel I stuck…While I travelled go home on the subway read the statement, I realized when no solution I should write ‘impossible’ and not ‘impossible!’. That hurt… So when I got TL it was a huge relief :slight_smile: So this was Evil. I lost about 2 days with this ‘important!’ bug, but of course it’s totally my fault, I’ve deserved that.

‘Tom and Jerry’: I have the idea to we can catch the Jerry if he is more than 5 distance from the closest door, and some similar idea, but I feel it’s not so easy to implement, and saturday night I was tired, so I gave up…

‘Ciel and Earthquake’: I don’t thinking on this, I saw just few contestant solved it, so I left it to the end, but I don’t have time…

I’m very happy for the result, and for that my ranking on the long contest now is better than the short, but I think this is the true… I feel I’m not good at the short.

I have some questions too:

When will the new ‘ELO based’ rating showed in the profile?
Is this forum will be different main subjects? I feel it would be better and more easy to handle if Long contests discussion, Short contests, and technical questions not showed in the same place… What do you think?

I accepted with the codechef can put some message on my facebook wall. Did you know do you put today 4 times my 2011 December result? :slight_smile:

1 Like
2

My reflections on the contest.

SPOON: I did strstr on each row of the matrix after converting it to complete lower case. Then again on the rotated matrix.

SHUTTLE: I sort of cheated in here. Seeing lot of people doing it in 0.00 time and that N<=10,000 I though there must be a simple formula. So wrote a small brute force kind of program to print values for N<=10 and then used oeis to find out that it was phi(n). Of course later did the analysis to why phi(n) was the answer :slight_smile:

LUCKY2: There was pretty much only one way to solve these kind of questions but I was frustrated with getting wrong answer for long time. In the end just to realize that I was using for(k=0;k<=14;k++) to loop over an array of 14 elements.

LWS: Just like you I was bothered when I saw lot of contestants solved it with very high accuracy. Tried some greedy kind of solutions based on LIS and LDS even though I had a gut feeling those were not correct. It took too long for me to come to the correct approach though I was always concentrating on the limitec haracter set a-z.

PARCOS: Having solved PARSIN earlier I was thinking I need to solve it some similar way but that N in denominator Cos(KiX/N) was bothering me. Luckily I realized that the constraints N and M were swapped from that problem. But still I managed to solve the problem by matrix exponentiation only.

XOR: My first idea really worked for this problem also but it took some time to do a careful implementation to avoid TLE.

TOMJERRY: My essential idea was on these lines.

If Along the current shortest path for Jerry if there exists two consecutive nodes n1 and n2 (apart from Jerry’s current position, the home and the node just before home) such that the distance from Jerry to n1 is greater than equal to the number of neighbors of n1 and n2 - 1 then we can block Jerry in these two nodes other block this shortest path and let Jerry take some other path. If multiple such n1 and n2 exists pick the ones closest to Jerry. I think your idea was also on the same lines and that is why you proposed more than 5 steps away from the home.

An example run to illustrate my idea.

..........   
J........0
..........

Tom Move    Jerry Move
....#.....  ....#.....
J........0  .J.......0
..........  ..........

....#.....  ....#.....
.J.......0  ..J......0
....#.....  ....#.....

...##.....  ...##.....
..J......0  ...J.....0
....#.....  ....#.....

...##.....  ...##.....
...J.....0  ....J....0
...##.....  ...##.....

...##.....  ...##.....
....J#...0  ....J#...0
...##.....  ...##.....

...##.....  Can't Move
..#.J#...0
...##.....

During the contest I made a wrong analysis and the implementation was not perfect. I was getting a penalty of 2e6 on two test cases and was not able to eliminate that and hence had a very low score.

I didn’t even have a first idea of EVILBOOK and didn’t even bother trying CIELQUAK as only 3 people solved it. Overall satisfied with my performance for the first time in a long contest.

4 Likes
3

Luckily in my time, I realized that the constraints N and M were swapped from that problem. But still I managed to solve the problem by matrix exponentiation only. assignment-crux help service uk

4

Yes I have the same idea on the Tom and Jerry… Nice explanation by the way…

5

@iscsi: Thanks for your valuable feedback. We really appreciate it :slight_smile: The user profile page currently shows ELO based rating. Regarding posting message on your facebook wall, we really apologize as we ran some tests on the new ELO ratings and that triggered the automated facebook wall posting :(.

6

For the new forums, we think relevant questions should be easy to find and also we are trying to tag the questions correctly so that the community does not find it hard to find what they are looking for.