hi neko_nyaa

could you please tell us what you do to improve your skills in competitive programming and get this level (rating) in only one year ? please don't just say practice . tell us what kind and type and of practice

Heck, how far have you been for a year. I'm pretty much jealous if you ask. :D

I think got some trouble in recent rounds. With many small mistakes and feel very tired then coding. Maybe I should rest for a while? Or are there any way to improve skills to prevent such small mistakes?

I hope I can promote fastly like you,you are brilliant！

Wow! Didn't expect that! Very very interesting! Perhaps you could tell us a bit more about that? I'm sure everyone's eager to know!

LOL

Perhaps they noticed majk's comment. It got quite a bit of upvotes.

Initially we wanted to award $100 to the top 25 and $50 to the following 50, but the contributions in the campaign weren't enough so we made it the following 46.

I want to become expert this year as well :)

What is good in not being hacked?) It's better to be hacked with a chance to resolve then to fail the system testing

And maybe lose the chance to win a prize :)

Thanks, fixed.

http://mirror.codeforces.com/blog/entry/61450?#comment-454399

Me,too. hope so!

.

Does the exam last 10 months?

Good luck!

We tried hide reason why restriction in G is unusual

No.

lol, I was wondering why it was taking me so long to solve

xd indeed

the drawback from different coordinators

Hi, so to me seems like a notorious coincidence.

To be serious, it's a pity nobody from authors' team is regularly solving Div. 3 contests. Probably next time we would check several previous contests to avoid such inconvenient situations. Sorry for that.

I went with that method as well. Unfortunately, problem C wasn't enough. There was/is some point important to note, without which it will throw WA as it did with my case.

I think it is something like this:
3
0 1 3 2
1 0 2 3
4 4 5 5

What's wrong with just doing it in n log n? It's simple and works.

O(n) solution: precalculate intersections of all prefixes/suffixes of rectangles. If the intersection doesn't actually exist, then you have a rectangle with a low x/y higher than its high x/y, which you can easily check for. You can then brute force all possible n-1 rectangle combinations.

42180099

I don't know why you're using nlogn or randomization. Isn't it enough to just find intersection of first i rect and last n-i-1 rect and see if it's not empty

It's just 'count of them + 1', because all the numbers are different.

if they're in between the clamps (confirmed buy/sell offers), multiply by the number of adds + 1

Thanks all.

Observe that if there are no "ACCEPTS" then answer is simply #("ADD") + 1 since you can partition the prices at any point. Also note that "ACCEPT" only restricts the segment where you can partition. This should be easy to implement. Take care of cases where once you "ACCEPT" your value you know that minimum and maximum of your restricted segment is in which direction.

Find any point where val[i] < val[i+1]. Set ans[i+1] = val[i+1]. Then, for j = i, i-1, ..., i+2, set ans[j] = ans[j+1] + val[j]. Then, in order to ensure the value is large enough, if ans[j] < 1e9, set ans[j] = ans[j] + 1e9 * ans[j+1].

It's easy to verify that this works. 42175007

Special cases are val[i] = val[j] != 0 for all i && j, in which case you answer NO, and val[i] = 0 for all i, in which case you just print a bunch of 1's.

If all elements of b equal, then there are two cases: b₀ = 0 and b₀ ≠ 0. b₀ = 0 is trivial. For b₀ ≠ 0, it can be proved that answer does not exist.

Otherwise, find any position k in b such that b_k > b_k - 1. Assign a_k = b_k. Then, construct the array a backward from k - 1 to k + 1. For position i, we need to find a_i such that:

• a_i = x * a_i + 1 + b_i with x can be any non-negative integer.

• a_i > b_i - 1.

Since a_k + 1 > b_k, it followed that .

Maybe, for the constructive problems, the admins should implement the system specifically for those to show the checker logs only (Yup, that means the checker should only answer if the outputted answer suits the criteria and not give any clues to the model solution).

I think we should stop showing answers for pretests during the contest, just show your output and checker log.

Yeah we've also noticed this during the contest and for new submissions only the answer same as in the statements (with no hints) is shown. I think it is sometimes useful to show correct answer and checker comment, we just forgot to check that in the system it shows the same answer as in the statements.

read maximal intersection 506div.3

We need to find any point which lies in n-1 rectangles out of the given n rectangles. There can now be n cases. The first case will be considering all rectangles except 1, second case will be all rectangles except 2 and so on until index n. We can now create two arrays. First array will store the intersection area start and end of all the rectangles before an index. Second array will store the intersection area start and end of all the rectangles after that index. This can be done by: arr1[1]={start[1],end[1]}; for i=2:n arr1[i]=intersection(arr1[i-1], start[i], end[i]); /// Intersection returns both start and end area // of intersection region. arr2[i]={start[n], end[n]}; for i=n-1:1 arr2[i]=intersection(arr2[i+1], start[i], end[i]);

We can now for all rectangles check whether rectangles on left and right intersect or not.

http://mirror.codeforces.com/blog/entry/61450?#comment-454356

especially capitals

I think it should hide jury's answer and showing contestant's output only.

See my answer here. It was just a bug that an answer different from one in the statements is shown.

1) check your computer's power 2) try restarting

Looks like in some compilers (like ideone) sort doesn't work correctly in your case for some reason...

Sorry, of course sort always work correctly...

Maybe I've found the problem. It's with idx: it's "-1" on Codeforces and "4" on ideone before the last erase. I believe this happens because in the second for(i = 1; i < n; i++) you take both p2[i-1].first and p2[i+1].first.

Then p2[n].first and undefined behaviour. Ideone say !f(...p1[n].first, p2[n].first, ...) is true and Codeforces say it's false.

Again? (like he did something before?)

Can you clarify yourself?

I Can't see how he cheated, can you explain more?

Yeah.The issue is addressed by KAN

You can do preprocessing in O(n·7·2⁷) and then answer queries in O(7).

The preprocessing should give you all the information about answers for all intervals. So, for every left end L of an interval, and every possible answer a (0 ≤ a ≤ 14), find minimum possible R such that [L, R] has answer a. Then you don't need trees or binary searches.

How is it weak? Maximum is 1129, and your least sum is 1200

It is right!

The test data is not weak. It's just your solution that is correct :-)

I don't think it's strange.

the problem itself is weak, not the test data

Wow never expected my solution to be posted by others for whatever reason

It is my honor

It's more of a joke rather than an actual problem xD. Basic idea is if 0 ≤ a < b, so with a little bit of care we can make work something like a_i = a_i + 1 + b_i for most values of i.

If they're all equal, then it's impossible (unless they are all 0, in which case a constant sequence works).

Otherwise, find some i where b[i]>b[i-1]. Set a[i]=b[i], and then work backwards — set a[j]=b[j]+ka[j+1], for the smallest k that makes this expression bigger than b[j-1]. Make sure you're careful with the wraparound, and that's all.

zeliboba answered here that yes.

Let O be the origin. For each query A(x,y) we want to calculate a) number of points which lie on line OA and b) number of pair of points which are symmetrical with respect to OA. The first one is easy. To calculate the second, two points B and C are symmetrical to OA iff OB = OC and AB = AC. If the first condition is already satisfied, let D be the (unique) point such that OBDC is a rhombus, then AB = AC iff O, A, D is collinear.

After that we only care about pairs of points that have the same distance to O. For each pair, we add the corresponding D, then for each query A we want to know the number of points D which lie on OA (which is easy). The whole problem can solved just by bruting those points, as the number of integer solutions for x*x + y*y = r is not that large (based on some results which I didn't remember).