Croc Champ 2013 — Qualification Round
By MikeMirzayanov, 12 years ago, translation, In English

Hi everybody!

Let me remind you that on the 12th of April, at 20:00 the Qualification Round of the All-Russian Programming Championship CROC-2013 will start.

You need to participate in the Qualification Round to make it to Round 1. Contestants who gain a score equal to the 2000-th place finisher score or greater will advance to the Round 1 (also you need to gain positive score).

At the Qualification Round you will find a few problems, roughly ordered by the increasing complexity. During the Qualification Round the problems are judged only on pretests and system testing will take place after the end of the Qualification Round (round continues for 48 hours). The pretests do not cover all possible cases of input data, test your programs carefully! The Qualification Round has no hacks or decreasing values of the problems.

The round will last for 48 hours, but it does not mean that we encourage you to spend all this time solving of problems. We hope that most participants will cope with the problems (or with most problems) in a shorter period of time. This duration of the round is chosen so that each participant could find a convenient time to participate.

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 1. When the Qualification Round is over, you can discuss the problems and solutions.

You can register for the round at any time up to its end.

The results of the round will not affect the rating, non-competitive participation in the round is not allowed. However, all tasks will go to the archive after the end of the round.

Best of luck and enjoy solving the problems!

P.S. You can't take part here unofficially. You may register to the Championship here. The working language of the Championship is Russian, but all the problems will be in English too.

Most agile participants have registered before we implemented validation rules around Championship registration. So some registrations will be canceled. Sorry for it — you may register to the Champ and register for round after it.

UPD: Testing is completed. Unofficially qualification cut-off is 950. Participants with at least 950 points advance to Round 1. It can be changed because of cheaters disqualifications.

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

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

I don't know Russian and the registration form is Russian , how can I fill this form while don't understanding it ?

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

What's ВУЗ mean in registration,should I write in with school name?school code?or any other thing?

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

    ВУЗ means university or college.Write name of your university or college.

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

Good luck! I can't participate because of my age. I wish you have fun.

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

what a pity!!!I want to participate this game,but I don't know Russion...

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

Does "duration=2:00:00" mean that the contest will last for 2 days?

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

I love long contest and ACM-ICPC rules.thank you :D

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

    Well, there aren't ACM-ICPC rules because final tests will be after 2 days.

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

Since it lasts 24 hours, does that mean score is independent of when you submit? I notice that there's still score depreciation on the contest page.

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

What file do I submit? Source file or exe file?

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

The score is independent of submission time, but you still get -50 for pretests failed / resubmissions.

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

I have registered for the contest.. i am not able to submit solutions...

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

    There is registration for competition and reg for contest(elimination round). Maybe you mixed up them.

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

I just came to the Codeforces site and found about this competition. I have registered on the Croc's site, but the contest is already running on Codeforces, so I am not able to register in the system and participate. Is there a workaround for this, or am I just too late?

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

    Read the post:

    You can register for the round at any time up to its end.

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

Quite a pity that there's no T-shirt as rewards. T-shirt is honor for programmers!

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

Will round 1 affect rating ? Thanks.

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

    Croc Champ 2012 round 1 affect rating, so I think Croc Champ 2013 round 1 affect rating too.

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

      Round affects the rating members of both divisions?

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

What's up with system testing?

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

Why it is not possible to open other's solutions?

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

Can anyone briefly describe how to solve problem E efficiently? I tried to construct a suffix array for all strings but get TLE for large tests. Thanks.

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

    You can use simple string matching algorithm such as KMP. At every node, we store a number k where t[0..k] is the maximum prefix of t that match with the suffix of the string we obtain on the path from root. So k of each node can be quickly computed based on k of its parent in O(no. letters on the edge). In addition, hashing is another solution.

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

      I'm surprised that there is no test case in system test as below.

      6

      1 aaaaaaa

      2 ab

      2 ab

      2 ab

      2 ab

      aaaaaaaa

      Using kmp without optimization will result in O(n^2) running time in case like this. To overcome case like this, for every node we keep the longest string below the node and cut the computation below the node when the length of the prefix that ends at the node plus the length of the longest string below it is less than the length of the string we want to find.

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

        It's easier to precompute state transitions for all (state, char) pairs. This solution works in O(kn), where k is the alphabet size.

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

        There really is no test case like this?

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

        Yes, that's correct. However I just need to modify 1 line in the KMP code to pass this kind of test. You can check my submission: 3539931. This is asymptotically good enough if you don't want do precalculate all the states like what rng_58 said.

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

    I solve it using segmentree and polynomial string hashing . suppose there is a string chain , sometimes we delete some characters ,and sometimes insert some characters,and another operation is qeury for a substring's hash value,we can do these operations by segmentree and hash. so this problem is like this,when we come to a node,we add a string to the end of the chain,when backtrack ,we delete the last characters ,and also judge whether the last "cnt" characters is the target string or not.the overall complexity is nlogn , n is the number of total characters my code is here

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

Hi,

I've solved E with hashing, just for fun, I don't think this solution 3540056 should be passed, or am I wrong? Last week read this very good article, so now I would like to understand how Hash working and this is the reason why I want to solve this problem with hashing:) So while I implementing I have the problem how should I choose the modulo, and the multiplicator (I don't know how it should call) which I denote with q. Could you suggest some rule how should these choose?

I read hashing on the wikipedia, but I couldn't find any article about hashing for competitive programming, could you recommend some other article?

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

When the solution come out?

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

How Can you find out who cheated?

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

    As far as I know, some automatic heuristics is used. Then all suspicious pairs are checked for the similarity by human.

    → Reply