Recent actions

Marcin_smu, you lucky bastard :P

Created or updated the text

I got the answer from I_love_natalia. It seems memory allocator/deallocator are slow on RCC. I guess my solution was slow because I used too much vectors/priority_queues.

Thank you!

To RussianCodeCup: I still don't know why I got TLE for E during the contest. My submission is #27152353 of http://codeforces.com/gym/101397/status/E, and it's much faster (2027ms) than genomes_iz_2modules.cpp (2870ms). Is it possible that my code works very slowly on RCC's server?

Sorry for long delay, contest has been added (finally!) to gyms: 2017 Russian Code Cup (RCC 17), Elimination Round

0n25, already mentioned that Codeforces have internal error which not allow add problems to gym. They will be added after problem will be resolved.

Will there be a place to submit solutions after the contest?

My solution (http://ideone.com/ahuhnB) is a little different from described here. For each point I generate a set of vectors from it. The number of right and obtuse triangles is equal to number of pairs of vectors with non-positive scalar product. To find it I rotate the vector and support the set of such vectors. Once it becomes co-directional with one vector I increase number of bad triangles by number in the set. Supporting it is quite simple since a vector enters this set from the moment it coincides with one of orthogonal vectors and leaves after it coincides with another. So I put into the set of events for each point 3 events: add point, query result, remove point. I start with vector slightly above vector (-1,0) and make a full circle counterclockwise.

Could someone please paste their implementation of D (which they think is elegant)?

I mean how can I use the checker to check my solution on my computer. I don't see a main function in the checker, and I see a lot of "import ..." that I've never seen before.

Sorry for my inexperience with Java.

You can try DFS, you just need hash table to check point exists or not and same for visited.

How to use the checker for problem C on my computer ?

Just count for every vertex v, number of pairs (u1<u2) ui!=v, such that Ang(u1-v-u2) < 90. Then you just need to subtract 2 * binom_coef(n,3).

What is solution for D?

No, you just have not to get position (0,y) or (x,0) at the end (to make both subsequences not empty).

If we take n vertices of regular n-gon then the answer will be about .

My solution is O(N2), but it didn't pass test 9 because of the corner case.

I greedily construct the answer one by one. I store the set of pairs of prefixes of a and b I used to construct the answer up till now. It has size O(N), because for each prefix of a we're only interested in the shortest prefix of b.

For the given pair of prefixes, we can take any element, after which there's enough elements to construct the rest. We need the smallest, so we can take RMQ over the next allowed elements in O(1) for each pair, and find minimum over the pairs.

Now, we need to advance the prefixes to reach the chosen element. To do that, we can just construct arrays of pointers to the next occurrence of this element in both arrays in O(N + M).

Yes.

Is the final round online?

How close can the answer in problem D (about triangles) be to for a huge n?

Tried to come up with several tests but answer turned out to be small all the time

So, you don't fix the number of elements chosen from each array?

We just construe answer one by one and for each position in either array keep track of minimal position in the other array such that we can construe prefix of answer we have so far from corresponding prefixes of arrays

I used min segment tree for creating subsequences and O(N * log(N)) suffix array to merge them and it passed.

Created or updated the text

There is a solution for n^2log. You check symbols one by one for nlogn and also keep in mind dp[x] = min{y, you could have finished known prefix with x-prefix of a and y-prefix of b}.

Same. Quite atificial condition that we can get rid of just by adding following to the end:

        if (maxElement(answer) < minElement(b)) {
            answer[k - 1] = minElement(b);
        }
        if (maxElement(answer) < minElement(a)) {
            answer[k - 1] = minElement(a);
        }

Got WA#9 in problem E because missed the fact that both subsequences must be non-empty...

What's the intended solution for E? priority_queue for getting subarrays and binary search + hash for merging sequences get TL.

When you are one of the few people (3 to be exact) who solved F and you didn't get a T-shirt, because you forgot that in Russian Code Cup all problems are worth the same :')

Top 200

T-shirts?

Created or updated the text

No idea what is stack limit in Visual C++, but I submitted it in g++14 which is compiled with --stack=67108864 what means there is 64MB limit on stack.

Did you submitted on Visual C++? It seem to there are very strict stack limit on VC++, but isn,t on g++.

Same here... But, sadly, I didn't pass D during contest even with FastIO and some optimizations.

Code that got TLE on RCC got AC easily on CF in about 400 ms. Most frustrating is wasting more than one hour trying to make it fit in time limit.

Great, after learning that RCC has stack limit I also learned that I was constantly getting WA in E on test #2 because RCC is judged on Windows that has fu^&*# up rand() :/.

There was a stack limit, however a pretty big one as for existing stack limits — 64MB. I submitted on CF code that got RTE on RCC and it got AC using 96MB.

Hmm, I was doing recursive DFS in D, so it probably would have failed if there was a stack limit.

Something else that I didn't like though was getting TLE in D, which I fixed using FastIO :)

The problem is exactly the same, indeed.

I am sorry about that, we made it from scratch. None of our writers or testers noted that they saw it before, although some of them, as I see now, indeed did participate in the corresponding round.

There are tons of problems in the internet, so simple problems are almost certainly similar to some former ones. Of course, if we see exactly the same problem, we always replace one. We just didn't notice that this time.

Hope it didn't affect most participants.

Is this 21st century? Can somebody confirm? I am not sure because I have just participated in a contest with a stack limit. Come on guys, it's pathetic.

Created or updated the text

Hi, can you write your email in a personal?

I am not able to submit solutions as "You are not registered to the round. So you can not send solutions.". Is there anyway to register after the round has started?

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?