VK Cup Round 2 online mirror
By Zlobober, 9 years ago, translation, In English

This Friday, April 17th, 19:00 there will be Round 2 of VK Cup 2015! For all unofficial participants there will be an online mirror that is a usual rated div1-round. Any div1 contestant that does not participate in official Round 2 is able to compete in this mirror.

Round consists of 6 problems that are shuffled randomly. There will be a smooth dynamic scoring system.

Round is brought to you by Codeforces team, VK team and user Errichto, that offered his important help as a part of his donation for "Codeforces 5 years campaign". Significant testing effort was made by user winger.

Good luck and have fun!

UPD: Thanks everybody for participating! Editorial has just appeared. See you on Wild-card Round 2 and mirror of Round 3!

Announcement of VK Cup 2015 - Round 2
  • Vote: I like it
  • +319
  • Vote: I do not like it

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

Shuffled Randomly.. this will be interesting :D

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

Is it a rated event?

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

    For all unofficial participants there will be an online mirror that is a usual rated div1-round

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

      Is that an official statement? Could you please point to the source?

      EDIT: Thank you very much. I thought the text was the same as the one sent by email, but it isn't.

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

        Just read this topic...This Friday, April 17th, 19:00 there will be Round 2 of VK Cup 2015! For all unofficial participants there will be an online mirror that is a usual rated div1-round. Any div1 contestant that does not participate in official Round 2 is able to compete in this mirror.

        Here is the official statement

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

I hope that pro A will be the easist one, not pro E like last time.

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

Why I can't register for the round. Div1 participants can take part in only div2 rounds why we div2 participants can't take part in only div1 rounds unofficially ?!

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

    because u can't even solve problem A div2

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

      Actually he can. I know him personally. -_-

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

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

      do not judge people by their rating!!!

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

      Hey Sosiska, let's compete in Round #300. Are you in ?! Let's see who is unable to solve problem A !!!

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

The time is not so good for Chinese Coder... Because such a challenge contest will happen at 0:00 a.m. CST and until 2:30 a.m. CST. Maybe waiting for rating updated until 3:00 .. and 9:00 a.m. CST there is a google code jam Round 1A. I don't want to miss any one...

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

If the team takes place in top 100, will they receive 2 t-shirts?

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

I just read two random problems and decided that don't want to compete in this match :(

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

Our team advanced to round 2 and I have no idea where is the original round 2.

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

    I had to turn language to Russian. You could write the same post on English language. Nobody told me anything. You could email for example. What is the mean of turning off the registration? please at least turn it on!

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

      >What is the mean of turning off the registration?

      Allocation of participants to rooms.

      You got to round 2 and only noticed that the official round is visible only there just now? How did you open the qualification round and round 1, then?

      Yeah, there's probably no point in putting the Russian-only round to the English part of the site other than wanting to see blogs "I can't register in the official round, help!".

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

    It is Russian-speaking only Championship and the rounds are visible in Russian interface only. The schedule has been published in the day of Chanpionship announcement ~7 weeks ago and never changed.

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

So hard! I will get down rating !

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

How to solve E? I wasted all the time on it but my hashing+unordered_map solution didn't pass pretest 22...

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

    Answer can either be 0, 1, or 2. Take the substring from the the first occurrence of different characters to the last occurrence and check to see how many original strings you could have had.

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

      It's not true. If we have two equals strings the answer is not 0, 1 or 2.

      Edit. Ouch, reading the statement twice don't help =)

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

        and we can't have tho equal string according to statement.

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

        That's what I was solving but the 'Input' section mentions that given strings are distinct. I noticed that only after trying to hack with similar strings.

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

          And I don't understand why such essential information was only given in the input format.

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

            Yeah, was going to whine about it. Turned out that I spent quite a lot of time solving a bit different problem. I agree, it should have been mentioned in the problem statement as well as in the input.

            Same is true for B as well, the only part that confirms that the graph is indeed a tree is the input section where it says that pi < i

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

            "Implement a program that can, given two distinct words S and T..."

            That's main part of the statement.

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

              Ok, you proved once again that I can't read:(

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

        It's guaranteed that two string are different. :P

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

        S and T will not be same strings. Even if they could have been then it would be really hard to express the answer without modular arithmetic.

        Takeaway: It's OK to take part in contest at 2:00 AM — 4:30 AM but shouldn't have written comment at 4:30AM in the morning.

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

          If the strings are equal, the answer is 25 * n + 26

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

          I don't think the answer may exceed O(len) * 26

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

          Why? Even if they are same max answer is approximately 26 * N since we care only about distinct original strings.

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

            wouldn't in that case ans be 26 * (N + 1) ?

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

              No, consider the case "aab". If you insert 'a' before the first char and before the second char, you'll get the same strings. The answer is 25 * N + 26, as I mentioned above.

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

              In this case it depends on the string. For example

              2
aa
aa

              The answer here will be 25 + 25 + 26.

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

    So you may not use hashes, just find first mismatch in the strings and define in which of them a symbol was deleted exactly in this position (e.x. s[i+1]==t[i] if a symbol from S was deleted, next I will consider this case).

    Then create two copies T1 and T2 of T with erased symbol inserted before and after position of deleting.

    Finally, you need just to check if erasing a symbol from the second position of mismatching will lead to a string which is equal to S. If both T1 and T2 may be equal — ans=2, if one of them — ans=1, if no one — ans=0.

    I hope it will pass system testing! :)

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

Effect of shuffling and tricky questions: Only half out of all registered people submitted their solutions :/

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

My teammates message(20 min before end): "როდის იწყება ეს დედანატირები მე-2 რაუნდი" ("When vk cup 2nd round will be held?"), Fuck Him -_-

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

How to solve F?

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

    For each possible position and each letter present in t find the candidate letter for the replacement (it might be the same letter). Change s so that these two letters will be swapped and the remaining characters will be replaced with some separate symbol ('*' for example) , it will be kind of mask. Then for each such pair and the possible position you need to check whether this mask from s matches similarly masked t. In valid positions masks for all letters should match. In order to check masks I computed z-function for each possible pair of characters in advance.

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

      Thanks for the explanation! Link to marat.snowbear's implementation 10759593, which is very clean.

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

        Which is also very slow and takes a lot of memory so I even had to avoid storing full z-function vectors. But I don't hash, so I had almost no choice.

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

In prob -B what is the ans of 7 -1 3 1 2 1 1 1 4 4 2 4 3 5 5

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

    17 I suppose

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

      No, the answer should be 14. Take 1, 2, 4, 5, 6.

      EDIT: I misunderstood the problem. The correct answer is 17.

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

        Our AC solution says that the answer is 17

        Take 1,2,4,6,7

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

          thnx .

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

          If you take 1,2,4,6,7 won't that become disconnected since 7 is connected to 4 via 5?

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

            answer can be disconnected . there is just one condition in the problem statement that if i take a node then i must take even number of node in its subtree . answer is 17 here

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

              Thanks. Couldn't solve it just because of misunderstanding the problem :(

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

I can't seem to submit offline. When will we be able to do this?

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

Is there anything special about test case #35 in problem F? Seems like quite a lot of people failed on it.

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

    Anti-hash?

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

      Seems no. Our solution based on Z function also got WA on this test.

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

    My guess is that it's for errors in pairing logic check, e.g. I add only one "edge" in letters map (forgot to add reversed one). But can't check it until the problem is opened for practicing..

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

      You are right. I was just not completely clearing some array. Seems that everyone has it's own bug, and the 35-th test is just a good one.

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

    For example my code failed on #35, and also fails on this simple test:

    2 2 bc ab

    (answer 0)

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

      Almost all possible compilable codes fail both on #35 and your simple test :D.

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

System Testing is over . why cant we submit in practice.

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

My solution of F:

  • if we fix the substring of S (its first letter) to match T to, we can recover the pairing of letters: just remember one occurence of each letter (a-z) in T, look at the letters that are matched to them and here it is!

  • we can check if the given substring of S has the same hash (easily computable using polynomial hashes of prefixes) as T after the pairs of letters are swapped — the hash of T is just , where ki is a constant dependent only on the letter i; specifically, if (letters s[i] are numbered from 1 to 26), then over all i such that s[i] = c.

  • for better accuracy, do it for two polynomial hashes

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

    Same solution, just used big module instead of two hashes 10759121

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

    We had similar solution, but from a bit different angle. For a string, let's assign a number to each character — the distance between the nearest same character on the left (or 0 if this character is the first occurrence in the string now). For T it will be constant, for S it's easy to see that we can modify the hash as we're sliding the window — potentially subtract some power if it becomes 0 after the window slides, and add new character (we do not have to remove old character since it's the first occurrence and it's 0 anyway).

    Now, if the hashes match, we have a valid permutation in this position and only then we have to take first occurrences of 26 letters and check whether our permutation forms pairs.

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

Looking forward to upsolving!!

Zlobober, fix this, pls!

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

    Enabled upsolving in the mirror contest.

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

      Why tests for E problem can not be seen?

      (upd) You can find it in Vk Cup Round 2 log

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

Did you simply forget to make submissions public? If not, what is the reason behind it?

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

    The upsolving is available in the mirror contest.

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

      I know, what I meant is I can not see other's solutions.

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

I was a bit surprised, this is a team contest but rated? http://codeforces.com/contest/532/ratings

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

    Yes. It was a lot of posts and discussions about that at the russian side of CF.

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

    tourist has not seen such a gain for quite some time. Maybe he should have gone in the same team with worse, he would gain even more :D.

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

Could you please link to English version of editorial (or to both versions at once)?

→ Reply