Croc Champ 2012 — Round 1
By Gerald, 13 years ago, translation, In English

Good day, Codeforces!

Today at 19:00 the Round 1 of the Open Moscow Programming Championship By CROC will start.

This is usual two-hour Codeforces round with hacks and decreasing values of problems. Everybody, who passed Qualification Round and registered for today’s round, has advanced to Round 1. The remain participants are allowed to participate in this Round out of competition. Round will be rated for everyone as usual. Contestants who gain a score equal to the 300-th place finisher score or greater will advance to the Round 2 (also you need to gain positive score).

You will find a few problems, roughly ordered by the increasing complexity. Score distribution is standard (500-1000-1500-2000-2500). During the Round the problems are judged only on pretests and system testing will take place after the end of the Round. The pretests do not cover all possible cases of input data, test your programs carefully!

Before the end of the round it is strictly forbidden to publish the problem statements/solutions/any thoughts and ideas about them elsewhere. It is forbidden to talk about the problems, discuss the statements and so on. Be honest and let the best men make it into Round 2. When the Round is over, you can discuss the problems and solutions.

It seems that this Round could be a bit hard for Div2 participants. Don’t forget that rating will be calculated only for participants, who make at least one submit.

In today’s round preparation take part: Ripatti, havaliza, haas, RAD, Gerald, MikeMirzayanov, Delinur. A huge thank you to all of them for their work!

Good round to everybody!

Announcement of Croc Champ 2012 - Round 1
  • Vote: I like it
  • +181
  • Vote: I do not like it

Comments Comments (63)
| Write comment?
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Admin plz look in to it. I received a mail that I qualified for round 1 and I also registered for round 1 as usual but now I am trying to submit solutions but it gives me access denied what is the problem admin plz look into it asap.

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

    I am too receiving the same problem ...

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

    Now I had "access denied" too, but using the "Submit" tab (rather than submitting from problem page) helped.

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

    Same here!

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

The problems were quite tricky. I've hacked someone at every problem I've solved (A,B,C) :-)

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

    what kind of tests?

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

    What's the corner case for A? I saw a lot of hacking.

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

    I don't tnink it shows that problems are tricky. Just somebody can't understand that naive algos are slow enough.

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

I will comeback next time！

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

Is there going to be any wild card round like we saw in VK cup??

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

For problem B, if using DFS, what's the time and space complexity?

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

    Can you explain how do you find shortest path with dfs?

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

      You would need to include the distance in the state. This makes the time and space complexity quite large for this problem, but I guess that if in another problem, you really wanted to do it, you can do it.

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

        For this problem, I guess the risk is not high time complexity but stack overflow?

        If someone thought it can be solved by DFS, please let me know.

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

          It is both, I think the maximum result for the distance is around 2000 , so 2000*1000*1000 sounds slow even if you deal with the stack overflow.

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

            How did you get 2000*1000*1000? What's about BFS when the result is 2000?

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

              Talking about DFS, and since you need to include the distance in the state, and the maximum distance is 2000, and there are 1000x1000 cells, then a very sloppy estimation is 2000*1000*1000 (I bet it is much smaller with cropping, but still).

              In BFS (Actually a Dijkstra variation), the distance is not part of the state, so this is not a problem.

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

                Let the function prototype be dfs(x,y,dist,dir). The stop condition of the recurrence is x == n-1 or y == m-1. So param dist is not a decisive factor of time complexity but only stack usage.

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

                  In a DFS, You can visit different (x,y,dir)s with different distance values.

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

                  That's right. But I still thought 2000*1000*1000 is a wrong way to estimate although I agree DFS might be slow.

                  I will try to implement a DFS version which passed systest or failed due to TLE. We may discuss further via private messages then. Thanks.

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

    For problem B, unsuccessful solution was Dijkstra with O(n^2 + m). On 1000 1000 with all #: n = 10^6, m = 2 * 10^9. 2 * 10^9 + 10^6 is TL.

    DFS was even a more stupid idea, i think.

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

      Depends on how you build graph

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

        Yes, but I wrote this to show the solution which passes pre-tests, but is not correct

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

          you can make every point in a number. It only cost 20 long long to represent a line. so the build graph time is O(n*m*20)

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

Is the result of the last query in the sample case of Problem E right?

n = 5, k = 1, r's and a's are given as (1 5 4 1 2) and (4 4 3 2 2), respectively, and the last query asks if the 1st and the 4th members can be together in a group. But their age difference is 2, which exceed k(= 1), so they cannot be in the same group.

My misunderstanding or what?

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

    Condition on ages doesn't look like "no 2 members have ages with difference greater than k", but like "each age of the member of the group should have difference no greater than k with group leader".

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

      I see, but the problem also requires that one of the two members given in the query be the leader, doesn't it?

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

        "It's possible for x or y to be the group leader.", not required.

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

Overly long explanations for Problems A, B and C

I liked this contest, wish I didn't fail so much in problem A so I could have tried D.

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

    One cute way of solving C without using the "shape" array is to define a spiral of size 1 as simply a single square. The recurrence then follows quite naturally for larger spirals.

    → Reply
»
13 years ago, # |
  Vote: I like it -7 Vote: I do not like it

I don't remember when I was so lucky as in this contest, watching the system test was too exciting... (I fell to place 300)

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

why there is no practice after the contest? and the problems are not available in problemset also.

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

Why is Dijsktra for B too slow? 1000 * 1000 * lg(1000000) * 4 = 80 million, which should be doable in 2 seconds. Unless the server is very slow today ... :(

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

    True story

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

    It's kind of pointless to use Dijkstra when your graph only contains edges of weight 1. ;)

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

      0 and 1.
      But BFS is enough, throught

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

        BFS when weights are 0 or 1 is Dijkstra, just optimized for such low edge weights.

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

          Use deque and it's still BFS.

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

            Yes. Boundaries between these algorithms are not so crispy. A BFS when weights are 0 or 1 is both a BFS and Dijkstra :)

            Even with normal BFS using a single queue, if you use it to find the shortest path, you are applying Dijkstra's idea. The original Dijkstra algorithm didn't use a heap. It was just the concept to expand the current shortest path first. When you do a BFS to calculate the minimum path, you do exactly that. Specially if you use a deque, you are no longer just doing a search, you are already following the same algo but with a deque instead of a heap.

            So, Dijkstra works in this algorithm, just use a Deque instead of a heap.

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

              Can you please share how you use to a deque to make it work?

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

                Some edges have cost 0 and some edges have cost 1.

                Normally, you have a queue and push all edges to the back of the queue.

                If you have a deque, you can push edges that do not increase the current distance (edges of cost 0) to the front of the deque. And edges that increase the distance, cost 1 to the back of the deque. Afterwards, it is the same as a BFS.

                It works because it guarantees the node with the shortest distance is always at the front of the deque.

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

    There was no need to write Dijkstra, especially with heap. Didn't you think about any simpler solution?

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

    The complexity of Dijkstra with a heap is O( log(|V|) x (|V| + |E|) ) I think that the usual Dijkstra solution has |E| around 4x4x1000x1000 and |V|=4x1000x1000 (There is a node for each pair between each cell and each of the 4 directions. And for each of those nodes, there are 4 edges towards other nodes in case the cell it is a column).

    Your complexity estimation seems to be |V|x log(number of cells), quite smaller. O( log(|V|) x (|V| + |E|) ) is 5 times larger and yields 9 digits.

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

      I see, I missed out the number of edges. So I need around 400 million operations in the worst case.

      Still, that is on the order of 100 million operations, so it should pass? =D

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

        Set has a high constant (as compared to others algo like bfs..), so it would not pass

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

Thanks for the great contest . There was lots of div 2 participants in the contest so please prepare more problems for div 2 like the VK 2 contest .

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

I got about +10 hacks in A by using this case

2000000000
R
R

These hacks saved my score after failing A and B. I was so lucky. Nice contest, by the way! :)

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

+0 rating change. This is the second time it happened to me!

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

Can someonw tell me whats wrong in the submission(for Prob B)..Solution...

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

There's inconsistency in final standings and rank in member's profiles, take Petr for example, he finished 3rd, but on his profile page the graph shows Rank: 4

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

    There is one unofficial participant above Petr

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

      thanks for reply, I think usually official rank is displayed

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

        Rank shown in profile should be the rank used to calculate rating, which includes unofficial participants in this contest

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

Since the editorial doesn't seem to be coming, could someone share the ideas of their solutions to D and E?

→ Reply