I haven't received anything related to t-shirt, although I'm in top 512. Is it normal?

It didn't work for me either even though I was logged in.

Thanks a lot for the effort :) I think it would be great if you can add interesting sample problems for each topic and also add some more advanced techniques and algorithms. By the way, I would love to donate and to translate it into Turkish.

My solution has O(N * 2^N) time complexity and O(2^N) space complexity.

Is it just me or are this year's COCI rounds significantly harder than the last year's?

I agree with you. I think D is much easier than C. Simple solutions aren't necessarily easy.

My O(nC²) solution with memoization got TLE on one of the sample test cases; therefore, I had to rewrite it in a bottom-up approach. I was very surprised when I saw O(nC³) solutions could pass. Maybe this is the reason why they wanted to extend the time limit a bit (which ultimately caused asymptotically slow solutions to pass).

In no particular order:

1. jcvb
2. yutaka1999
3. ko_osaga
4. waterfalls
5. V--o_o--V
6. LiTi
7. mustrumr
8. SpyCheese
9. Radewoosh
10. brandnewnode

UPD: Sorry for listing 10 people instead of 5. I just couldn't resist.

Using that approximation you need to find a new function f that gives the partial sum. After that you need to find the inverse of it so that you can find the x such that f(x) = randomly selected number.

Thank you for great explanation!

Btw, this is the updated version, do you think it is correct now?

Oops. I didn't realize that. Thanks!

To fix the distribution I need to find the number of ways it can be done for each case, right? Then, it will become O(n²).

I think this should work. It's O(n).

UPD: Now that I looked, it's the same idea with what Zlobober said.

No. You need to write your solution to an external file.

You just send the source code.

Where did you provide your email? I can't remember if I did that.

Kotlin is too common to be fair. People who are familiar with the language (or even with Java) has a clear advantage.

I haven't received it yet either.

What does it say in the Russian version?

Everybody makes mistakes :P

Thank you very much.

It's because of the compiler optimization. I ran the code on my computer. It took 2.1 seconds to run when compiled without -02 flag, but it took 0.3 seconds with the flag.

Same :/

When will the final standings (three rounds combined) be released?

UPD: It's out!

My solution gets Idleness Limit Exceeded, even though I flush the buffer. Where do you think the problem is?

18300219

UPD: I've found the error! I should've printed one query per line.

There is an O(X + Y + TlogMOD) solution for the 6th problem.

Related paper

You need to binary search the answer for each query. To speed it up, you need to do these binary searches simultaneously.

My Code

Complexity: O(mlogm + logm(qlogq + nlog²n + m + qlogn))

It's not about how civilized it is.

convex hull trick, maybe?

The interesting thing is when I searched "da vinci" on OEIS, only fibonacci thing came up. Now it shows the other one. Maybe I didn't wait enough for all search results to come :/

When registering during the extra time a participant is automatically assigned to a random room (among suitable for its role).

Unfortunately, it's. But as far as I know, Syria isn't any different.

It's one of 2 university entrance exams in Turkey. (The other is LYS)

It was a really nice problemset. Thanks!

We iterate the array. For ith index we will find the best position j, left to the i (it could be right instead of left, but we will compute the right in another iteration), which maximizes (this equals to change of the value of the array when we move jth element to ith position).

As I said before we do the same thing (almost the same thing, equations are little different of course) for right. Then, the answer is the value of the original array + max(0, max of all changes).

To find the best j for a particular i, we need to fiddle with the equations a little and represent every element as a linear line:

ps[0] =  - ar[0]

ps[i] = ps[i - 1] - ar[i]

max_{1 ≤ j < i}{ps[i] - ps[j] - ar[j] * j + ar[j] * i} = ps[i] + max_{1 ≤ j < i}{( - ps[j] - ar[j] * j) + ar[j] * i}

Now we can represent ith element as a linear line. ith line equals to y = ar[i] * x + ( - ps[i] - ar[i] * i).

We first add the line 1. We then start iterating from index 2. When we're done with i (computed the result for it), we add the line i to our structure.

(To find the result for that position) When we're at a new position, let's again call it as i, we find the line which has the highest value for x = i. We also need to increase this value by ps[i].

To find the best line, we can use the convex hull trick on a segment tree, since slopes aren't non-decreasing like in the case of traditional convex hull trick.

Time complexity: O(NlogN)

Can someone explain the solution of the fifth problem, Combining Rice Balls?

Something like 10^12 10^12. My error was because of integer overflow.

Please read the blog before commenting.

The problem is similar to the ones that are being solved by VeeRoute daily. As the competition format is very different from a standard Codeforces round, the contest will be unrated.

What you say is a really bad way of learning.

Generators and validators are different things. How can you be so sure even when their source codes are different by the way?

Can you please translate it? There is a translation below but it's not better than a google-translate translation.

I commented the same thing twice, sorry.

Since n ≤ 10⁴, a normal dfs do just fine. I got full score.

I did dfs.

related

Auto comment: topic has been updated by determinism (previous revision, new revision, compare).

I think that two ways you mention are really good and can be used together (similar to the current system for non-interactive problems). I'm not sure about the complexity of implementation though (especially manually interacting, automated interactor stuff is something already implemented I think).

N can be up to 200. How is that wiki enough? Am I missing something?

UPD: There is a link to a related paper on that wiki page. I wrote this too early I guess.

There is another section called magic.

Here's a sentence that I never thought I would say it: "Finally, I can be a nutella!"

Oops, I didn't realize it. Thank you!

What's the solution of High Card Low Card (platinum)?

" The old bronze, silver, and gold divisions will be scaled down in difficulty accordingly, so that bronze contests will provide an easier entry-level experience for our new competitors (we've received overwhelming feedback requesting this) and so it will be less of a discontinuity for students to compete in higher divisions after promotion. Platinum-level contests will be roughly comparable to the difficulty level of prior-year gold contests. "

Aren't there infinitely many solutions if we don't assume it?

I think it is compatible because f(n, k - 1) + f(n - k, k) = f(n - k, k) + f(n - k + 1, k - 1) + ... + f(n - 1, 1).

For example when k = 3:

Its time complexity is O(K⁶logN).

Wouldn't you get a O(NK) solution with that?

By the way, I already thought of an O(NK) solution:

It's one of the most detailed editorials I have seen. Awesome!

Problemset was also really good. Congratulations!

What's the solution of Div1 B?

For problem D, I assumed that m = (6x + n³ - n) / (3n² + 3n) is decreasing because data seemed like it. So n's upper bound is when . When 6x gets bigger n gets bigger. So n's upper bound is when 2n³ + 3n² - n = 6 * 10¹⁸ therefore n ≤ 1442249. Fortunately, this got accepted. But after the exam I looked at some m - n graphs for various x values and realized that this is not monotonically decreasing, instead it first goes down, and after n = m it goes up again. I'm wondering if there's any integer (n, m) pairs where n is bigger than the first intersection point (a.k.a my pseudo upper bound). If not, how to prove it?

Graph of the first test case of the problem:

UPD: Nevermind me :D I don't know how I couldn't see n is always bigger than m after intersection (even though m starts to increase again, it increases more slowly compared to n) by looking at that graph.

Mine is still at system testing too.

Cartoon for idiots?

I loved Sponge Bob when I was a kid.

Mine is same.

He performed really well, that's why.

Yes. Probably because magnets are rectangle in real-life.

Can you please explain in a detailed way what modeled solution was and why it's wrong? Because I was really sure about my solution for Div1A.

I think problem Div1A is really nice.

Did you use any data structure?

I can't remember the problem, but once I wrote it without ranks, and I got TLE. When I added ranks to it, it passed. That's why I don't think it's always a good idea.

It didn't get WA, but it's because of my luck. If they can touch, this solution is wrong.

Didn't problem say they can't touch?

I didn't know that. Sorry.

You used to be purple :D

It's not funny when it's told to you, isn't it?

I think it's not that neat, but let me share my solution:

I first check if their projections on x axis intersect. If not, then they don't block each other. Then I think them as lines instead of line segments and find their equations. Then I choose the bigger one of left ends of segments as common x value that both have y values. I plug that common x into their equations. The line segment with the less value is the one which blocks the other, so we should remove it first. The only tricky situation is when a line segment doesn't have a slope. In that case, instead of using equation, we can use any value between y1 and y2 of that line segment.

My code

What do you think is the problem of my solution for SAVEZ?

It gets WA on 1C.

Don't be silly. Hashing is one of the most fundamental and most flexible techniques; that's why, it's as "real" as it gets.

Heavy Light Decomposition is what you're looking for:

• http://wcipeg.com/wiki/Heavy-light_decomposition
• http://blog.anudeep2011.com/heavy-light-decomposition/

Btw, did you create a new account to ask a question? If so, why?

Thank you for your effort. It's an amazing extension.

After system test, the extension was showing that I will get -8, but instead I got +6. I think there is difference between your and Codeforces' algorithm (unless some people was banned from leaderboard because of cheating after systest; I'm not sure about that)

What are the upper bounds of number of all steps and number of steps that we need to compute divisors?

It depends on the person. I think that the new system is more motivating.

Exactly! I feel like the same way. I also think that in the new system it's less probable for someone to get lucky and have a higher rating than their actual skill or vice versa.

Thank you for informing :) I didn't know that.

No, it's like pretests. You need to click on "run system test" button.

UPD: I was wrong. As riadwaw said, it's not like pretests. You'll get positive score anyway.

Even though it's confusing, I think it's a nice feature because it lets users to measure themselves in terms of speed.

MikeMirzayanov explained it.

" If your solution can not deal with the train of size 1, your solution may not good enough~~ "

Can someone explain the solution of A? I've looked at the solution slide, but I didn't understand it (except the first insight; I've already found it).

Then you (maybe without realizing) assumed that there is always valid p2 and p3 whose sum equals to n — p1. Problem guarantees there is a solution. It doesn't guarantee there is a valid (p2, p3) pair; that's why, you need to know Goldbach's conjecture.

What's the complexity of finding the closest prime number?

How to solve D?

Thank you really much :)

I don't know if it's only me, but the link doesn't work.

Won't new formulas be applied to old contests?

I think calling it "square root decomposition on queries" is a better choice, since not specifying it implies that decomposition happens on the array itself. (Of course, we store queries on another array but I mean the main array.)

Why do you suggest to watch to it there? They're basically the same.

That's totally logical. Thanks for answering.

Since it's IOI 2013 syllabus, it just means that the intended solutions won't use them. There might be conceptually easier solutions using them, that's why I think learning those algorithms would be a better idea.

Thanks for info! What's your suggestion? Which one would be better to learn in terms of easiness to write etc.?

Is learning one of balanced BSTs (in your case treap) enough to solve problems that can be solved with BBSTs? Or do some problems need some specific BBSTs?

What are your priorities while studying IOI? (I'm asking this since you said you have higher priorities of training.)

Thanks for nice tip.

Btw, how do you use binary search for B part?

Auto comment: topic has been updated by determinism (previous revision, new revision, compare).