manishbisht's blog

Google Code Jam Round 1C
By manishbisht, history, 9 years ago, In English

Don't forget that Google Code Jam Round 1C will be starting in less then 28 hours !! Visit the Code Jam site and get ready to compete.

Let's discuss solutions here after the contest. I would like to know other peoples approaches.

Good Luck :)

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

Comments Comments (43)
| Write comment?
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

C-large?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it 
    int j, p, s, k;
cin >> j >> p >> s >> k;
vector< vector< int > > res;
int diff = min(s, k);
for (int i1 = 0; i1 < j; ++i1) {
    for (int i2 = 0; i2 < p; ++i2) {
        for (int l = 0; l < diff; ++l) {
            int i3 = (i1 + i2 + l) % s;
            res.push_back({i1 + 1, i2 + 1, i3 + 1});
        }
    }
}
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      you are genius! my solution of C_small is about 100 lines:)

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

      Can you please explain what you are doing? You have chosen diff as min(s, k), so any pair of (jacket, pants) will not occur more than 'diff' times. But what about the (jacket, shirt) and (shirt, pants) pairs? I did not understand how this guarantees that those pairs will also occur <= k times.

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

        It's easy to prove that for arbitrary present pair (i1, i3) of jacket and shirt and every l in range [0;diff) there is at most one valid pants i2, i.e. satisfying constraints i3 ≡ (i1 + i2 + l)(mod s), because s ≥ p ≥ j. That's why we get no more than diff ≤ k pairs (i1, i3).

        The same holds for arbitrary present pair (i2, i3).

        → Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it -6 Vote: I do not like it

is the solution to problem A: always remove first two biggest numbers of senators?

nvm source code removed

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

    No. If there is three senators from different parties, you should firstly remove only one of them.

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

    Countertest is 1 1 1. You'll remove AB. Then you'll have one C. But the correct answer is A B C.

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

      You probably made a typo there. The correct answer is "A BC" and symmetric versions thereof. The answer "A B C" is not correct because after A and B leave C would have majority.

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

    If there are odd no of total senators , In first move remove only 1 largest senator Then for rest keep removing 2 largest ones

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

It was so frustrating that I was debugging my B for more than 20 minutes just because I was printing extra spaces between the elements. =/

Reminds me of how stupid I can be at times.

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

    Oh. I just learned I made the same mistake. Never fixed it during the contest. I know how you feel...

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

C-small?

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

    I generate set of all possible variants and the find best subset. But it looks like just hardcore all answers is simpler:)

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

      Isn't it O(T * 2 ^ 27 * 27)?

      I mean, that shouldn't give an answer in 4 mins, right?

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

        You can remove one 27 with just doing dfs, which is enough.

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

        O(T * 2 ^ 18 * 18), I hardcore answers for 3 3 3 k

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

        But it gives the answer in about 2 mins, Lily

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

          OK, will definetely try brute-force next time.

          P.S. You missed letter 'l' in my name.

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

        I wrote O(T × 227 × 27) in Java with multithreading, and it took 3 minutes 21 seconds (8 minutes 58 seconds total CPU time)—but I screwed up a bit and ended up running out of submission time somehow (and with too little contest time to make another attempt).

        After the contest, I added these lines at the start of the 227 loop body:

            if (Integer.bitCount(mask) <= bestTotal)
        continue;

        Now the whole thing terminates in just 12 seconds.

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

    I did total brute with some optimizations ( I read the constraints incorrect and I thought total combinations will be only 9 ) that is why I wrote a total brute.

    Link to code

    It ran in about 27 seconds

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

      Yep, the popcount check really helps. Like I said in another comment above, my brute went from 9 minutes to under 20 seconds when I added the popcount check. Sadly, I didn’t do it during the contest, as I didn’t imagine it would have such a huge effect.

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

Was brute force able to pass for C small?

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

    Yes, if you hardcore answer for 3 3 3 k

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

      Why is this a special case?

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

        Because for this case there are 27 possible variants and for all others less then 18. O(2^27) is too much (if you haven't 10+ threads), but O(2^18) is OK:)

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

1B rank — 1206
1C rank — 1149

i think i will never make to top 1000 :(

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

    1B rank — 1042

    1C rank — 1003

    Hahaha, and this time the error was so stupid :'(

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

      I saved all files as .txt and uploaded.Worked fine .

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

What is the solution for B?

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

    The main idea is following: let's build a graph, where there is an edge V -> U (for all V, U, V < U). It's easy to see, that in this graph the total amount of ways to get from point 1 to point N is 2 ^ (N — 2) (because we can choose any subset of vertices from 2 to N — 1 to go through). Now, if we delete an edge 1 -> V0, we'll lose 2 ^ (N — V0 — 1) ways. Thus, we can use greedy algorithm : iterate over all V0 (from 2 to N — 1) and try to remove an edge (1 -> V0).

    Code : http://pastebin.com/WrGmMdtU

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

      We can also not to remove, but add the edges (1 -> K) using the binary representation of (m - 1)
      (edge (1 -> B) that gives us 1 way I took in any case).

      Code: http://paste.ubuntu.com/16298555/

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

        Yeah and I kept adding edges from i to j for all i < j in a loop going through all j for each i from 2 to B-1 until I had gone above M, and then I used the binary representation of the difference between how many paths there currently was (which I had kept count of) and M, to delete the edges between the bits that are on in the difference and B-1, it follows the same kind of logic to prove it works.

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

          Your solution seems to be unnecessarily complicated. The main reason for me to use binary representation was to avoid greediness. Since every number has exactly one binary representation, I can iterate from 0 to B-3 or vise versa and get the solution anyway.

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

            I agree that yours which is also the way of the contest analysis is much more straight forward, I just came to the other one, and thought I'd share a similar but different approach :). I don't use anything that's greedy either though, I just keep adding edges until I'm past M and if it's not equal to M I use the binary representation of the difference to remove edges that will make the paths == M

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

    I did backtracking + dfs Basically kept adding edges using dfs as long as no. of paths was less than M If addition of new edge led to no of paths >M remove it and try others Keep count of no. of paths starting at a particular bldg and ending at final building

    http://pastebin.com/MaKJBdGK

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

I accidentally deleted my input0 for 1st problem, so when I downloaded it again, it triggered input1 for the problem, so two incorrect solutions. Can anyone expain this? Anyway I finished with 1004 missing the cut by 20 seconds :(

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

    If you download input twice, you should have only one incorrect submission, you can try making a complaint.

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

    Now you're in :)

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

That moment when your problem B fails due to ll maximum = 1 << (B-2); overflow that should've been ll maximum = 1ll << (B-2);

"luckily" I would only have placed around 1300 if I'd gotten it correct due to being slow, otherwise I would be punishing myself for that for a week :P.

→ Reply