erdos's blog

By erdos, history, 4 months ago, In English,

Code Jam R2 starts in ~24h (Saturday, May 19th 14:00 UTC)

Let's discuss the problems after the contest!

 
 
 
 
  • Vote: I like it  
  • +236
  • Vote: I do not like it  

»
4 months ago, # |
Rev. 2   Vote: I like it -77 Vote: I do not like it

ok

»
4 months ago, # |
Rev. 2   Vote: I like it +81 Vote: I do not like it

I wonder what the exact scoring rules are.
They were not important in Round 1, but are important for me and people of my level now, in Round 2.

Case 1:
Attempt 1. Solve Small correctly and Large incorrectly.
Attempt 2. Solve Small correctly and Large correctly.
I think I get +1 penalty here, no doubt.

Case 2:
Attempt 1. Solve Small correctly and Large incorrectly.
Attempt 2. Solve Small correctly and Large incorrectly.
But do I get +1 penalty here? (I hope not, it would be nonsense, but let's wait for approved answer)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +97 Vote: I do not like it

    There is a section explaining the scoring system in the FAQ. ( https://code.google.com/codejam/resources/faq )

    They take in consideration your earliest attempt that passed the visible tests, and your latest attempt, and give you points/penalty based on the better of the two.

    So for your examples, you would get +1 penalty in Case 1, and get no penalty in Case 2.

»
4 months ago, # |
  Vote: I like it +58 Vote: I do not like it

BUMP! Round starts in less than 30 minutes. Good luck and have fun! :)

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Why this shows round 3? https://codejam.withgoogle.com/2018/

»
4 months ago, # |
Rev. 2   Vote: I like it +75 Vote: I do not like it

I'm writing my address and all those stuffs just to start the contest. I already wrote this about 5 times when taking 2018QR, and now I have to write this in the middle of the contest? If you don't want to give me t-shirts, then do it in the fair way.

»
4 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Can someone please fix the contest? It keeps showing 20 hours for Round 3. If I go to Past Contests, I can see problems from Round 2, but I can't fu**ing submit !!!!!!

Anyone from Google around? This is unacceptable!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    idk, try a different browser or change time on your computer (it does affect some websites)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Google doesn't care about CF (or particularly about competitive programming in general), you should write to the Codejam Google Group. Although I don't know how much requests there are watched...

    One guy had broken round 1C, the dashboard ignored timezones and had the round "start" 2 hours earlier — the problems weren't visible for those 2 hours, so he had 30 minutes to compete. This bug only happened at one computer, but it was pretty persistent (restarting browser or cache clean didn't work).

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it

    they don't want to fix it, I emailed them about the issue last round as my contest ended after 1:30 instead of 2:30.

»
4 months ago, # |
Rev. 3   Vote: I like it +50 Vote: I do not like it

Had a lot of ideas for D, cant think of how to keep my code clean and effective .... Should've gone for small instead of going for large + AK. :/

Edit:

Me and my teammates after the contest:

Me: Whew, this is the first time I ever used the simplex template, it actually fit into B's TL!

Teammate: Isn't it DP?

Me: What?

Teammate: What?

Edit 2: So it turns out I am the only edgy kid who used simplex for B ... ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    How did you use simplex for B?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Maximize dot(c, x):

      c is a column vector filled with 1, each entry of x represents if we will pick (x reds, y blues), so dot(c, x) will be the amount of jugglers we have at the end.

      Simliar to the editorial make sure you only keep pairs that are possible to be juggled with the amount of chainsaws we have.

      While satisfying Ax <= b:

      First two rows of A will be representing the constraints on how much red / blue chainsaws we have, if the i-th entry of x represents (x reds, y blues), then A[0][i] = x, A[1][i] = y. Set b[0] = Red, b[1] = Blue, such that we will never exceed the budget.

      For the i-th entry in x, to make sure we don't have jugglers which share the same juggling arrangement, add extra rows where A[i+2][i] = b[i+2] = 1.

      Code:

      https://ideone.com/VA2Uvw

      Simplex template credit goes to MIT 2008 ACM template.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please elaborate a little on last part to ensure that we don't have jugglers sharing same arrangement?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It makes sure max(x) <= 1, similar to how you prove IP is NPC from knapsack.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Makes sense now. Thank you :)

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +34 Vote: I do not like it

        How can you be sure that the answers from simplex solver are integers?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

          I am not sure about the proof -- But I suppose that the problem nature encourages the simplex solver to take pairs which spends less chainsaw to attain maximimzed real results, and taking floor shouldn't hurt.

»
4 months ago, # |
  Vote: I like it +32 Vote: I do not like it

239 people with 100 points... that's a lot more than last year's 7.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was C Augmenting Path/Max-Flow?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    just bipartite matching(n^2 — match matching for each value)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      OMG, it seems I copied not-working code from the internet).

»
4 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

For C, why the greedy idea (Let s the sum of size of maximum matching for each number, then answer = n2 - s) fail?

I regret wasting too much time on C, not realizing that D is actually easier than C.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's the correct answer for C.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Except it should not fail... I suppose you built a flow graph w.r.t row/column for each number?

    Meanwhile me failing to code D.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +103 Vote: I do not like it

    IMO C was the easiest problem today :P

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Could you explain your solution?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Iterate x from  - n to n. For each x, we will find the maximum number of cell with number x that we can keep unchanged. To do that, build a bipartite graph, each vertex on the left right represent a row, each vertex on the right side represent a column. Add an edge from u on the left to v on the right if a[u][v] = x. Then, the number of cell we can keep is the cardinality of maximum matching in the above graph.

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I just don't why finding a maximum matching in above graph correspond to maximal independent set in original graph.

        What's the meaning of taking edge ij?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 2   Vote: I like it +6 Vote: I do not like it

          Each edge is corresponding to a cell in the original graph. In the maximum matching, no two edge coincident to the same vertex, similar to how no two chosen cells should be in the same row or column.

          Consider the following example

          0 3 0 
          0 3 0
          0 3 3 
          

          If we consider number 3, then the bipartite graph will look like the following:

          1  1
           \ 
            \
          2--2
            /
           /
          3--3
          

          One possible maximum matching is (1, 2), (2, 2) and (3, 3), which corresponding to the solution of keeping cell (1, 2), (2, 2) and (3, 3) unchanged.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you so much.

»
4 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Is there any scrapper available online to filter contest results by countries at least?

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve C? I thought that we should compute minimum vertex cover in the graph where we have edges between vertex with the same color and (same row or column) but this graph is not bipartite. :(

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B large Fail Test Case?

»
4 months ago, # |
  Vote: I like it +49 Vote: I do not like it

Wow, compilation error still counts as penalty attempt.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, I also got one in previous rounds for using C++17.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe my OK large test submission was obscured by CE submissions after it. Is it really ok?)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give me a hint why this code is failing in A : https://ideone.com/hVQGi2

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    At this point I like to generate random input to see if it crashes.

    1
    6
    3 2 0 0 0 1
    Exception in thread "Main" java.lang.ArrayIndexOutOfBoundsException: -1
    	at Solution.run(Solution.java:207)
    	at java.lang.Thread.run(Thread.java:748)
    
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this should work:

    Notice that if you go deep enough, any fixed-size pattern can only be part of a very simple grid composed of 4 quadrants with the same colours (let's allow a quadrant to have colour None to deal with edge cases). Each such grid is formed by expanding a square 2x2 in the original grid sufficiently many times; there are at most 81 of them, so we can find all such colourings by brute force.

    Now, we can try dividing the original grid into 4 parts by a vertical and horizontal line; there are O(RC) ways to do this, we can try them all. We can also try all possible colourings. For each of these cases, we know which cells can't be in our pattern, and out of the remaining cells, we can build the largest connected component. Then we just need the maximum of all CC. Time O(R2C2).

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Using 24 = 16 coloring isn't too difficult either. You just have to expand 1x1 and 1x2 colorings to matching 2x2 coloring when checking which ones are present.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In the end, my implementation could just ignore colourings with None, so not even expanding anything was necessary, but using dummy objects that simplify implementation and only increase the constant factor is a good approach in many problems.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      My python implementation TL'd on large, so sad. 100 tests x 16 colourings x R^2C^2 = 256 x 10^6. Didn't have time to generate maxtests, but was pretty sure that should fit...

»
4 months ago, # |
Rev. 3   Vote: I like it +85 Vote: I do not like it

Has it happened to you that a solution thats calculates all the 5002 answers and then solves each test in constant time passed the small, but not the large? What is wrong with their platform? How is that supposed to work?

Code:

Spoiler

Verdict is: AC on small, TLE on large.

Locally runs on just over 9s.

Their TL is 25s.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are probably many reasons why your code can get large wrong while passing small. What you have described here is definitely too less to draw any conclusions.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Fair enough. I've added some information to my comment.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        OK, if that is TLE then it is definitely weird :P. Hypothetical WA could have been easily your fault.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        Btw, I know that is irrelevant, but you can change

        for (int i = 0; i <= 500; ++i) {
                for (int j = 0; j <= 500; ++j) {
        

        to

        for (int i = 0; i <= 33; ++i) {
                for (int j = 0; j <= 33; ++j) {
        

        and your code should remain correct.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 2   Vote: I like it +51 Vote: I do not like it

          I know, I figured it out later during the contest, but I did not resubmit, due to obvious reasons XD.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    Yesterday, I'm pretty sure I solved a problem by resubmitting (1B B, I was trying an alternative solution that was getting TLE sometimes). And in 2B here, I got TLE on something that was running in 4 seconds locally, even though the time limit on the server is much larger.

    Maybe they're measuring time with an hourglass or something?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Well, that's definitely an unpleasant experience to have during actual contest. Maybe they should pay more attention to testing their platform more thoroughly before throwing it to the world.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +133 Vote: I do not like it

    Update: Resubmitting after the contest ended, the verdict was AC on small and large. Guess you have to submit at the right moment to do well on this contest.

    How stupid.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +121 Vote: I do not like it

      Try making some noise about it to organizers. They should be aware of platform's weaknesses. It's not only your business, we too don't want such surprises in future :D.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +34 Vote: I do not like it

        I have written an e-mail to them. I hope they will catch up with the issue, and it won't happen in the future. Thanks for the idea.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      Damn, O(n^4) got AC? Nice.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    For me, 501x501 array solution first gave MLE :) on the small test set, then exact the same code passed smaller, then gave MLE on big test set, then third time, gave WA on big test set. But WA was correct.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any "hacks" for falling balls? Had wrong answer but haven't figured it out yet.

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I can't understand official solution for c. What's the intuition behind taking at most one vertex from edge AiBj?

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Getting wrong answer for B, but then I took someone else's code that was accepted, generated cases for all possible R & B and took a diff of the output with my code. Surprisingly it's the same. Edit: Figured it out, there was an overflow while calculating the dp

Spoiler
»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Now, The tests are assumed that can be all maximum? In the past, there are small testcases and a few large testcases.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In some problems in rounds 1, the constraints were in the format "3 out of 100 tests are maxtests, the rest are small", so you should probably assume all tests are equally large unless written otherwise. It makes sense if you need to pass test i to pass test i + 1.

»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it +47 Vote: I do not like it

For fucks sake, I didn't solve task because forget to put '#' in 'Case #x:'
I got WA and didn't understand why.
So, suicide is the only way.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    Another way: Copy the expected output and diff it with your output. (I also learned that the hard way.)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Calm down dude

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same with you with 6 wrong submissions for problem A

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For "Graceful Chainsaw Jugglers" problem, I was thinking of a greedy solution. It is as follows:

Make all possible pairs such {A,B} s.t. A+B = i. Here we iterate i from 1 to 1000, and if (R-Ak)  ≥  0 and (B-Bk)  ≥  0, then we update ans  =  (ans + 1), R  =  (R  -  Ak) and B  =  (B  -  Bk).

I got a WA, but I am not able to come up with a counter example. Any help is highly appreciated.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It doesn't work for some cases where R and B have a large difference. Depending on the order of iteration over the pairs with A+B=2, the case 39 3 might fail for example, choosing

    0 1
    1 0
    0 2
    2 0
    3 0
    4 0
    5 0
    6 0
    7 0
    11 0
    

    But you could optimally choose (1,1), (2,1), (8,0) instead of (0,2), (11,0).

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see. Thank you so much! :)
      Just curious, did it come intuitively to you, or you generated some test cases and tested against an AC code?

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        During the contest I at first thought greedy might be correct, but after some time had the intuition that there would probably be a counterexample with larger numbers and larger difference. For actually finding a counterexample now I had to generate some test cases.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    11 11 -> 9:

    1 0
    0 1
    1 1
    2 0
    0 2
    3 0
    0 3
    4 0
    0 4
    
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for the help, but it seems the above algorithm managed correct answer on it.

»
4 months ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

Submitted precomputed answers for B (400kb of code):

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a yahoo code jam or baidu code jam?

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

This entire new UI is so weird. Has so many problems with it. Always kind of asks for logging in, even when I am logged in. Its so weird. The older platform was much better.

»
4 months ago, # |
  Vote: I like it +34 Vote: I do not like it

I spent 90 minutes trying to debug my code for the last problem, and it turns out I had misread the problem statement...

When it says "present in at least a googol deeper dream grids", I interpreted "present in at least one of googol deeper dream grids". After a lot of wrong submissions, I re-read the problem statement and still failed to catch my mistake. In the end, I didn't have any time left to think the harder part of problems B and C and, because of that, I ended up ranking 1200+.

I was sleepy and kinda upset because my computer clock was wrong at the start of the contest, not allowing me to submit for the first 30 minutes. But, I still think that the words "at least" shouldn't have been there. It leads to confusion. It would have been much clearer if it said "present in 10100 deeper dream grids or more".

More on the matter of the clock: It's utterly unacceptable that a competition like Google Code Jam has code that reads your computer time to tell you when the contest starts/ends instead of reading it from a Google server. I lost 30 minutes because of that laziness/stupidity from the designers of the page. I hope they fix that for the next contest, because I wasn't the only person affected by that. Just read the comments on this page alone, and there's at least one other guy.