### Betlista's blog

By Betlista, 10 years ago,

Probably almost everyone here knows the contest, but I didn't find post about it here (except this one)...

Currently there is qualification round for GCJ 2012 running just now, enjoy ;-)

• 0

 » 10 years ago, # |   -9 can anybody propose a solution for qualification round's 2nd problem for small dataset.
•  » » 10 years ago, # ^ | ← Rev. 2 →   +3 Here is what i did and passed both the tests.. initially for each test case set count=0; Scan the scores of googlers one by one in a variable say 't' if(t/3>=p) //score of atleast p definitely possible count++; else k=t-p; //assuming at least one judge gave score of p if( k>=(2*p-2) && k>=0 && p>0) count++; //worst case score 'p' 'p-1' 'p-1' and as max diff is 1 //so 's' will not be decreased else if(k>=(2*p-4) && s>0 && k>=0 && p>0) { count++; //worst case score 'p' 'p-2' 'p-2' and max diff is 2 s--; //so 's' will be deceased } do this for all the scores and then print the final count for the test case.....i hope you understood the approach.
•  » » 10 years ago, # ^ | ← Rev. 3 →   +4 Let dp[i][j] is the answer for exactly i dancers and j surprising scores. Initialization: dp[0][0] = 0. Try to add a new dancer.If the best result of at least p is reachable, update dp[i+1][j] = max(dp[i+1][j], dp[i][j]+1). If not, update dp[i+1][j] = max(dp[i+1][j], dp[i][j]).And if this result can be also surprising, update dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1). If not, update dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]).At the end answer will be in dp[n][s].
•  » » 10 years ago, # ^ |   0 I don't know why people Downvoted my post even though it works....i got AC on it...if anyone has any problem then ask... I think the thought process is simple and extra space also is not required as in DP solutiom..Here is the Complete Code..
•  » » » 10 years ago, # ^ |   +13 There is a lot of idiots on Codeforces who vote agains posts without clear reason. Don't mind.
•  » » » 10 years ago, # ^ | ← Rev. 2 →   +10 I think you got minuses because what you wrote is not classified as idea or algorithm, but implementation details, thus it was very difficult to understand quickly.Some statements to outline the algo like "the main idea is greedy", "for each contestant check if he is surprising" may help :)
•  » » » 10 years ago, # ^ |   -12 Its probably because you are green just like me..Many people vote just by the color and not by the content :(
 » 10 years ago, # |   +3 Is there any way so that i can see the results filtered by Country.....
•  » » 10 years ago, # ^ |   +3 Usually statistics are published here: http://www.go-hero.net/jam/11/
•  » » » 10 years ago, # ^ |   +6 I think it will be http://www.go-hero.net/jam/12/ this year)
•  » » 10 years ago, # ^ | ← Rev. 2 →   +5 Statistics are updated ;-)