halin.george's blog

Google Code Jam Round 1B
By halin.george, 10 years ago, In English

Code Jam Round 1B starts in a few hours(19:00 MSK).

GL & HF.

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

»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Good luck guys!:D

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

The contest in Gym: 2015 Google Code Jam Round 1B (GCJ 15 Round 1B).

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

    Will Round 1A also appear in a Gym? If not Mike, could someone with trainer permissions add it? Thanks.

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

    Can someone help me, how can I see failing test case? Thanks

    edit: I found the problem 5 3 9 -> 3 (I had 4)

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

      5 3 9 -> 3 is correct

      x is where the neighbor located, and o is empty space

      xox
      oxo
      xox
      oxo
      xxx

      which is the best strategy to get minimum possible unhappiness (3).

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

Hmm, seriously, I have no idea about A and B. I just wrote brute force and guessed the pattern.

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

    You make it sound too simple...
    congratulations

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

    I reduced this problem to the following one. Select M edges from the graph so that they have minimal number of incident vertices, but did not know how to solve it. Any ideas how one can tackle this problem?

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

      Graph is bipartite. Let me denote L, R as two parts of graph where every edge is between L and R.

      if n ≤ |L| then the answer is 0 else, we will add more nodes from R part and every node will increase the answer by it's degree in the graph. So just choose those nodes with greedy approach(Which is obviously increasing order of degrees). After then swap L and R and do the same thing.

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

        The problem here is to proof, that we should always take the whole L or R, and not some and .

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

          Yes, I know. I just gave him some ideas as he requested. For me, it was just a guess coming from small inputs and brute force solution. If you can share the proof it would be great!.

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

        It is easy to construct counter-example for arbitrary bipartite graph. In this problem graph is very special.

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

    Glad I'm not the only one. It felt a bit dirty..

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

    Pattern for A? I don't see any easy-to-observe-and-hard-to-come-up observations here. My solution's main ideas were "You have to go through 10k - 1 and 10k for valid k's", "If 10|n, then ans(n) = 1 + ans(n - 1)" and "If I have a digit which is a positions from left and b positions from right I need to perform digit·10min(a, b) operations" and "Reverse is needed unless n looks like 1000...003454, where that 100...00 part is at least as long as half of length"

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

    rng_58 Can you explain your solution of C ?

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

The problem setter pwned tourist :D

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

    I guess that it is some fake Gennady.Korotkevich, since the original tourist ™ passes to the finals automatically as winner of the previous year.

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

      But the coding style is similar to tourist. May be he is practicing it.

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

      Nope, that's him, the same nickname. Also he needs to participate if he wants to be qualified to the Distributed Code Jam.

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

For A-large, I noticed that the answer depended on numbers like 1,11,101,1001,10001, ... and also if N was of order k, then the answer could be found out by a smaller number of order ceil(k / 2) . I couldnt formulate it exactly. Can someone please explain their solution?

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

    First you want to have same number of digits as n. So, you want to move 1->10->100->.. Let's say you have d digits in total. The best strategy is to move to 100..099..9(d/2 times 9) then reverse this to 99..9(d/2 times)0..01 and add 99..9(ceil(d/2) times) to reach 100..0(d+1 digits).

    After that, you would want to make transformations such that, after reverse you have same prefix as n or lesser than that. For example, if you have 10000..0(d+1 digits) and n is of from n0, n1, ..nd, then you have to try for all prefixs n0, ..ni and make 100..ni, ni - 1, ..n0. After that apply reverse to get n0, n1, .., ni00..1. You will have to add ni+1,..nd(suffix) — 1. Make sure that the add component is greater than 1, if it is zero, substract one from prefix and add 1 in the MSD of suffix.

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

      Can you explain why your strategy to move from d digits to d+1 digits is optimal? Is there some standard method behind it or it's just intuitive?

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

        It's intuitive, but can also be proved easily. This problem is adhoc in nature, so there is no standard method(atleast I don't know of any).

        Also, you can sort of follow the approach for the second part of the problem in this. Move from 100..0 to 99..9 (both d digits), and add one to that (you cannot avoid adding one if you want to move to d + 1 digits.)

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

    I only knew that the flip cannot increase the digit of a number, so must go from 1-->10-->100... But then I have totally no idea...

    Also, I do not know if this is important, but will there be a unique optimal path from number a to number b (a < b), that some number c is in the path and c > b > a?

    For example, from 18 to reach 28, will path like ...18-->81-->82-->28 be a unique and optimal one?

    From A-small, I think the answer is No, but I cannot figure out why...

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

      I think 18-->81-->82-->28 is the optimal path when you go from 18 to reach 28.

      But, it's NOT a part the optimal path if you want to reach 28 from 1, because from 1 to 18 needs 18 moves, and from 1 to 20 needs only 20 moves. It's trivial that 18+3=21>20. That is caused from a unnecessary flip move, because you should use <=1 flip moves from any two-digit number to 11,but 18->81->82->28 have 2 flip moves.

      In my solution, the optimal path from 1 to 20 is 1->2->3->4->5->6->7->8->9->10->11->12->21->22->23->24->25->26->27->28(20 moves).

      Sorry for my bad English...

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

        yes I knew it is not as I passed A-small, but I did not have a strong proof on it...also I guessed in same digit range (100-->999, or 1000-->9999), at most 1 flip is used, is that true?

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

      Also, I do not know if this is important, but will there be a unique optimal path from number a to number b (a < b), that some number c is in the path and c > b > a?

      it's illegal in this problem, because ai + 1 should be greater than ai.

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

        Sorry if I missed it, but I did not see this in problem statement...(though by common sense it should be true)

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

          OK, looks like yesterday I misread the statement, and this quickly led me to the correct solution :D

          It is true, but it should be proved.

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

How to fail in a contest:

  • Your computer hangs and you have to retype your solution
  • You find your bug in B 40 seconds before the end, and the bug is 2*r/2 written instead of 2*(r/2)
  • You submit B immediately after the contest and it passes both small and large samples
  • Finally you realize that the problem description only said R*C <= 10000 and not R, C <= 10000 like you assumed
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    BTW, I checked your code, and there's at least one flaw in your rust template. In this line:

    io::stdin().read_line(&mut s).unwrap();

    io::stdin() is protected by mutex, and its read_line() function is implemented like this:

    lock mutex
read_line() from internal buffer
unlock mutex

    You can lock it one time and read everything directly from internal buffer:

    let stdin = io::stdin();
let buf = stdin.lock();
...

    this can lead to significant speedup.

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

      Thanks, I'm still learning :)

      I am not particularly fond of this input macro anyway, because it has to allocate and deallocate a String for every line. But I know no good way to make it work without temporary Strings.

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

I think Round 1B is relatively harder than 1A, isn't it?

At first, I think the first problem should be easy as in round 1A, but it turns out to be quite error prone with lots of tricky cases if one uses the greedy implementation. And I realized not many people have solved the large input, so I decided to solve the small input by dp and look at the other problem.

Again, I thought that I might not completely solve the second and third problem, so I focus on the small input. With B, R*C<=16, so I just consider all combination of placements. With C, where there are no more than 2 hikers, the answer can only be 0 and 1.

After solving these 3 small datasets with 36 points, I thought that's enough to advance since I was ranked around 300 (it turned out to be wrong as at the end, competitors with 37 points advance). But it's quite relaxed for me, then I can look at the large input of the first problem. My solution is that, with a number has k digits, we first need to reach 10^(k-1), and then for the digit d at position i (0-indexed), there's 2 ways to increment it, either 10^i or 10^(k-1-i), except for i=0. For example, if n=3902, we need to reach 1000, then increment to 1093, flip to 3901 and increment to 3902. In case n is divided by 10, we solve n-1 first. To be sure, I have tested the result with every n<1000000, compared to the result of the dp approach.

For large input of the second problem, when N<=(R*C+1)/2, then the answer is obviously 0, we can always allocate the tenants so that there is no pair of neighbor. The allocation is similar with white(or black) squares of a chess board. When N>(R*C+1)/2, we consider empty squares instead of occupied squares. We need to maximize the number of borders of those squares. So first, we start with the inner square with 4 borders, then the edge with 3 borders and last, the conner with 2 borders. The allocation again looks like a chess board. We need to consider 2 cases: choose (1,1) or not.

I haven't figured out the solution for large input of last problem yet.

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

Rank 1001

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

    Congratulations! you should notice that there are some people had advanced to next round ranked in 1000th! ^_^

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

      I dont understand your point , those who advanced in round 1A cannot take part in 1B . So rank 1001 is not supposed to decrease . But if someone is proved of plagiarism only then rank will improve ( which actually happened in 1A and 1001 th person went to the round 2 )

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

    Check the scoreboard again. :)

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

      Ohh wow, how wonderful indeed. Jeez, now I feel really bad for "newSolar".

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

Problem A and B really twisted me from inside. I want to make sure same doesn't happen in next round. Any pointers/links to similar problems like problem A and B? I have 4 days to prepare for the next chance. Also in general if someone has comments on preparing for rounds like these will be really helpful. Thanks

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

    Practice on round 1C from 2014 and 2013. For the preparation of the round, maybe this video will help you. Mimino mentions this idea of generating the first elements of the series, to detect a pattern. Good luck!

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

      Just curious, why only practice on round 1C from previous years? What's the difference between 1C and 1A/B every year?

      → Reply