I_love_Tanya_Romanova changed his bio on Quora to "Red on Codeforces" from "Winner of SEERC, ACM ICPC finalist" :D

In which revolution?!

This is every contestant's first contest in some way or the other(First contest with Updated rules).

But my first **_palindrome _** contest

A lot of reds have been saying its much easier to become red on CF, than being red on topcoder. MikeMirzayanov had a fitting reply to that, and most reds lost the color. So sad.

Could luck X-D

sadly , yes :'(

Seems like the round is delayed for 15 minutes

:( Again delayed 15 min!!!

You should never expect anything on time.

It will be announced shortly before the contest...

No, there was only 6950 on Bayan Thanks-Round (#320).

In fact, in 15 minutes before round we felt like:

too many people are eager to get back their colors!!

I think we must find all flat parts in region [1,2*n]. Then do LIS in n^2 for each point and see if LIS upto this point+(t-2)*flatpart of this point is the highest

My idea(which didn't pass pretest 2) was to split the problem into 2 cases:

If T<=250, then just run LIS algorithm and get the answer.

Otherwise, run the LIS algo on the first n * 250 numbers and get the sequence. Then pick some number close to the end(but not quite at the end): this is your "capped" value. You then treat the other T-250 periods as if the only numbers we selected in them were occurrences of this "capped" value. Then on the last period you can select higher numbers or whatever. This is probably wrong though :P

Let us define a graph with 300 nodes with weight of edge (i, j) denoting the length of lis starting with beginning value (not the index) being i and ending value being j.

Now, we want to find a maximum weight walk in the graph of length T. This can be done by matrix exponentiation.

If T <= 5000, then find the LIS for the A x T array by nlog(n).
Else, find the answer for s1 = A x 5000 and for s2 = A x 5001, then X = s2 — s1.
Result is s1 + (T — 5000) * X;
13386622

i hacked using

4

2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4

My first submission produced wrong answer for this case:

4

10 5 2 2 5 5 1 1 2 1 4 4 2 1 4 4

I think they used similar one for hacking.

Maybe something like this:

4 10

1 1 1 2

answer 31

rip me

I did the same.. and I think it is correct

Did the same, but got TLE on 7 pretest.

Could you tell some more on your implementation?

what if the top number repeats ,like 6 6 4 2. Hope you handled that.

That's what I did too, and I'm pretty sure it's correct. A not-very-well-explained proof: Consider the situation: You have a partial solution that is certain, and you need to sort the remaining numbers. If you don't put the biggest one on the diagonal in the table (i.e. as one of the numbers we're looking for), and pick some smaller one for all the cells there. Then you have to put the big number somewhere else. But the number on the diagonal in the same row/col as the biggest number has to be a multiple of that -> contradiction.

It's correct. Notice that if you make the GCD table from the sorted array A, then the maximum element of (full table minus a square touching the bottom right corner) is the last diagonal element.

I'ts definitely correct. I have most of an inductive proof on my scrap paper.

I did precisely this with C++ multisets as my underlying data structure. Got TLE. I constructed the worst case on my computer and it runs in ~0.1 seconds. No clue what the problem is.

In first one we can make two arrays : one for horizontal and one for vertical and initialize them to zero. Then while taking input we can check if both are zero then we store the position at which input comes. After taking all input we print the stored values.

Div1-A

Sort the array. It's obvious that the biggest number in array is actually from answer (gcd(A, A) = A, gcd(A, B) <= min(A, B)). So you take the biggest number and store in some Ans array. Next biggest number in array (let's call it B) is actually the second number from answer because gcd(A, B) <= B and gcd(B, B) = B. So now you know that it's number from answer, you erase it from array and add to the answer. Now last move, you need to erase gcd(A, B) and gcd(B, A) from the array. Finally, at every step you take the biggest number, add it to the answer, erase it from the array and erase each gcd with other numbers in answer two times. That's all.

My solution 13368755

Div1-B

It's kinda obvious that there will be some "plato" in answer subsequence. There will be one number (maybe on several positions) that will be taken in all copies of initial array in the "middle" of answer. So I checked if n * T is bigger than 10000 and if it is than I take Tnew copies of array such that n * Tnew <  = 10000. Now you can compute the length of the longest subsequence with the dummy quadratic algorithm and than you take two neighbor copies of array in the middle of answer. You take the biggest length of subsequence to them and say that difference between these lengths will be constant between each neighbor pair of arrays in the middle of the answer. So now you just add that difference multiplied to T - Tnew to the computed answer on Tnew copies.

If n * T is less than 10000 you can use dummy algorithm to compute answer.

My solution 13373614

The input can be in any order.

I thought this, but then I read that ELEMENTS CAN BE INPUTTED IN ANY ORDER.

You're right, answer is diagonal elements but the thing is elements in the input were in an arbitrary order

Graph is not given as it.. It is given in arbitrary order

and gcd(x,y)<=min(x,y)

You are still thinking in Java, everything in C++ is pass by value unless you explicitly pass a pointer/reference.

Your st is the instance of multiset<...> template class, so when you pass it without a reference (&), you pass the whole structure. It applies to all STL containers, not only multiset so don't forget to pass the reference!

Because when you declare parameter without a refrence you are saying "Please copy the whole stuff", which can be VERY slow.

When you are passing by reference you just passing an pointer to the object, so nothing should be copied.

Yes, we have a solution in Java that works in 2.2 sec.

If you see something like this, write us a message and we'll ignore one of those two submissions. We have a system that detects double-submissions with zero diff, but sometimes it doesn't work properly :(

I ignored the second of those two submissions.

I solve in O(300 * n²)

I solved it in O(min(10⁸, (nt)²)) 13373614

I solved it in O(n^2*logn)

I had the same complexity. I observed that for a LIS,I need maximum n periodic arrays where an element changes(from x to y ,y>x) ,the others contain only an element. But I fixed the number of periodic arrays needed,So I have (n +n^2+..+n*n)*log.

I didn't see that the case with n*n(or t if n>t) includes all of the others,so if there is an answer when I need just x<n arrays,it will include also that :P

It looks almost the same as mine... Maybe the timelimit is too tight. (Or the problem setter has a better solution.)

Edit: dreamoon_love_AA is right. I used n/len gcd instead.

I think you use too many time of function __gcd() in line 34. So the time complexity of your program is O(nlog²n).

maybe, because rating updating

Editorial is already out:

http://codeforces.net/blog/entry/20692

He has written:

 vertical = vector<bool> (n, false);
 horizontal = vector<bool> (n, false);

If you are talking about +-1 error in your solution than it is actually rare to crash because of this. It's like chances that A[n] will cause an Runtime error are very small (but they exist) and it's often better to leave the solution as it is.

Vector [] operator doesn't check if the index is out of bounds. Using it with index outside the bounds is undefined behavior. Vectors may also allocate more memory than necessary so that new elements may be added without reallocation.

You aren't going very far our of the bounds anyway.

what is the feel seeing russian as foreign language?

Yeah may be. Some submissions got skipped!

Also only -91 (so cyan) for last place (with -600 points) seems weird. My natural instinct would've said gray, maybe low green.

Edit: I guess that happened before too, looking at http://codeforces.net/profile/worse my bad :P (though worse was 2k, and this was 4.7, so maybe it's not actually the same)