Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By RussianCodeCup, 20 months ago, translation, ,

Hi, everyone!

This Sunday, April, 2 at 19-00 Moscow time the First Qualification Round of Russian Code Cup 2017 will take place. 200 top participants will qualify for the Elimination Round, those who wouldn't qualify can still take part in two following qualification rounds.

We have a news for you: we have added Kotlin, Haskell and Free Pascal to our list of programming languages, also you can now submit your Python programs to run in PyPy. Exact versions of compilers and compilation commands are published at the official web site. We are working on adding more programming languages.

Good luck to everyone and see you at http://russiancodecup.ru!

UPD Editorial is published

•
• +118
•

 » 20 months ago, # |   0 Hope, checking won't last as long as in warm-up.
 » 20 months ago, # |   +13 Will there be a mirror contest on Codeforces ?
•  » » 20 months ago, # ^ |   +34 Why do you need a mirror contest? Everyone can participate in the official contest.
•  » » » 20 months ago, # ^ |   0 thanks, i just registered at rcc, i thought it was a closed contest for Russians or something like that, gl and hf :D
•  » » » 20 months ago, # ^ | ← Rev. 2 →   +2 Maybe there are some guys (including me) who want more round which will be rated :)
 » 20 months ago, # | ← Rev. 4 →   0 Hello, I see "Qual" word and green tick front of my name in results of warm-up round:What does it mean? Am I qualified for elimination round?
 » 20 months ago, # |   +18 How to solve E?
•  » » 20 months ago, # ^ | ← Rev. 4 →   +18 The answer is the number of different prefixes times the number of different suffixes in the range minus the sum over all letters of the number of prefixes that end with the given letter times the number of suffixes that have this letter before them in some string (basically, what we do is counting everything, possibly twice, and then subtracting strings that were considered twice). Now we need to count the number of different prefixes and suffixes in a range. If we use hashes, it's just a number of different integers in a range. We can compute it using a sweep line with a binary index tree (we also need to keep a binary index tree for each letter in the alphabet to do the subtractions).
•  » » » 20 months ago, # ^ |   +15 We don't really need hashes. Just construct a trie and assign different integers to different nodes.
 » 20 months ago, # |   0 How to solve C?
•  » » 20 months ago, # ^ |   +5 Optimal order is found by sorting according to the following comparator: (a[i] — b[i]) / x[i]. Then one can do simple DP to find value of savings by using this order.
•  » » » 20 months ago, # ^ |   +10 Been there, done that, gottten WA xD.
•  » » » » 20 months ago, # ^ |   0 Here is my code, it worked for me, hope this is helpful, link:
•  » » » » 20 months ago, # ^ |   0 it was because of precision. I also got WA, but then I did just one division by 1e7 at the end and got AC
•  » » » » 20 months ago, # ^ |   +29 The case where a[i] = b[i] or x[i] = 0 can be tricky. I handled them separately.
•  » » » » » 20 months ago, # ^ |   0 Yes, you're right. I thought my code worked in that case but now I see that I was wrong. Thanks!
•  » » » 20 months ago, # ^ | ← Rev. 2 →   0 With this method I was getting TLE on test 4. Any optimization in implementation? My code
•  » » » » 20 months ago, # ^ |   0 Well just to double check the sorting part just takes nlog(n). Then the dp for me is two dimensions of size n and 2, and constant amount of transition states. Thus nlog(n) + 2n should work in time I believe, constants are not bad I think?
•  » » » » 20 months ago, # ^ |   0 Can anyone please give working C++ code?
•  » » » » » 20 months ago, # ^ |   +5 Here it is.
•  » » » » 20 months ago, # ^ |   +11 Your comparing function can return x
•  » » » » » 20 months ago, # ^ |   0 ohh Thanks! I removed those two lines, but now it started giving WA in test case 3.
•  » » » » » » 20 months ago, # ^ |   +5 For any x!=y you need the function to return true exactly once for x
•  » » » » » » » 20 months ago, # ^ |   0 But if I have d1 = d2. Then it is like I am assuming x = y. So in that case shouldn't it be alright to return false both the times?
•  » » » » » » » » 20 months ago, # ^ | ← Rev. 3 →   +5 No. You can return twice false only for exactly the same elements. Think of it in the way: would a correct sorting of [x, y] be [x, x]? If not, then you can't treat them as equal. And that's the case here.You can check out c++ strict weak ordering for more information about comparators.
•  » » » » » » » » » 20 months ago, # ^ |   0 Thanks again! I understood what was the problem. It worked after removing this ambiguity.
 » 20 months ago, # |   +3 How to solve D?
•  » » 20 months ago, # ^ |   +13 for each index find out how far you can go while having K distinct elements , now do dp with segtree
•  » » » 20 months ago, # ^ |   +23 We can actually keep a multiset of available transitions to avoid using any custom data structures.
 » 20 months ago, # |   +18 How to solve F?
 » 20 months ago, # |   +14 How to solve B?
•  » » 20 months ago, # ^ | ← Rev. 2 →   +29 Check if there exists continuous vertical or horizontal segment of tiles of size more than k. If so, print 'NO', otherwise print 'YES' and ((i + j) % k) + 1 on places where tiles are. (You can check that this answer satisfies the statement).
•  » » » 20 months ago, # ^ |   0 why ((i + j) % k) + 1 works ?
•  » » » » 20 months ago, # ^ |   +1 In the case when answer is "YES" we know that all the segments have length < k. Consider any such segment. Assume that the segment is horizontal. Same argument will work when it is vertical. For this horizontal segment i is constant. So in (i+j)%k will be different for each of those tiles in the segment. As we are incrementing it by 1 modulo k each time while moving along the segment.
 » 20 months ago, # |   +72 I wasted more than 1 hour on problem B misunderstanding the definition of "continuous segments of tiles." Please make problem statements clearer next time.
•  » » 20 months ago, # ^ |   +6 can you please explain it.I m still trying to figure it out.
•  » » » 20 months ago, # ^ |   0 teja349 it means continuous 1's in array.
•  » » » » 20 months ago, # ^ |   0 Ohh ,I overlooked the word contiguous tiles and was always trying for contiguous segments.Can the question be solved for contiguous segments (instead of tiles) or is it NP?
•  » » » » » 20 months ago, # ^ |   0 With Bipartite matching.
•  » » » » » » 20 months ago, # ^ |   +5 Can you elaborate?? How with bipartite matching.PS: I dint mean adjacent.
•  » » 20 months ago, # ^ |   0 Same here.
•  » » 20 months ago, # ^ |   +4 I didn't understand the statement but managed to guess it from the samples. The explanation for samples would be so useful.
 » 20 months ago, # |   +16 Does anyone know where can I submit solution after the contest is over?
•  » » 20 months ago, # ^ | ← Rev. 2 →   +21 It is not possible to submit solution to system after contest, as far as I know, but instead of that you can download tests and check yourself :)UPD: It added to gyms, here :)
•  » » » 20 months ago, # ^ |   0 Ok, I see, thanks!
 » 20 months ago, # |   +26 First Qualification round has been added to gyms: 2017 Russian Code Cup (RCC 17), 1st qualification round
 » 20 months ago, # |   0 I downloaded tests, but in russian-code-cup-2017-qual1/b/tests I can onlu see files named "01", "01.a", "02", "02.a",... How can I see the tests? I am using OS X
•  » » 20 months ago, # ^ |   0 That's it. Just open that files in any text editor. There are few files, but each contains a lot of internal tests. *.a files are expected answers. Btw, your answers for B can be different, that in .a files, but also correct, because there can be more than one correct answer.
 » 20 months ago, # |   0 Is this contest for more than a specific rating or for anyone ?