Goldsmith94's blog

Google Code Jam Round 1A
By Goldsmith94, history, 9 years ago, In English

Let's discuss solutions here. I know I'd be curious to hear other peoples approaches.

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

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

Well, that was one of the shittiest qualification rounds I've ever seen. You know you screwed it up when even full score doesn't advance you through.

So we have simple A, and then B, where the only task is to see the trick. The trick is nice (output the numbers appearing odd amount of times), sure, but you can just get stuck on that problem easily, which isn't the task you want to put in your set if you require 100% to advance. And then there is an actual Round 1 task, C, although also not too difficult in my opinion (especially with N = 1000 instead of bigger ones even the implementation is simple) and in no way capable of differentiating the top 1000.

I don't think my opinion of the round would've changed if I didn't get stuck on B. The only thing that would've is me not wasting 2.5 hours during the night.

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

    I also got stuck on problem B. I spent about one and a half hours working on a constraint-based approach before I shoved aside all my complicated code, looked for an easier approach, and found it. I'm angry at myself, not at the problem authors. I think it's perfectly legitimate to write a problem in which a single "Aha!" insight leads to a compact solution.

    In fact, aren't those among the most satisfying problems to solve? I like a problem that rewards creative thinking rather than prior knowledge. I was pleased with this problem set even though I didn't manage to solve the hard variant of problem C in time.

    Let me also point out that only 55 people who scored 100 failed to make the top 1000. That seems close to optimal, doesn't it? In other cases there are many more people who fail to make the cut-off even though they scored the same number of points as the last person who did make it. Here only the bottom 5.2% of people with the same score failed to make it.

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

      I got bit by problem B too, couldn't find the trick. How did you guys approached problem C, I wasn't able to find solution in time.

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

      Note that I didn't say anything about the tasks. I enjoyed the beauty of B after I learned its solution. It's quite possible to create a shit round with good tasks, as we just saw.

      In qualification rounds I consider any round where there is any must-have problem to be quite bad. Good qualification rounds, in my opinion, are those where even if you fail to solve one task for various reasons, you can make it up by solving different (and usually harder) problems. Here there weren't even hard tasks, in my opinion. I think this is a safe thing to say considering the results. They even simplified C by allowing quadratic solutions. Not even solving everything was enough.

      The organizers have avoided a massive shitstorm by having this failure as 1A, where from past experience, the results have been weaker, as most of the Europe is asleep (stupid me). I fear to imagine the cutoff if this was round 1B or 1C.

      And I sincerely hope that there weren't any naive brute-force solutions which just managed to pass the test data. Mine brute-force TLE'd on a single test and I wonder if a bit more pruning would've solved this problem.

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

        For B, I couldn't realize the trick during contest however my bruteforce with pruning passed. Though didn't expected but i submitted for both small and large tests in the last minute and it just worked (phew). Code: http://ideone.com/cj02mr

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

    Me too. I wasted about an hour on B and was angry at myself after realizing the trick. Anyways, I still think it is a fun contest. I need to try harder next time.

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

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

    Is it that important to qualify when there are three round 1s? Judging from your performance here you still have more than 99% chance to qualify.

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

      As I said, my performance on the round wouldn't really impact my opinion on the round. The bad round doesn't magically become good if I'd qualified. I hoped that no one would interpret my comment as "I didn't qualify, this round is shit" type of comment, but looks like it was inevitable.

      So, let me clarify. I didn't qualify because I failed. As simple as that, and quite unrelated to the matter, which is why my performance is never mentioned in the original comment, with the exception of a remark at the end, in hopes to prevent people from thinking about this as "I didn't qualify, this round is shit" type of comment.

      What I'm against about are qualification rounds (by which I mean any rounds where some amount of contestants qualify for something) where a single mistake can doom one. Should one get penalized for failing one task for whatever reason? Of course. Should there be a way for them to bounce back by solving other (and usually more difficult) tasks? I believe so. Sometimes this doesn't happen though, because organizers misestimate the difficulty of tasks and either run out of tasks completely or the remaining ones are way too hard for the qualification level. In these cases I don't consider rounds as good ones, no matter what my performance was.

      Do I antagonize the problem setters? No. Creating a balanced problem set is hard, and mistakes happen. However, do they consider this round a problem? Doesn't look like it from the analysis, where they say "To be in the top 1000, you needed a perfect score and a little bit of speed. However, there are two more chances to qualify for round 2"! And this is what worries me the most. But how do problem setters learn about problems if not from the feedback? Which is why I believe similarly to "Great round!" comments when they are appropriate, "This round was bad, here's why" comments are also as important.

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

        Well, I agree that it's not good if a single mistake leads to disqualification, but in order to avoid that they have three round 1s. You have to make at least three mistakes to disqualify in round 1.

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

        Agreed about the feedback part. I would not comment here either if the official overview showed a hint of concern.

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

I got stuck on B as well, and never quite got the trick, went on to C and made quite a bit of progress, after seeing the contest analysis I just changed a few lines of code and it was done, what I needed was a bit extra mathematical analysis of the graph, realizing that it was (what is apparently called) a pseudoforest, that there'll only be one cycle per connected component etc. I was nearly there, I was just trying to do a more complete search of the graph from all the points that had cycles of length 2 (and compare with the longest cycle for the final answer) I was just worried about all kinds of cases that mathematical analysis would've shown to be impossible

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

Problem A was quite easy — although I made a harder approach which wasted my time like 10min. For all alphabet, place the alphabet in the front or back, and simply pick the lexicographically smallest. This is the most intuitive approach and we can prove it's correctness by induction. Both part was fun and it was my favorite.

I have no idea why problem B was created. The solution was really trivial (print element with odd occurence), and usually it means that I read the statements wrong. But it was not.. I checked the english again and again after clearing the problemset.

Problem C was also interesting. I first thought that the answer is longest cycle, but after analyzing sample input more, I found something interesting happens when there is a cycle of length 2. We can find two longest root — leaf path, which roots at two cycle vertice, and insert it into a circle.

I felt that GCJ problems are very tricky and that makes me nervous. I had a sad memory of failing R1B/R1C last year, (I was still 2000+ then) and today's problem B reminded that sad memories..

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

    Problem B was created for people who like to make things complicated. Here is my solution: http://pastie.org/private/qqdg5cnchgtffvnkdcn7w#5,98 . I was so proud I found it (and proved, by induction!), This took me more than an hour.

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

    Your lesson plan for tomorrow includes an activity in which the participants must sit in a circle. You want to make the activity as successful as possible by building the largest possible circle of kids such that each kid in the circle is sitting directly next to their BFF, either to the left or to the right. Any kids not in the circle will watch the activity without participating.

    They don't know what a circle means apparently. At least they could've said they're redefining a circle.

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

      Can I ask you what is the problem with their statements?

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

        Isn't a circle supposed to be a cycle without extensions?

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

          The kids are sitting in a circle. That has nothing directly to do with the graph where you find disconnected cycles with extensions and add them together in a circle.

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

    Hi, ko_osaga could you give more insight as how to solve Problem C? I went through the problem analysis and got kind of confused Thanks

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

      First observe that it's a graph, and it's special. it looks like a tree hanging in the vertex of disjoint cycles. https://en.wikipedia.org/wiki/Pseudoforest#Graphs_of_functions

      Now, it's clear that the cycle can be inserted into circle. If we insert a cycle there, we can't insert other vertices, unless (size of cycle) == 2.

      What can we insert more, if (size of cycle) == 2 ? If we insert those cycles, there are some extra spaces (left / right) to insert a single path. Also, we can append other subgraph with (size of cycle) == 2 as lot as we can.

      cycle detection can be done with various ways, (I used the way simillar to topological sort) and simple dfs will be enough for finding a single longest path to insert.

      Download my source for implementation : https://code.google.com/codejam/contest/4304486/scoreboard?c=4304486#vf=1

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

I got the trick of B as soon as I wrote the grid of sample test on paper. And after the contest, I found out that many of my friends with a high rating (purple, almost orange) could not solve B.

I remember seeing some math problems those looked pretty hard but if you give them to a little kid who just started schooling, he will solve it in an instance. Perhaps this was like one of those :v

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

This would have been a better round overall if it featured a fourth problem. The points for subproblems did not actually have any meaning for the cutoff, and there was no tolerance for errors. These flaws are not fatal since it was just the first of three sub-rounds, but they are serious flaws nonetheless.

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

    It would be nice if Google allowed all people who got perfect score to qualify.

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

      However, this would not remedy the two specific flaws I mentioned.

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

Frustrated about GCJ Round 1A? Wondering if lack of Ahmed Aly did this :|

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

Sad story. Woke up at 2am, solved 3 problems, realised that submitted wrong code for the first problem, asked organisers to resubmit the source, they refused. Outcome 89 points, 1059 place, and sleepless rest of the night thinking what a hell...

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

    Does the code not only using for finding cheaters?

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

    Hey my friend also submitted wrong code in 1st problem but his output was correct ,, and he got full marks,,

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

      Well, he didn't ask to resubmit... He might be caught though when source code has been verified.

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

With regards to problem B — has anyone ever seen a problem based on a similar idea before?

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

    One that comes to mind is this — http://acm.timus.ru/problem.aspx?space=81&num=5. It's also based on the parity concept and has an elegant solution. You can also think about the minimum number of steps required to find the artefact for any N.

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

      Thanks though apart from parity this seems to be quite different/unrelated?

      → Reply