nuclearbomb's blog

Google Code Jam Round 1B
By nuclearbomb, history, 5 years ago, In English

What are your solutions?

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

Comments Comments (75)
| Write comment?
»
5 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Here is my solution for Expogo but it is giving WA. Any suggestions why I am getting WA?

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

    You swapped flag1 and flag2.

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

      worst mistake I had ever done. Cost me everything. I have given this question all time.

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

        vineetjai, For Question 1 from CodeJam Round 1A, how did you learn the bitwise logic behind the question? Did you obtain this from practice?

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

          just used the logic that the steps are in powers of 2. yes it was a little bit tricky but I think key observation is that you have to use every powers of 2 exactly once. also, you have to practice bit manipulation question for this.

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

    Can you explain your answer ?

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

Haven't solved any. But interested to know — How would you compare the difficulty level of the first, second and third problems in GCJ to the code forces Div2/Div1 problems? I can solve Div2 — C, D (at best). Never tried an E. But GCJ 1st problem seems harder than Div2-C. How would you practice on Codeforces for a GCJ Round 1?

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

    this round was much tougher than previous round 1's . p1 > div2d p2 > div2e p3 > div2f or more.

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

      I think P2 isn't harder than Div2E difficulty. For me P2 was easier than P1.

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

        as u say.. but i felt harder than old round 1. I have solved all round 1 problems from 2008 to 2017 and this problem set was harder that old ones.

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

        P2 was surely easier than P1, even for me, but implementing a binary search and that too during a round was so frustrating, I ditched it finally!

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

          This is why you should do modular programming. :)

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

    I'd say today's A is Div1 B/C, and today's B is Div1 A/B.

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

Lmao, how to solve A?

I tried it for over an hour, then finally moved on to B (which I think is more straightforward).

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

    Let $$$N$$$, $$$S$$$, $$$E$$$ and $$$W$$$ be masks representing the moves in corresponding directions.

    $$$N-S = Y$$$

    $$$E-W = X$$$

    Lets fix number of moves K Then,

    $$$N+S+E+W = 2^K-1$$$

    From above equations we can solve for, $$$N+E$$$, $$$S+W$$$ and $$$N+W$$$ lets say $$$a$$$, $$$b$$$ and $$$c$$$.

    Since, each bit can be present in only one of them, we get

    $$$N=a$$$ & $$$c$$$

    $$$E=a - N$$$

    $$$W=c-N$$$

    $$$S=b-W$$$

    Now, we can just check if the solution is valid.

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

      hitman623 where can i find such type of problems for practice ?

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

      :O

      Also, congrats for country rank 1

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

      I have some doubts. What you mean by masks here ? and how n + s + e + w = 2^k — 1.

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

        The bits which are ON in mask $$$N$$$ are the moves in the North direction. When we fix number of moves, each move/bit should be present in exactly one of $$$N$$$, $$$S$$$, $$$E$$$ and $$$W$$$ therefore they sum up to $$$2^K-1$$$.

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

          Could you further explain your intuition behind: N = a&c

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it +9 Vote: I do not like it 
            (N | E) & (N | W) 
= ((N | E) & N) | (E & (N | W))     // distributivity 
= (N & N | E & N) | (E & N | E & W) // distributivity
= (N | 0) | (0 | 0)                 // idempotency
= N
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              This makes sense. Thank you.

              → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it
      $$$ Just\, loved\, your\, Math\, man.\, Pure\,mathematics!! \,Write\, down\, statement \,into\, equations\, of \,variables\, and\, solve\, for\, them, \, wow!$$$

      This is the solution i was seeking. Thanks a lot.

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

    Find mininal T such that 1 + 2 + 4 + 8 + ... + T >= abs(X) + abs(Y). Now for each of {1, 2, 4, 8, ..., T} you can uniquely determine if it should be negated. Now you have a vector of <= 31 numbers. You should choose a subset with sum equal to x (other numbers will have sum y). It is done with meet in the middle.

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

      Thanks for describing your solution idea. How do you determine the sign of each of {1, 2, 4, 8, ..., T}?

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

        You need to subtract s = (sum — (abs(x) + abs(y))) from the sum (sum = LHS).

        Negative numbers are just the binary representation of the s/2 (if s is divisible by 2 (else "IMPOSSIBLE"), which also essentially means x and y should have different parities).

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

          Does sum = 1 + 2 + 4 + 8 + ... + T in your notation?

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

      I'm really sorry for the stupid doubt, but can you explain the meet in the middle part? I wasn't able to think that.

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

        $$$T$$$ is for sure smaller than $$$2^{40}$$$. As the sign can be determined for each bit, looking at the sum $$$x + y$$$, there are $$$2^{\log T} = T$$$ combinations. This is too much, so let's start off by calculating all the possible values of $$$x'$$$ (so the first half of the $$$x$$$) looking just at first $$$\frac{\log T}{2}$$$ bits. We move to the second part, and for each $$$x' '$$$ (second half of $$$x$$$) we check if such $$$x'$$$ exists that $$$x' + x' ' = x$$$.

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

      We can do it greedily instead of meet in the middle.

      We can get a valid solution if $$$1 + 2 + 4 + \dots + T \geq |x| + |y|$$$ and $$$x \not\equiv y$$$. Let's decide what do we do with $$$T$$$. We want to get such $$$(x', y')$$$ that $$$1 + 2 + 4 + \dots + T - T \geq |x'| + |y'|$$$. Assume that $$$|x| > |y|$$$. A valid pair $$$(x', y')$$$ is $$$(x \pm T, y)$$$, minimizing the absolute value of $$$x \pm T$$$. The pair is valid, so the rest of solution exists.

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

        Another way to do it is to think about what do we do with $$$1$$$, not $$$T$$$. Since exactly one of $$$x$$$ and $$$y$$$ is odd, we need to increase/decrease that number by $$$1$$$. Now $$$x$$$ and $$$y$$$ are both even, so we divide everything by 2 and continue with the next bit.

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

    Try to reproduce the sequence in reverse direction. On each step, check what coordinate has larger absolute value, and make a shift towards the origin along that axis.

    Why does it work?
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I solved it using some visualization. I found the points reachable for every possible string for Len =1,2,3 and then it just followed a pattern. Every point reachable by Len=w will be reachable by Len= z where z > w.
    And if abs(x) + abs(y) = even, then answer is impossible. After this we only need to generate the path. Here is the visualization: vis.png

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

      What do you mean by len?

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

        Len is the length of the string, For example if we are considering Len = 1 then the possible strings are N, W, S, E. And for these strings the integer points on the red square are reachable.

        For Len = 2. Possible strings are NN, NW, NE, NS ... and so on. And for Len =2, The integer points on the blue square and on the red square are reachable. For Len = 3 all the points on the curve |x| + |y| <= K, where K is odd and K <= (2^3-1) are reachable.

        So in general for Len = n, all the points on the curve |x| + |y| <= P where P is odd and P <= (2^n-1) are reachable.

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

    Well, I ran a dfs basically for every index (1<<index) has to present in any one of the directions if at any point u find that N-S == Y && E-W == X print the answer. I got AC for test set 1 and 2 but failed for 3 bcoz of the costly time complexity :(

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

Hard problems.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +31 Vote: I do not like it

A looks like this one: ARC103D. I was suprpised to see it as the first one.

B can be solved by finding any point in the circle and then doing 4 binary searches.

Any ideas to solve C?

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

    In C, I couldn't come up with a tc where just coming from back and maintaining sorted order from back will fail. does anyone know the testcase?

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

    Let's name continuous sequence of cards with same rank as a group. First obvious observation: you shouldn't divide group.
    Let's name group which contains all the suits as complete one. Otherwise it is incomplete.

    The main idea is that if you have two incomplete groups on the top of the deck — you should place them (select as pile A) between next two cards with same ranks as cards in groups(*)(**). Otherwise, there remains only one incomplete group, which can be completed in a single operation.

    (*) — Such cards will always exist because groups aren't complete. Also, it's guaranteed that this cards will be consequent because described solution will keep relative order of card ranks.
    (**) — In such a way you will add one card to both groups in single operation and this is the best we can achieve with described type of operation.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Problem 2 "Blindfolded Bullseye" gave TLE( in the 3rd hidden test set) in many solutions including me.

Please someone tell the reason why?

problem link: https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b63 My sol link :https://codingcompetitions.withgoogle.com/codejam/submissions/000000000019fef2/bWVodWxfMDI

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

Here is my link to my code of B. It's giving TLE, I am not able to figure out why. I am finding the first hit point and then applying 4 binary search. Any suggestions on where I am doing wrong?

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

    I am doing the same and have the same doubt :/

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

    [deleted] do_good_ is right

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

      You were also technically right that it is a mistake, but the odds of hitting the center are too small. Since statement says the position is pregenerated, there's no issue of adaptive grader testing if you handle the corner case correctly.

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

    actually you are getting TLE bcoz you are taking cin >> x >> y for every test case in solve() function. just use it once. i tried it and it is giving WA for ur code.

    I spend most of time with TLE due to same issue.

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

    u need to input a and b only one time

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

I spent the entire time trying to solve problem A, but ended up getting WA on 1 of the test sets. Later I realized that B was a little bit easier than A, but it was too late. Any advice guys on how to attempt problems in competitions where relative difficulty of problems is not mentioned( ex : in codeforces, we can easily discover that problems are given in increasing order of difficulties) ?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +93 Vote: I do not like it

Nobody seemed to describe the easiest solution to A (at least for me). If x and y are both even or both odd we clearly can't get to the goal (except if x=y=0). If x is odd we branch to reduced problems for ((x+1)/2, y/2) and ((x-1)/2, y/2), similarly for the case when y is odd. It can be proven this backtrack has O(log(range)) nodes, since values of x differ by one only, so one of them will be cut out by parity check, so basically our move is uniquely determined at every level (except for the case when we can go to (0, 0), but then we want to go there no matter what).

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

Is there a way to modify interactive_runner.py so that the interaction between the two programs is outputted somewhere?

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

    This is a modification I did to last year runner. I think the runner changed this year, so beware not to use that code, but try to adapt that to the new runner. Probably I'll do it before Round 2 if anybody had.

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

I'm getting WA - - for Expogo on submission. Here is the code run on the first 80 test-cases. IDK which one I'm getting WA on. Can anyone suggest which one I'm getting WA on?

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

my submission This is first problem of GCJ 1B, Can anyone help me why this is accepted instead of giving TLE, I think when tt(in my code line no. 84) is large, it should give TLE.

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

    Your loop contains simple instructions, and you can thank google's 10+ seconds TL policy for the rest.

    The 20 seconds time limit should easily allow you to run the loop 1e9 times.

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

    I wonder what the logic is behind your solution?

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

      Find mininal T such that 1 + 2 + 4 + 8 + ... + T >= abs(X) + abs(Y).
      Here sum is 1 + 2 + 4 + 8 + ... + T. So we have extra move is (sum-abs(X)-abs(Y)), let we call it as tt. Now p=tt/2 moves will be in the negative direction. And out of this p moves, I assume that f1 moves will be in negative direction of X and f2=p-f1 moves will be in the negative direction of Y. So I run a loop for f1 from 0 to p.
      Now,for any f1 and f2 answer is possible only when XOR of (f1,f2,X+f1,Y+f2) is sum.

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

Another solution for A, which was straightforward for me (probably not as simple as Swistakk's solution).

Iterate over the bits of both $$$x$$$ and $$$y$$$ from right to left. Let us say we're on the $$$i$$$'th bit from the right. If both the bits are equal, it is impossible.

Otherwise, check if the $$$i + 1$$$'th bits of the two numbers are equal or not (the bits to the left of our current bits). If they are not, subtract the power of two (by setting appropriate directions) from either $$$x$$$ or $$$y$$$ based on which number's $$$i$$$'th bit is set. If they are equal, add the power of two to either $$$x$$$ or $$$y$$$, again based on which number's $$$i$$$'th bit is set. If both $$$x == 0$$$ and $$$y == 0$$$, break the loop.

This works because if the $$$i$$$'th bits of the two numbers are equal and we've used up all the powers of two for $$$2^k$$$ for $$$k < i$$$, it is impossible. Otherwise, we can either subtract the power of 2, or add it so that the next bit (to the left) which is 0 gets set, and all the bits to the right become 0.

(When I say subtract and add, I mean setting the directions appropriately so that the $$$x$$$ or $$$y$$$ value either increases or decreases; we get our answer when both the values are 0, i.e, we are at our target)

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

How did the people who solved C arrived at the solution? It will be very helpful to me and others to know the thinking process required in this type of problems.

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

    Did anyone solve it by simulation + Observation on small cases?

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

    On the beginning I noted that $$$\lceil \frac{(s-1)r}{2} \rceil$$$ is kind of an obvious lower bound, but didnt have an idea how to construct it, so I was dubious about it being correct answer. Then I wrote simple exponential bruteforce BFS on all permutations, because I thought it would be too hard for me to guess the pattern quickly. Fortunately, solutions I got from it were very heplful and helped me notice the patterns, but even with it, I needed to consider a lot of small cases by hand to get the hang of it and answer turned out to be equal to that lower bound indeed. In total that was pretty hard problem for me, took me more than hour. I am often against writing bruteforces to notice patterns if thinking could be used instead (it is often the case that Radewoosh tells me and Marek that we are stupid because we have not written backtrack for some small cases even though the problem was so simple we managed to get its full understanding within one minute), but everything has its own balance — if problem seems hard to you to then it may be a good idea. I am sure many people solved it without help of bruteforce though, it was doable as well. Probably the best line of attack without writing bruteforce was investigating the lower bound and targeting it directly by inspecting what kind of move we need to make to not make it worse (<=> always creating two pairs of adjacent numbers that will stand next to each other in sorted sequence).

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

In problem A I tried 0 to 32 walks scenarios, and in each scenario I chose from the biggest step to the smallest step while minimizing the manhattan distance between current position and the goal greedily. However I just can't explain why did it works, pls help.

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

In problem B. Since, the x-axis (y = 0) and the y-axis (x = 0) will definitely touch or intersect the circle. So using binary search, I calculated the points of intersection. Now we have two perpendicular chords (or tangents). We can easily find the centre using their mid-points. To get rid of errors I'm also checking some points which are in the neighbourhood of our expected answer.

But I'm getting WA :(
Can anyone please tell me how this is wrong?

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

    How have you applied binary search?

    In order to use binary search, you need to find a point laying inside the circle or on the border at first.

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

      Can you once go through my code? Link

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        1. You can not use binary search that way. Consider the case when the circle has coordinates $$$(10^9/2-5, 10^9/2)$$$ and radius $$$10^9/2$$$.
        2. When the judge replies "CENTER", you need to stop making any new requests and move to the next test case.
        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A Explanation with code if anyone is interested Here

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

IF anyone need Problem B explanation and code Here

→ Reply