(Idea — Sender , developing — timgaripov)
Tutorial is loading...
(Idea — Chmel_Tolstiy, developing — mingaleg)
Tutorial is loading...
(Idea — Zlobober, developing — halin.george)
Tutorial is loading...
(Idea — GlebsHP, developing — mingaleg)
Tutorial is loading...
(Idea — glebushka98, developing — vintage_Vlad_Makeev)
Tutorial is loading...
(Idea — Elena Andreeva, developing — vintage_Vlad_Makeev)
Tutorial is loading...
(Idea — Zlobober, developing — malcolm)
Tutorial is loading...
Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).
I have a simple solution for D. It has complexity O(NlogNlogX), but can be applied when (1000, 2000) bigger, and changing bonus function.
Could you please explain the logic behind your solution?
Assume we need to check if X is enough. Iterate a the number of whole cash paying for 1000. Clearly, we should pay b = (X - 1000 * a) / 2000 times for 2000. And We should do it for first a 1000 and first b 2000, each position we set values to 100/200. The remaining position are filled with their negative cost. Finally, add X - 1000 * a - 2000 * b to first position. If the minimal prefix is non-negative we know X is enough.
Can someone link to the classical problem referenced in D? I can't seem to easily find it on Google.
In Div2-A, when n is even, won't the answer be the opposite of what you have written? If n is divided by 4, the answer should be n/2-1 and n/2+1.
Div2 C can be solved with DSU which is faster
Your solution isn't faster, you sort the numbers and that's the same complexity as the proposed solution.
Oh you are right but since numbers are up to 1e7 you can sort them in linear time
Thanks for a fast and well explained Editorial....
How does Div2C greedy approach work? We can create a bipartite graph with the left vertices as initial times and the right vertices as final times and an edge with the weight of the cost. It is a classic assignment problem. What condition in this question reduces the problem complexity making the greedy solution optimal?
Let me try it. Consider we have a set of planes yet to leave. Now, if we choose ith plane to stay from our current set, we incur a penality of Ci. And we want this penality to be minimum. Now think about it and you will understand.
Let's say at some point we have two planes x and y with cx = 2, cy = 5. Intially x is supposed to depart at 4 and y is supposed to depart at 3. Currently we are at 5th time unit. The total cost if we choose x first will be 2 * (5 — 4) + 5 * (6 — 3) equals 17. If we choose y, it will be 5 * (5 — 3) + 2 * (6 — 4) = 14. But the minimal penalty is given by cx at 5th time unit. That is not leading to the optimal solution. Correct me if I am wrong.
I don't understand you. What we want is minimum cost and we will get it by taking cy cost first because it is bigger, and as you say this is optimal.
"We will show that following greedy is correct: let's for each moment of time use a plane, which can depart in this moment of time (and didn't depart earlier, of course) with minimal cost of delay." Does this not mean that the plane x gives us the minimal cost?
I am having trouble understanding the editorial. But the solution i mentioned in first comment is correct. You can refer to my solution if it helps.
I think there is a mistake in the second solution of A. In line 2, it should be b=(n/b)+1; not b=(n/b);
If you look carefully there is a "ceiling" sign. As n is a odd number, n/2 will always be x.5, here x is (n-1)/2. And ceiling of x.5 is x+1.
Thanks.
Can anyone please explain the solution of problem 853B - Jury Meeting more?
Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).
In problem Div2D, you say that: "Obviously, each member of the jury needs to buy exactly two tickets — to the capital and back." Does it mean that two jury members can't fly in the same plane? o.O
EDIT: we7d right, they obviously can't — silly me ^_^
they can't because only one member in each city and flights are only from city x to city 0 and vice versa
Thx for answer, now it's much simpler task.:D Previously I thought that flights like 1 10 8 5000 and so could exist. Silly me :(
My same solution which passed during system testing if I submit again now gives TLE. Is it that system testing servers are better or any other reason.
can someone explain the greedy proof in div2 C could not understand it from editorial like in this statement "Let x be plane with minimal cx, such ax ≠ bx. At any moment greedy algorithm takes avaliable plane with lowest cx, so ax < bx. " what is the proof for ax<bx.?
I think there is a better explanation. You can think about this, how to get the best answer? Supposing that we have an initial arrangement, how to optimize it. First of all, we will come up with an idea to swap some planes' departure time. If plane i departs at ti, plane j departs at tj, then the cost of them two is ci * (ti — i) + cj * (tj — j) = ci * ti + cj * tj — ci * i — cj * j, and ci * i — cj * j is a constant. So our goal is to minimize ci * ti + cj * tj, and it's obvious if ci > cj, ti > tj, we should swap ti and tj. So for every moment t, we should choose the highest cost from those who can take off at this time. And this is my code.http://codeforces.com/contest/853/submission/30136836
tnx ,good explanation.
In Div1C : can anyone please elaborate how to find the number of points in the query rectangle efficiently?
Try persistent segment tree, where root[i] represents the root of segment tree for all elements having a row <= i.
You can also solve the queries offline and you won't need persistent tree.
can you please explain how we can answer the queries offline?
Sort the queries and marked squares from left to right(column),and use segment tree to maintain it.When adding a suqare(i,p_i),add 1 to p_i in the segment tree,and you can find the answer when asking a query.
Div 1 B can be easily solved in linear time.
Can you provide a solution using this approach?
Yes, here's my submission: 30179926
I'll provide my non-linear two-pointer version without multiset (actually, it's replaced by inverse of two mini-stacks) for clarity: 30313607
In Div1-D, what is "next after i interesting day"? Did you mean "the interesting day next after i"?
Spent two hours to debug 1C, just to find out that p[i] is supposed to be row p[i] column i instead of row i column p[i]...
same here :(
Same! Though I've even read this right but swapped rows and columns in queries in my mind.
is there any explanation about "2d-tree" or whatever you use to reach O(q·logn) complexity in 1C/2E ?
Yes, actually with a 2D Tree, you get O(Q * log2N). To reach O(Q * logN), you can use an approach similar to sweep line supported by a BIT. The process would be as follows.
Is it even possible to get a 2D tree under the memory limit?
Опять русские авторы и английские разборы?
in Div1-C I tried persistent segment tree to solve the queries in O(n*logn)
but I failed at test 4 , any help or hint please code
UPD : problem solved , I had to swap rows and columns from the input ...
I solved it during competition using persistent segment tree. You can check my code 30147451
Why is Div1C offline search O(qlogn)?I think it should be O(qn)process time and O(1) query time.
Sorry, I understand now.
Can anyone please explain Div2-D/Div-1 B. I'm not able to understand much from the editorial.
I can't understand the proof for Div. 1 D. Why is it always optimal to have x_i <= 3000?
854 B
Please Explain this part.
Otherwise, if k > x, assume that apartments with indices 2, 5, 8 and so on are occupied, so any room has at least one inhabited room adjacent to it. Therefore number of good apartments is equal to number of vacant apartments and is equal to n - k.
One neighbour can cover two adjacent apartments. If there are more than x occupied apartments, one can divide the apartments in groups of 3 and assign them to the middle of each group (hence the 2 in 123, 5 in 456, etc.)
Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).
Actually Div.1 C can be solved in O(q log^2 n) and get Accepted...
haha you're right, I have just changed oset for a vector and got accepted
Regarding Michael and charging stations... the order of spending should be like... First check if u can pay with money and get some bonus back, if not then check if u can pay in bonus if not then check if u can pay combinely with money and bonus. But there is problem in above cases.. like what if at some point of time u had x (2000<=x&&x<3000) money and y amount in bonus and and value at next wo indexes is 1000,2000..., now u will pay 1000 by money and then u will be left with money<2000 and u got 100 in bonus back.. but what if u had decided to pay this 1000 in a way that u have 2000<=money left then in next index u would have paid in money full and got 200 bonus back.
So find out the last index of ten for which u can pay in money full, without spending bonus till then. Then check for two cases first u will buy that 1000 with money and u will not buy that 1000 (or any 1000 coming ahead) with money (actually spend money such that atleast 2000 is left to get a chance to get 200 in bonus on future indexes).
https://codeforces.com/contest/853/submission/85513762
Solution to Div. 1 D : For the most part greedy algorithm to first pay by only cash, then by only balance and finally by both if all else fails is a good idea. But the algorithm can fail in one case, ie, when instead of last 1000 we took could be replaced by a 2000 in the nearest future and it makes sense because say we are left with money amount of 1500 after last transaction and we do at least 1 1000 burles complete transaction but say instead of taking one of the 1000 burles payout, we consider a 2000 complete payout, we are left with 1500 + 1000 — 2000 = 500 burles cash with more bonus points and overall more amount to spend. Hence consider only 2 cases to solve the problem : First apply binary search on the amoung, check the greedy transactions, check greedy transaction when we do not do last 1000 complete transaction and instead a 2000 transaction in nearest future and if any of the case is viable, iterate in the binary search flow.
Div1 D: Проще представить решение следующим образом. Начнем с того, что мы имеем максимально возможную сумму бонусов (sum), которую можем накопить за все дни. Далее в качестве начальной позиции, предположим, что мы тратим бонусы в n, n-1, n-2 ... дни по максимуму, т.е. если n-й день стоит 1000, то мы тратим на него 1000 бонусов. Тогда каждый день, в который мы тратим бонусы будет вычитать из нашей sum-=(a[n-i]+cost) и ans-=a[n-i]. Далее рассуждаем, как это можно оптимизировать. Более эффективно можно распределить только последний день (с конца) в который мы тратим бонусы при условии, что для него a[n-i] == 2000 и sum<=1100. Т.е. вместо того, чтобы расплатиться оставшимися бонусами в день, который приносит 200 бонусов, нужно найти день стоимостью 1000.
It is easier to provide a solution for this. Let's start with the fact that we have a large possible amount of bonuses (sum) that can be accumulated over all days. Further, as a state position, let's assume that we spend bonuses in n, n-1, n-2 ... days at the maximum, i.e. if the i-day costs 1000, then we spend 1000 bonuses on it. Each day we spend bonuses will subtract from our sum-=(a[n-i]+cost) and ans-=a[n-i]. Next, we discuss how this can be optimized. More quickly, you can distribute only the last day (from the end) on which we spend bonuses when calculating that for it a[n-i] == 2000 and the sum<=1100. Those, instead of scattering the remaining bonuses on a day that brings 200 bonuses, you need to find a day with a[i]=1000.
В общем делается все за O(n) если учитывать время на чтение входных данных. Решение: https://codeforces.com/contest/853/submission/205653206