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