By Zlobober, 5 years ago, translation, ,

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

• +319

 » 5 years ago, # |   0 Shuffled Randomly.. this will be interesting :D
•  » » 5 years ago, # ^ |   0 Not for all!
•  » » 5 years ago, # ^ | ← Rev. 2 →   -12 ;/
 » 5 years ago, # |   -16 Is it a rated event?
•  » » 5 years ago, # ^ |   +2 For all unofficial participants there will be an online mirror that is a usual rated div1-round
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -32 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.
•  » » » » 5 years ago, # ^ |   +13 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
 » 5 years ago, # |   0 I hope that pro A will be the easist one, not pro E like last time.
 » 5 years ago, # |   -7 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 ?!
•  » » 5 years ago, # ^ |   +52 because u can't even solve problem A div2
•  » » » 5 years ago, # ^ |   +26 Actually he can. I know him personally. -_-
•  » » » 5 years ago, # ^ |   -41
•  » » » 5 years ago, # ^ |   +35 do not judge people by their rating!!!
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   -21 khafe sho
•  » » » 5 years ago, # ^ |   0 Hey Sosiska, let's compete in Round #300. Are you in ?! Let's see who is unable to solve problem A !!!
 » 5 years ago, # |   +16 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...
 » 5 years ago, # |   0 If the team takes place in top 100, will they receive 2 t-shirts?
•  » » 5 years ago, # ^ |   +255 Only one XXXXL.
•  » » 5 years ago, # ^ |   +29 Yes
•  » » » 5 years ago, # ^ |   +5 Thanks a lot
 » 5 years ago, # |   +23 I just read two random problems and decided that don't want to compete in this match :(
 » 5 years ago, # |   -34 Our team advanced to round 2 and I have no idea where is the original round 2.
•  » » 5 years ago, # ^ |   0 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!
•  » » » 5 years ago, # ^ |   +28 >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!".
•  » » 5 years ago, # ^ | ← Rev. 2 →   +16 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.
 » 5 years ago, # | ← Rev. 3 →   0 So hard! I will get down rating !
 » 5 years ago, # |   0 How to solve E? I wasted all the time on it but my hashing+unordered_map solution didn't pass pretest 22...
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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 =)
•  » » » » 5 years ago, # ^ |   0 and we can't have tho equal string according to statement.
•  » » » » 5 years ago, # ^ |   +5 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.
•  » » » » » 5 years ago, # ^ |   +13 And I don't understand why such essential information was only given in the input format.
•  » » » » » » 5 years ago, # ^ |   0 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
•  » » » » » » 5 years ago, # ^ |   +10 "Implement a program that can, given two distinct words S and T..."That's main part of the statement.
•  » » » » » » » 5 years ago, # ^ |   +13 Ok, you proved once again that I can't read:(
•  » » » » 5 years ago, # ^ |   0 It's guaranteed that two string are different. :P
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +5 If the strings are equal, the answer is 25 * n + 26
•  » » » » » 5 years ago, # ^ |   0 I don't think the answer may exceed O(len) * 26
•  » » » » » 5 years ago, # ^ |   0 Why? Even if they are same max answer is approximately 26 * N since we care only about distinct original strings.
•  » » » » » » 5 years ago, # ^ |   +5 wouldn't in that case ans be 26 * (N + 1) ?
•  » » » » » » » 5 years ago, # ^ |   +3 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.
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +5 In this case it depends on the string. For example 2 aa aa The answer here will be 25 + 25 + 26.
•  » » 5 years ago, # ^ |   0 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! :)
 » 5 years ago, # |   0 Effect of shuffling and tricky questions: Only half out of all registered people submitted their solutions :/
 » 5 years ago, # | ← Rev. 2 →   +71 My teammates message(20 min before end): "როდის იწყება ეს დედანატირები მე-2 რაუნდი" ("When vk cup 2nd round will be held?"), Fuck Him -_-
 » 5 years ago, # |   +5 How to solve F?
•  » » 5 years ago, # ^ |   +13 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.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Thanks for the explanation! Link to marat.snowbear's implementation 10759593, which is very clean.
•  » » » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   0 In prob -B what is the ans of 7 -1 3 1 2 1 1 1 4 4 2 4 3 5 5
•  » » 5 years ago, # ^ |   0 17 I suppose
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 No, the answer should be 14. Take 1, 2, 4, 5, 6.EDIT: I misunderstood the problem. The correct answer is 17.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +1 Our AC solution says that the answer is 17Take 1,2,4,6,7
•  » » » » » 5 years ago, # ^ |   0 thnx .
•  » » » » » 5 years ago, # ^ |   0 If you take 1,2,4,6,7 won't that become disconnected since 7 is connected to 4 via 5?
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » » 5 years ago, # ^ |   0 Thanks. Couldn't solve it just because of misunderstanding the problem :(
 » 5 years ago, # |   +6 I can't seem to submit offline. When will we be able to do this?
•  » » 5 years ago, # ^ |   0 It's possible now.
 » 5 years ago, # |   +6 Is there anything special about test case #35 in problem F? Seems like quite a lot of people failed on it.
•  » » 5 years ago, # ^ |   0 Anti-hash?
•  » » » 5 years ago, # ^ |   +5 Seems no. Our solution based on Z function also got WA on this test.
•  » » 5 years ago, # ^ |   0 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..
•  » » » 5 years ago, # ^ |   +8 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.
•  » » 5 years ago, # ^ |   0 For example my code failed on #35, and also fails on this simple test:2 2 bc ab(answer 0)
•  » » » 5 years ago, # ^ |   +5 Almost all possible compilable codes fail both on #35 and your simple test :D.
 » 5 years ago, # |   +39 System Testing is over . why cant we submit in practice.
 » 5 years ago, # |   +13 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
•  » » 5 years ago, # ^ |   0 Same solution, just used big module instead of two hashes 10759121
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   +37 Looking forward to upsolving!!Zlobober, fix this, pls!
•  » » 5 years ago, # ^ |   0 Enabled upsolving in the mirror contest.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +13 Why tests for E problem can not be seen?(upd) You can find it in Vk Cup Round 2 log
 » 5 years ago, # |   +21 Did you simply forget to make submissions public? If not, what is the reason behind it?
•  » » 5 years ago, # ^ |   0 The upsolving is available in the mirror contest.
•  » » » 5 years ago, # ^ |   +17 I know, what I meant is I can not see other's solutions.
 » 5 years ago, # |   +11 I was a bit surprised, this is a team contest but rated? http://codeforces.com/contest/532/ratings
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Yes. It was a lot of posts and discussions about that at the russian side of CF.
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   0 Could you please link to English version of editorial (or to both versions at once)?