Recent actions

Thanks.Good luck

Good luck to everyone, hopefully we will classify for the next round!

Created or updated the text

fixed :)

when?

It hasn't been posted yet.

Sure. You will be able to get it later in the trainings section

Will the problems get added to Gym like Qualification Round 1?

Nice trick!

Yes

My solution is similar to hellman_'s one, except a trick to avoid log factor in the complexity :). Maintain two array a[], b[]. When adding/removing a segment of leng d we add/substract one from a[d / sqrt(N)] and b[d]. To find the maximal len, we need only O(sqrt(N)).

Created or updated the text

I tried to, but got TLE :(

First, transform array into prefix sums + lift it up by 100000 to avoid negative values. So our goal is to find longest interval such that arr[l] = arr[r] inside the quered interval.

We start MO's algorithm and check intervals. We maintain:

  • for each value: a deque of indices of this value in our current interval (easy to add/remove index from any side);
  • a multiset of maximal lengths for each value (that is multiset of all deque[val].front() - deque[val].back()). The multiset is also easy to update since we can compute the length for the value from the deque. The answer for current query is then the largest value in the multiset.

At the end of block check, we can clear the multiset directly, and clean the deque's by collapsing the current interval.

PS: I used map<int,int> instead of multiset.

The edge here signifies (ind,arr(ind)) ???

Very Nice, So chemthan, Please explain your solution .

Yes, it does. I solved it by MO.

The answer to the fully given array = N — number of cycles. So you collect all cycle segments (e.g. ? -> 1 -> 4 -> 5 -> ?) where ? is controlled by you. If you have one segment — you have no choice (just put one element you have). Otherwise you can connect all segments into a one cycle (e.g. end0 -> start1, end1 ->start2, ... endI->start0), thus maximizing the answer.

Minimize the number of cycles.

I have a feeling that E can be solved using MO's Algorithm but I don't know how xD So Can Someone Help Me ?

How to solve C?

I qualified in the previous round. Can I take part in this round unofficially?

Yes. They said there was a problem with the post and they're going to send it again.

Thanks for the link! Did you end up with a reply?

http://codeforces.com/blog/entry/51001#comment-349145

by the way, the typo was really funny :D

Oh my gosh — thanks :P That wasn't intended!

Don't be so critical!

Has anybody received their shirts from last year?

EDIT: oops... that was an unfortunate typo!

If I qualified to the elimination round, how can I receive the certificate and I'm live in Egypt ?!

Created or updated the text

Is this contest for more than a specific rating or for anyone ?

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.

Thanks again! I understood what was the problem. It worked after removing this ambiguity.

why ((i + j) % k) + 1 works ?

I didn't understand the statement but managed to guess it from the samples. The explanation for samples would be so useful.

Ok, I see, thanks!

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.

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?

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.

For any x!=y you need the function to return true exactly once for x<y and y<x. Without these two lines it may return false twice if d1=d2. I usually return lexicographical order in such cases like your d1=d2.

ohh Thanks! I removed those two lines, but now it started giving WA in test case 3.

Your comparing function can return x<y and y<x for some triples x,y (e.g. both having a=b) and the sorting enters infinite loop.

Here it is.

Can anyone please give working C++ code?

Can you elaborate?? How with bipartite matching.

PS: I dint mean adjacent.

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

With Bipartite matching.

Same here.

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?

teja349 it means continuous 1's in array.

First Qualification round has been added to gyms: 2017 Russian Code Cup (RCC 17), 1st qualification round

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 :)

can you please explain it.I m still trying to figure it out.

Yes, you're right. I thought my code worked in that case but now I see that I was wrong. Thanks!

Does anyone know where can I submit solution after the contest is over?

I wasted more than 1 hour on problem B misunderstanding the definition of "continuous segments of tiles." Please make problem statements clearer next time.

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?

The case where a[i] = b[i] or x[i] = 0 can be tricky. I handled them separately.

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).

it was because of precision. I also got WA, but then I did just one division by 1e7 at the end and got AC

Here is my code, it worked for me, hope this is helpful, link:

We don't really need hashes. Just construct a trie and assign different integers to different nodes.

With this method I was getting TLE on test 4. Any optimization in implementation? My code

Created or updated the text

We can actually keep a multiset of available transitions to avoid using any custom data structures.

Been there, done that, gottten WA xD.

How to solve B?

How to solve F?

for each index find out how far you can go while having K distinct elements , now do dp with segtree

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).

How to solve D?

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.

Created or updated the text

How to solve C?

How to solve E?

Maybe there are some guys (including me) who want more round which will be rated :)

Hello, I see "Qual" word and green tick front of my name in results of warm-up round:

Capture

What does it mean? Am I qualified for elimination round?

thanks, i just registered at rcc, i thought it was a closed contest for Russians or something like that, gl and hf :D

Why do you need a mirror contest? Everyone can participate in the official contest.

Will there be a mirror contest on Codeforces ?

Hope, checking won't last as long as in warm-up.

I have to add the contest to gyms soon.

Will the test data be public ? Or maybe add the contest to gym like last year ?

There is one trick to search all cycles of length 3.

code

It seems that this code is slow but it works in O(n*sqrt) where n is number of vertexes in our graph (i don't remember proof of that). so use compression for numbers to make n = 400'000 not 1'000'000 in worth case

so as you see this part solves when sides look like (x,y)(x,y) (x,z)(x,z) (y,z)(y,z). other cases, when answer looks like (x,x)(x,x)(x,x)(x,x)(x,x)(x,x) or (x,y)(x,y)(x,y)(x,y) (x,x)(x,x) can be solved in O(n*log) with map

D can be solved in O(1) by case-studying.

During contest, I coded a brute-force method to check all the possible assignment of knights and knaves for k ≤ 10. And, find out the pattern for each pair of

How to solve E in ?

Created or updated the text

It is already posted here.

I used combinatorics but failed on test 20. I think I made mistake with counting same numbers.

And tests :)

Will you post the editorial?

How to solve C?

There must not be such situation.

Please send what you think is incorrect using "Feedback" form at the bottom of http://russiancodecup.ru page.

It looks like you rejudged my solution, and I got extra penalty because of it?

Created or updated the text

Sorry for the delays, the queues are almost real-time now, we thank you for your patience. We will make sure this doesn't happen during qualification rounds.

yep :( we got 2500+ participants instead of usual 1200. Trying to find additional capacity now

Well this is not the best start so far, seems system is already lagging tremendously in the judging :(

I mailed you, but I didn't receive any response.

Sure :)