USACO Special Chinese Contest
“This was a (so far) unique endeavor for USACO. Richard Peng and I invited several of China’s best competitors and veterans to devise some very ‘evil’ tasks for a very challenging contest.” (http://ace.delos.com/CHN07results).
Wow, extremely challenging and hard problem set of USACO. Say if we can separate 6 problems in IOI as 2 easy – 2 medium – 2 hard. We can categorized these 3 problems as the medium and hard, no easy one!
Sadly I can’t really join the competition, I just arrived from Purwakarta on Sunday evening and felt so tired (woke up at 1PM on the following day). Well, simply, I’ve tried the analysis mode.
Problem 1 seems to be the easiest one, at a glance we can directly see the O(N*T) solution, but it’s not sufficient, we have to dig more. Mathematically it’s not really hard to see that the sum of all numbers in t-time will equal to [(N-1)^T * init_sum]. So, mathematically the only problem is to count that value which we can solve within O(logT), but sadly if you use this approach, there will be a dividing-operation where the modulo arithmetic won’t be easy to code, I’ve tried this kind of solution and only got 6 testcases. Knowing that problem, we have to back to the pattern, considering the change of only one number, we can see that ith number in t-time will be [(N-1)T-1 - (N-1)T-2 + (N-1)T-3 - (N-1)T-4 + ... ± (N-1)1 ∓ (N-1)0]*init_sum∓init_1th_number. Now using this approach we can also do O(logT) code and there’s no more dividing-operation, yeah! Got fullscore with this approach. This approach is someway same as the 1st solution in USACO analysis. Surprisingly, this kind of problem can be solved using power of matrices like we do to count fibonnacci number. Kurniady and Suhendry tell me about it before the analysis came out, they were both successfully solved it (I think Kurniady just left one little thing so that his code didn’t got fullscore).
Problem 2 is suh a dynamic-programming problem. I stuck on the O(N^3) solution, don’t know what to do anymore. In fact the proper solution is working only in O(N^2).
Problem 3, umm, actually I don’t know what to say, the problem seems to be extremely hard, with those constraint we can directly know that only O(N) or (N log N) solution will sufficient. In facts it’s kind of hashing in graph. If I’m not mistaken, one of CEOI07′s problems was kind of this, but that was only hashing in tree, I think that was easier. As a matter of fact, I couldn’t solve that CEOI07′s problem, so I think it’s obvious that I’m still unable to do so.
Summarize, if these are real problems in a competition, optimally I may only got about 400 out of 1000. A little bit sad, realizing that among Chinese competitor I’m nothing, hehe… Applause for them!
Oh ya, several Indonesian competitors did the CHN07 in the contest time and here is their results:
Irvan Jahja 424
Timotius Sakti 370
Suhendry Effendy 280
Andrian Kurniady 224
Amal Syahreza, Timotius Chandra, Muhammad Irfan Alfarabbi, Risan, Reinardus Surya Pradhitya 112
Listiarso Wastuargo, Gerry Yulian 80
Izhari Ishak Aksa 56
Congratz to Irvan Jahja who got the highest score, did the contest very well (especially on the 1st problem). For the others, there’s still a lot of time to learn and practicing, hope everyone will be better. See u in USACO January Contest!
January 2, 2008