Lol what? His last round was great (especially D) and had only one math-related problem. He writes hard rounds but it doesn't mean they're bad contests.

lol

You missed just a bit. Mine was A :)

for you nothing

What do you mean? At least 554 contests in a row!

after this there will be most probably a div.3 round

Your segment tree works wrong. In your code: int q2=query(node*2+1,mid+1,end,l,r); Correct: int q2=query(node*2+2,mid+1,end,l,r);

No.

At least, in the VK Cup series, no contestants today know about those problems (as those who do know has participated before in the official round).

For other series (like parallel Olympiad or something), disciplines are kept through words. Not a really effective way in theory, but it's worked times before.

For example in the announcements of Codeforces Round #500 (based on EJOI — European Junior Olympiad in Informatics):

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of EJOI (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

@Mahmoud..Adel

Совет — если хочешь зашутить в комментах, чтобы твою шутку оценили и при этом в посте есть англ перевод, пиши на англ

The Joke

I could not get it faster than n**5. Can you share your insight for n**3, because i think that should pass the time limit.

I think n^3 with some early break optimization might be fast enough.

maybe need some optimization, my O(n ^ 3) solution got TLE

n^3 / 64 fits in the time limit. Can you imagine a solution with bitsets?

My N^3 passed the pretests: 41846474. I think I tested it with the worst possible input (no interval is possible), and it used 0.085 seconds of time.

My solution was the same as explained by Len.

EDIT: AC. Another factor that maybe impacts this is that I precalculated the GCD's.

Using STL bitset, the O(n³) DP can be optimized to .

http://codeforces.me/contest/1025/submission/41844612

Brute... With some optimizations. Consider the array to be inorder traversal of BST. Construct tree using recursion. If there is atleast one valid tree, then "Yes". Also... Use Top Down DP.

Just find all prime factors of a[1] and b[1], and check if some of them can divide everything.

I solved it using dp with state of 3 variables l, r, i (l and r are the interval limts I am working on from the sorted array, and i is the chosen root of the sub-tree represented by this interval).

Not sure if it will pass system tests though.

I tried to use flows, but I think it won't pass too. There are cases where my program will fail.

1 1000000007 1000000007

I hacked succesfully with

2
17 18
3 3
ANS = 3

and

3
1890 1890
5 7
5 5
ANS = 5

2 1000000007 1234567891 1234567891 1000000007

150000 pairs of 1999999973 and 1999999973. It gives TLE because people take gcd of all a*b instead of lcm(a,b)

you may try this: 2 2000006 3000099 5000015 7000231

answer should be either 1000003 or 1000033

My assumption was that it doesn't make sense to do more than one time the operation. Hence, check the length of the pattern from beginning as l1 and length of pattern from end as l2 such that s[0] and s[n-1] are not equal then answer will be max(answer without any operation, l1+l2)

split it in max len correct zebras. mark from 1 to n. whenever you split it between any two zebras, the neighbours stay the same, except for the first and last zebras — the could become neighbours so the answer is either the longest correct zebra or the sum of 1st and last zebra if it's possible

Yes.

I did that but i dont have any aidea why that works haha

I tried the same but I tried that the free cells were on the border... I think I have a bug in my implementation though

The problems A-D were pretty nice, the issues in my opinion were really bad pretests, horrible E and silly bounds in D (straight n^3 passes with precalculated gcd's).

So in summary, bad round but not as bad as for example Codeforces Round 497 (Div. 1) where 4/5'ths of div1 participants only solved Div1A (and Div1A was really easy).

That's a heavy assumption to make (that zebra cannot have length 1), and should have been something you asked during the contest. It doesn't say anywhere that minimum length should be 2, so you should assume that the minimum length is 1.

Can you explain?

F is similar to the JOI problem: solution

Think of every pair of non-intersecting triangles (they have points a[0], a[1], a[2] and b[0], b[1], b[2]).

Now note that there are only two lines passing through points a[x] and b[y] for each 0 <= x, y < 3, such that all the points of one triangle will lie to the left of the line (one point will line on the line), and all the points of the other triangle lie to the right of the line (one point will lie on the line).

How can we solve the problem? We can draw a line from point p[i] to point p[j] for each pair of points. Points p[i] and p[j] become vertices of different triangles. Now we should find the rest of the points of our triangles. For the first triangle, we choose any two points to left of the line, for the second triangle, we choose any two points to the right of the line.

The statement above helps us to understand that, using this algorithm, we add each valid pair of triangles exactly two times.

Now we should find a way to find the number of points to the left of each line. First, sort all the lines by their angle. Suppose we now consider the line l[i] = A[i]*x + B[i]*y + C[i]. Denote pp(i, j) = A[i]*p[j].x + B[i]*p[j].y + C. For each line l[i], we should keep the points sorted by its pp(i, j) (p[a] must be earlier than p[b] if pp(i, a) < pp(i, b). If we can maintain this, we can say number of points which are to the left of l[i]: it's all the points p[j] which have pp(i, j) < 0. Don't forget that the points are sorted by pp(i, j), so, to answer this, we can find the position of first point pp(i, j) >= 0 using binary search and so we find the answer.

Now we should learn to maintain the array of points in the sorted order when we move to another line. Notice that, when line changes, only some two points swap (those two that lied on this line). It's possible beacuse the lines are sorted by angle.

So, we get O(N^2 * logN) solution.

How to solve B?

Did C have any corner cases? (except maybe that the answer is at most n)

These authors, they played with us man i am telling you.

Btw, Nice work on D.

1. Define the constraints such that the unoptimised obvious solution won't pass.

2. Make weak pretests such that unproven incorrect solution passes.

I mean, this is some fun game. I like it, you sleazy mofos

I think GreenGrape has become a PURPLE one.

You can send script that generates test.

You can submit the generator itself instead of input.

Maybe solving F would be a better choice.

That is close to what I did:

1. Move every cube to a unique row (n * n moves)
2. Move every cube to a unique column s.t. they are sorted by their final columns (n * n moves)
3. Move every cube to the correct row (n * n moves)
4. Move every cube to the correct column (n * n moves)

I actually think that the solution is really nice, although many people used randomized solutions, which makes me even more sad that I couldn't code it up in time. Anyway, here is my code that passes, and I would like to believe that it is pretty readable:

link

My guessing:

A — 505 problem C

B — 505 problem D

C — 504 problem E

D — 504 problem F

E — 505 problem F

F — 505 problem G

G — 504 problem G

504 EFG = VK Cup CDG

505 CEFG = VK Cup ABEF

Probably wanted to exclude O(n⁴).

I got AC with precalculated GCD, so you're correct :Dd 41846474

My n^3 passed (recursive dp). I used all boolean arrays (except for one long long vector to take the inputs).

So, is 1 second enough for a complexity of 5e8 or even 1e9 in CF? (D was a little more than 3e8 and my submission took only 62 ms)