I'm afraid that my laptop chagre is not enough for 4 hours of competition.

==============

Я боюсь, моему ноутбуку не хватит заряда на 4 часа соревнований.

We postponed the start of the CS Academy round by 15 minutes.

I believe this means that the round will be rated differently. Not sure on the specifics though.

This word is a translation of "внеочередной" and is used in the literal sense of it — "out of regular order", "specially arranged" (as you can see it's published the day before it takes place), as opposed to the more common meaning, "unusually good".

This translation of the word is bad but I can't think of a better one.

Can you read?

Would be interesting to see the dependency between rating and not loving geometry. I'm pretty sure that yellow+ people don't care, while all the greens hate it.

I just wanted to solve the tasks of the last year, so decided to add them to polygon to test. And then decided to add to the gym also for the others. But I got bored and didn't uploaded the second day :)

I found the tests on the official site, so you can find them and upload to polygon, if you want.

Сказал Алмат :D

contests*

you can find them after contest. there will be a lot of solutions)

Did you write dp[i][money on card] or what?

priority queue on cost.

DSU

Prepare a set S comprise of number from k+1 to k+n. Iterate over the flights in decrease order of their cost. For each flight, let's call the initial departure time i, find the first number in the set S that is greater or equal to i+k, erase that number from the set.

Sort the flights by their price in a descending order, then for each flight you have to do one of those things

1-the flight is already fine, no need to delay it(i > k) 2-the flight is bad, so you need to find the first j where j > k && j <= k also j must be minimum and set the flight to that time(you have to keep in mind that there is no other flight in the time j) and add the cost

I used intervals tree for find first free place, starting with min(i,k)

Prefix/suffix minimum sweep line

Sort all flights by their departure day. Now iterate over the last day that everyone must be in city 0 (from k to 1e6). We can see that the number flights we can use to go home will only decrease while the flights we can use to go to Metropolis increase. Now just keep minimum for every person (to go home and to go to Metropolis).

Well I calculated number of points in all 9 directions of every rectangle, so my solution is 9 * NlogN, if you accept that as NlogN :D

Yes i did with scan line in the O(6*n*logn)

Yes. You can sweep from left to right and do all the queries when appropriate using a binary index tree to query the appropriate 8 regions.

Can you explain your dp solution?

Too many greedy!

Can you explain how?

Well, i passed pretests with O(nlognlogn) solution, so there may be a problem in your implemention

same reaction when main tests and hacks are running as well.

I'd recommend using the -Wshadow compiler option because of this. It saved my life quite a few times.

Yes, but with priority_queue is easier.

I solved it with segment tree and my code is 120 lines long. I see other people submissions that are <=50 lines and I feel stupid :/

i used a greedy approach with a set

I used MergeSort + BinarySearch but couldn't finish the code before the contest .

I solved it using a set. First, insert all numbers from k + 1 to k + n into the set. Sort the given elements by the decreasing order of C, call them a[i].c, keeping their initial positions, call their initial positions id. Then iterate through the sorted array, and find lower_bound of the index, call it idx, and remove it from the set. Add ans = ans + (idx — a[i].id)* a[i].c.

I think so.

Let's do binary search on answer. It is clear that we will spend bonuses on last 1000s and last 2000s (it can be not a suffix, for example 2000 2000 ... 2000 (9 times) 1000 2000 1000, it is optimal to spend bonuses on two 1000 only). But if we omit two 1000s or take two 1000s after omitting 2000 (going from right to left) we can change it (two 1000 for one 2000, take the variant which is more on the right). So we have only O(1) possible variants, each of them can be checked in O(n) time.

You can show that there is an optimal solution that pays for the first k using cash, and the last n-k using rewards card, except for at most one exception which costs 1000.

cout << 1 << ' ' << min(n - k, 2 * k);

More clearly...You can consider a chosen one's left and right are all available and actually good. So you can divide the grids to blocks which contains 3 grids each(Sorry for my bad description) And when k>floor(n/3) it can be count by n-k because all the empty grid are next to a chosen one.

It can be done offline using sweep line + Fenwick trees.

Mine is with simple wavelet tree. It runs fast enough.

I think my code is right now. How can I submit my code after the contest? There is no button appearing.

Yes, i got AC with merge sort tree

I solved it offline using SQRT decomposition + Fenwick trees. Managed to squeeze it into TL.

Can be easily done by greedy + vector pair!! I got WA cz of missing to typecast answer to long long :(

I used persistent segment tree.

Sympathize with you

Molo5ya

Record the boundary range with a next array

This is my solution and might be wrong

1-Sort the A[] in descending order of cost (store it as pair<cost,time of flight>)

2-Make a set and insert all possible values which is from (k + 1 -> k + n)

3-Now loop over the A[] and do this for each value

binary search on the lower bound for the (time of flight) then before removing it cost += (newTime of Flight — oldTime) * A[i].cost;

4-Remove the new time of flight from the set

The flight with huge cost, the place wont change or change minimally..

priority_queue + save index which have the same cost

Greedily assign the most expensive flight to the earliest time you can.

How do you find this earliest time? My approach was to keep all indices from k+1 to k+n in a set. Then, when an index is assigned, remove it from the set. To find the earliest index, use set::lower_bound.

You are probably doing some loop till n instead of till m. Had the same retarded bug and got WA on the same test as you

First, you can compute the Minkowski sum of the velocity vectors. This gives a convex polygon with 2k sides that describes achievable speeds. Then, to compute the answer for a exhibition i, center the polygon on the exhibition, scale it depending on the number of days t_i, and count the number of factories inside it.

To compute the number of factories inside it, split the polygon into 2k triangles, and sum the results for each triangle. The hard part is then to compute the number of points inside a triangle.

Actually, there are only 2k different kinds of triangles if we ignore translation and scaling, and for a single kind of triangle, we can compute all values in O(n log n).

I shouldn't be the one posting this but the problemsetters :D

I just wanted to know why it doesn't happen. Why are you making fun of it ?

You're missing the case of buying first k plus the first "1000" after them.

Try this one?

13
2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 1000 1000

It should returns 21900 by buying first ten of 2000 and the first 1000 (12-th position).

Accepted now, thank you all!

Page of hacks: http://codeforces.me/contest/854/hacks. Just find yourself by nickname

Your hack-case: 15 6. You write 1 12, right: 1 9

I learned that in an official contest :') , AFAIK in worst case it can run in O(N^2)

http://en.cppreference.com/w/cpp/algorithm/lower_bound

The number of comparisons performed is logarithmic in the distance between first and last (At most log 2(last - first) + O(1) comparisons). However, for non-RandomAccessIterators, the number of iterator increments is linear.

Fastest system test I've ever seen!