Betlista's blog

Google Code Jam 2012 — qualification round
By Betlista, 12 years ago, In English

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 ;-)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it -9 Vote: I do not like it

can anybody propose a solution for qualification round's 2nd problem for small dataset.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      There is a lot of idiots on Codeforces who vote agains posts without clear reason. Don't mind.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      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 :)

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      Its probably because you are green just like me..Many people vote just by the color and not by the content :(

      → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there any way so that i can see the results filtered by Country.....

→ Reply