### Zlobober's blog

By Zlobober, 14 months ago, translation, ,

Hi everybody!

These days Moscow is conducting the 2nd International Olympiad of Metropolises that is an international competition for high school students from biggest cities and capitals all around the world. One of the disciplines of the competition is informatics. Rounds of the competition were prepared by the jury members invited from St. Petersburg, Minsk, Almaty and Moscow olympiad scientific committee which you may know by Moscow team Olympiad, Open Olympiad in Informatics and Moscow Olympiad for young students (rounds 327, 342, 345, 376, 401).

We are very grateful to MikeMirzayanov for Polygon system that made it possible to conveniently hold a simultaneous statement translation process into lots of languages. As a good friends of Codeforces platform, we conduct a parallel rated Div. 1 + Div. 2 round on the competition problemset.

Round will happen on September 6th at 12:55 UTC and it will last for two hours. There will be 5 problems for each division, scoring will be announced later.

Scientific Committee of the olympiad consists of: andrewzta, GlebsHP, Endagorion, _meshanya_, Chmel_Tolstiy, Zlobober, Helen Andreeva and Bakhyt Matkarymov. Problems were prepared by timgaripov, -__-, halin.george, grikukan, malcolm734, LHiC coordinated by your humble servant.

Codeforces coordinator KAN helped us to choose problems for a round.

Good luck and high ratings for everybody!

PS We kindly ask everybody who knows problems of an on-site event not to participate in a round and not to discuss them in public, as this may be a subject for disqualification.

Congratulations to the winners!

In div. 1 they are:

In div. 2 they are:

The analysis is published. Thanks to all for participating!

•
• +235
•

 » 14 months ago, # |   +129 Note that round ends 5 minutes before CSAcademy Round #47, so you can participate in both of them if you want.==============Обратите внимание, что раунд заканчивается за 5 минут до CSAcademy Round #47, и вы можете успеть поучаствовать в обоих раундах, если хотите.
•  » » 14 months ago, # ^ |   -32 I'm afraid that my laptop chagre is not enough for 4 hours of competition.==============Я боюсь, моему ноутбуку не хватит заряда на 4 часа соревнований.
•  » » 14 months ago, # ^ | ← Rev. 2 →   -29 I think will be good ,if we have 10 or 15 minutes before CS academy Zlobober .=================================Я думаю было бы хорошо ,если бы мы имели 10 или 15 минут до CS academy Zlobober .
•  » » 14 months ago, # ^ |   +186 We postponed the start of the CS Academy round by 15 minutes.
 » 14 months ago, # |   +143 Why this round called extraordinary? :)
•  » » 14 months ago, # ^ |   0 I believe this means that the round will be rated differently. Not sure on the specifics though.
•  » » » 14 months ago, # ^ |   +36 Some crazy things like "there will be subtasks" comes to my mind :)
•  » » » » 14 months ago, # ^ |   +8 I'm sorry to disappoint you, but there won't be any subtasks. Also, if there was any difference in contest format, most probably round wouldn't have been rated.
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   +5 http://codeforces.com/contest/391 (however one may argue this was not rated because it was affected by Codeforces Blackout xD)
•  » » » » » » 4 months ago, # ^ |   -8 while searching for solution of http://codeforces.com/contest/854/problem/E i found a blog which is using a data structure called chair tree . i don't know anything about this data structure and nothing is on internet can u help me to provide some link about this data structure from where i can learn blog -- https://blog.csdn.net/DaF_alex/article/details/77542114
•  » » » » » 14 months ago, # ^ |   -34 Is it rated on earth?
•  » » » » » » 14 months ago, # ^ | ← Rev. 2 →   -36 +1
•  » » 14 months ago, # ^ |   +49 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.
•  » » » 14 months ago, # ^ |   0 Yeah, makes sense. Thanks!
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +5 A better way to write is "Rated, extraordinary Codeforces ...". Still not so good but at least people would not have any doubt about rating.
 » 14 months ago, # |   0 3 contests in 3 days fantastic :)
•  » » 14 months ago, # ^ |   -59 Not to mention: - You just got 3 upvotes - As of now, this comment was posted 33 minutes ago - Your first name has 3 m's and 3 vowels - Your last name also has 3 consonants
 » 14 months ago, # |   -76 Is the round rated?
•  » » 14 months ago, # ^ |   +60 Can you read?
 » 14 months ago, # |   +70 I hope there won't be a geometry problem :D
•  » » 14 months ago, # ^ |   -15 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.
•  » » » 14 months ago, # ^ |   +184 Graphical Illustration :) Forgive my paint skills.
•  » » » 14 months ago, # ^ |   +8 why you have to be mean to him ?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 He wanted to see the dependency between rating and not loving geometry :(Offtopic Codeforce is missing emojis :D
•  » » » » » 14 months ago, # ^ |   -8 i don't mean you i mean him why he has to be mean to people with lower rating
•  » » » » » » 14 months ago, # ^ |   +30 Because he is Purple..? The Evolution Of CodeforcesMathforces -> implementationforces -> geometryforces -> ColorForces
•  » » » » » » » 14 months ago, # ^ | ← Rev. 2 →   -16 Codeforces -> ColorforcesCome on, even the legendary grandmasters admit it. And by leeching of their legitimacy to prove this, I too am contributing to it.This comment is an example: watch me get downvoted to hell because I am gray and posted this.
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +76 I would beg to differ. Geometry is rather hated all around the world by vast majority of people. The thing is, green struggle to check whether n points are collinear and reds struggle with computing area of sum of pacmans by integrating border of regions with holes with border consisting of different arcs and segments :P. However I like geometry. I think that maybe geo problems are not as appealing as others but I have just simply forced myself to like it because somebody in our team had to do this :P. And dealing with all stupid corner cases and precision issues is never exciting.
•  » » » 14 months ago, # ^ |   +28 I really hates geometry, so I'll be a great counterexample for that sentence :)
•  » » » 14 months ago, # ^ |   +27 I don't get it that how a particular type of problems should be or can be hated. I mean, there are so many topics there, and if one is not comfortable with some topics or faces difficulties in solving problems regarding those, he/she shouldn't dislike/hate it. Every topic has its own beauty. I personally like geometry even though I am not so good at it. And I suck at DP. Does that mean I'd say "Why so many DP problems?" or "This round sucks because 2 DP problems appeared!"??? No, I wouldn't say that. I know most people are not that comfortable with geometry problems. So what? That doesn't make it bad. And as Swistakk said, Red coders face trouble with really tough geometry problems and Blue/Green/Cyan/Grey coders face trouble with simple problems. So, it depends on one's skill. And it can also happen that a very good geometry(or any other particular topic) problem solver is Green while a red coder is not so good with that topic. It can happen sometimes, maybe rarely. But personally I think, everyone should have basic knowledge of every topic. One should know how to check if n points are collinear and other basic geometry stuffs, and one should also know the basics of every topic that may appear in a standard programming contest.
•  » » » » 14 months ago, # ^ |   +8 yeah, but a contest shouldn't be ALL math and geometry. What if you had a contest consisting of 6 DP problems? Wouldn't be very diverse or fun.
•  » » » 14 months ago, # ^ |   +59 No, I hate geometry.
•  » » » 14 months ago, # ^ |   +5 not really. Thanks to those geometry problems my color changed from green to light blue. I love geometry problems :)
 » 14 months ago, # |   +2 Good luck and high ratings for everybody
 » 14 months ago, # |   -41 PLZ downvote or be bad at code!
 » 14 months ago, # |   +20 I just find there is only 2016 International Olympiad of Metropolises, day 1 in CF GymWould you please put "2016 International Olympiad of Metropolises, day 2" to Gym
•  » » 14 months ago, # ^ |   +15 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.
 » 14 months ago, # |   -9 That's my last chance to become an expert till tomorrow.
 » 14 months ago, # |   +3 May the force be with all....
 » 14 months ago, # |   +6 For every contest, score distribution is announced just before the contest starts. Just for my curiosity, I want to know, what's the reason behind this?
 » 14 months ago, # |   -7 The start time of this contest is perfect. thank you ♂ sir
 » 14 months ago, # |   +18 Hope problems are better than previous contest.
•  » » 14 months ago, # ^ |   +2 contests*
 » 14 months ago, # | ← Rev. 2 →   +3 we need more CF rounds!!!
 » 14 months ago, # |   +13 Score distribution?
 » 14 months ago, # |   -14 WTFFFFFFFFF? WHY DIV1D is very easy??? I hope it will not faill
•  » » 14 months ago, # ^ |   0 Did you write dp[i][money on card] or what?
•  » » » 14 months ago, # ^ |   0 dp[i][j] means minimum answer for first i numbers with at the end you have 100*j bonus. (why 100*j? because j is divisible by 100 everytime)So, you can calculate dp in O(n2) easily, but I guessed it is not optimal to have > 3100 bonus. I'm not sure that it will pass systest
•  » » » » 14 months ago, # ^ |   0 I hope >2000 is not optimal, otherwise my solution is wrong :/
•  » » » » 14 months ago, # ^ |   0 Hope there won't be problems where you assume things at EJOI.I am not that good at such problems, always trying to prove things and then I spend a lot of time on some math (99% of cases I fail to prove). Just assume that as a fact but by the time I start coding the contest is over :(
 » 14 months ago, # |   0 How to solve Div 2 C? I tried to find a recurrence relation for 1 hour before giving up.
•  » » 14 months ago, # ^ |   +17 priority queue on cost.
•  » » 14 months ago, # ^ |   0 DSU
•  » » 14 months ago, # ^ | ← Rev. 2 →   +11 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.
•  » » 14 months ago, # ^ |   0 Sort the flights by their price in a descending order, then for each flight you have to do one of those things1-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
•  » » 14 months ago, # ^ |   0 I used intervals tree for find first free place, starting with min(i,k)
 » 14 months ago, # |   +3 How to solve div2 D/div1 B ?
•  » » 14 months ago, # ^ |   +8 Prefix/suffix minimum sweep line
•  » » » 14 months ago, # ^ |   0 mind to explain?
•  » » » » 14 months ago, # ^ |   +2 You need to find the minimum possible cost to cover all flights for n people towards the Metropolis within a certain prefix, and similarly we do that for each suffix. Then, you just do a sliding window, and at each step of the iteration, you can find the answer in O(1) using the precomputed prefix and suffix values.
•  » » » 14 months ago, # ^ |   +1 Can you suggest some good tutorial of this topic?
•  » » » » 14 months ago, # ^ |   0 This isn't a geometry sweep line, it's just the standard technique that's usually finding interval intersections and stuff like that.
•  » » 14 months ago, # ^ |   0 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).
•  » » » 14 months ago, # ^ |   0 Ok thnx.
 » 14 months ago, # |   0 do me git rate for contet?
 » 14 months ago, # |   0 Is there nlogn scanline solution for div1C? I solved it with merge sort tree in O(6 * n * logn * logn), but I'm quite concerned about TL
•  » » 14 months ago, # ^ |   0 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
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 Mine was 4*QlgN, I calculated the points that are up-left,up.right,down-left and down right for every query
•  » » 14 months ago, # ^ |   0 Yes i did with scan line in the O(6*n*logn)
•  » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # |   0 How to solve C?
 » 14 months ago, # | ← Rev. 2 →   +12 Is the there a hack test for DPpos, money, where money is current money in card?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Can you explain your dp solution?
•  » » » 14 months ago, # ^ |   +18 Well DPpos, money is the answer till pos if we have money money (:D) in the card. I assume that if money > 3000 we will just pay for the next by card. And we have 2 cases for the dp: either we pay everything by cash, or we remove Y (from 1 to min(currentcost, money)) from the card.
•  » » » » 14 months ago, # ^ |   +8 Do you have any proof?
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   +5 Nope, I stresstested it with a brute force (1000 random tests) and it was ok, but still I'm not sure so that's why I asked if someone has a counter sample. UPDATE: it passed.
 » 14 months ago, # |   +7 Too many data structure!
•  » » 14 months ago, # ^ |   0 Too many greedy!
•  » » » 14 months ago, # ^ |   0 Greed is good
 » 14 months ago, # |   +47 My current rating=2017, so this is good bye 2017 for me. Also goodbye div 1 :(
 » 14 months ago, # |   0 Binary search + segment tree (query min prefix) solve D1 D in any contrains for cost, bonus.
•  » » 14 months ago, # ^ |   +8 Can you explain how?
 » 14 months ago, # |   +13 Time limit of Div.1 C is too tight, I kept getting TLE on pretest 4 with N log N complexity! It's not fair!
•  » » 14 months ago, # ^ |   0 Well, i passed pretests with O(nlognlogn) solution, so there may be a problem in your implemention
•  » » » 14 months ago, # ^ |   0 I think there's nothing wrong with my implemention, maybe I have a large contant. That leads to 9 * N * log N.
•  » » » » 14 months ago, # ^ |   0 I also have a constant O(6nlognlogn)
•  » » » » » 14 months ago, # ^ |   0 O(6 * N * log N * log N) passed? That's crazy. Well, perhaps I was wrong. I'll check my program later.
•  » » » » » 14 months ago, # ^ |   0 I have corrected my answer. It seems that my submission during the contest was right, but I picked the wrong data structure. The problem can be solved with binary search tree by making all queries offline, but I used persistent segment tree. That brought me a huge constant, I think I could pass within 3 seconds. Thanks for listening to my problem.
•  » » » » » » 14 months ago, # ^ |   0 Good day to you,well I managed to get AC with PST (in ~1.6) so it shall be no problem.Your PST seemed to run even faster then mine.Moreover if I changed the limits: #define MAXN 500005 #define MAXP 18200095 the TLE turned into WA (but hope I didn't broke anything by this)Good Luck & Have Nice Day!
•  » » » » » » » 14 months ago, # ^ |   0 I'm sorry but I'm quite sure my PST method runs much slower than my BIT method (about twice slower), and my BIT method passed in 1.2s. That program might be my last submission during the contest, I had not finished debugging it, so it went WA. Check my previous submissions during the contest, I was saying about that. Thanks a lot for listening to me and wish you a nice day (Exactly evening here in China).
•  » » » » » » » » 14 months ago, # ^ |   0 Oh yes, I didn't want to doubt about this statement (imho PST has very big "constant" even though the complexity is nice — due to memory).I just wanted to propose that the mistake might have been somewhere else — anyway seems you have tried to increase constants too (with TLE) so I'm slightly confused :O :P [maybe other submission]Well so enjoy your evening then ^_^
 » 14 months ago, # |   +14 my reaction while pretests is running
•  » » 14 months ago, # ^ |   +9 same reaction when main tests and hacks are running as well.
 » 14 months ago, # |   +25 Finding a typo in my code for problem D after the contest ended. However it still passed the pretests. Pretests for D are too weak. :(
 » 14 months ago, # | ← Rev. 3 →   +21 A minute of silence for a contestant who made the following "genius" piece of code... int n; //Size of array P PersistentIT t; ll Solve(int l, int r, int d, int u) { ... int n = (r-l+1); int nu = t.query(l, r, u+1, n); ... } I can't believe that it took me nearly 1.5 hours to solve C (with I should be able to do in less than 15 minutes, given that I had the Persistent IT template). I'm so terrible at not creating bug T_T
•  » » 14 months ago, # ^ |   -34 You sound so arrogant man ? !
•  » » 14 months ago, # ^ |   +22 I'd recommend using the -Wshadow compiler option because of this. It saved my life quite a few times.
•  » » » 14 months ago, # ^ |   0 I wish I knew about this sooner. Thanks for the suggestion.
 » 14 months ago, # |   0 Div2C solvable with segment tree?
•  » » 14 months ago, # ^ |   +6 Yes, but with priority_queue is easier.
•  » » 14 months ago, # ^ |   0 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 :/
•  » » 14 months ago, # ^ |   +1 i used a greedy approach with a set
•  » » » 14 months ago, # ^ |   0 I used greedy with vector pair!! WA just cz of missing long long :(Same code passed on adding long long after the contest :(
 » 14 months ago, # |   0 How to solve div2C ?
•  » » 14 months ago, # ^ |   0 I used MergeSort + BinarySearch but couldn't finish the code before the contest .
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 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.
 » 14 months ago, # |   +29 Does anybody have solution to D, which is clearly correct? I wrote something and I've stresstested it, so I'm not in this group :P
•  » » 14 months ago, # ^ |   +26 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.
•  » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # |   0 how to slove div2 B....
•  » » 14 months ago, # ^ |   +1 cout << 1 << ' ' << min(n - k, 2 * k); 
•  » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # |   0 Is div1C merge sort tree? I found bug in my solution but still not sure if it's the right way
•  » » 14 months ago, # ^ |   +5 It can be done offline using sweep line + Fenwick trees.
•  » » 14 months ago, # ^ |   +5 Mine is with simple wavelet tree. It runs fast enough.
•  » » » 14 months ago, # ^ |   0 Nice!
•  » » 14 months ago, # ^ |   0 I think my code is right now. How can I submit my code after the contest? There is no button appearing.
•  » » » 14 months ago, # ^ |   0 You will have to wait until after system testing has finished. At that point you will be able to submit again.
•  » » 14 months ago, # ^ |   0 Yes, i got AC with merge sort tree
•  » » 14 months ago, # ^ |   0 I solved it offline using SQRT decomposition + Fenwick trees. Managed to squeeze it into TL.
•  » » 14 months ago, # ^ |   0 Can be easily done by greedy + vector pair!! I got WA cz of missing to typecast answer to long long :(
•  » » 14 months ago, # ^ |   0 I used persistent segment tree.
 » 14 months ago, # |   0 I wrote a '+' instead of a '-' in a 200-lines code on C and I found it 1 minute after contest ended :( FML
 » 14 months ago, # |   +76 when i locked my solution and solution is hacked
•  » » 14 months ago, # ^ |   0 Sympathize with you
•  » » 14 months ago, # ^ |   0
 » 14 months ago, # |   0 how to solve div2/C .
•  » » 14 months ago, # ^ |   0 Record the boundary range with a next array
•  » » 14 months ago, # ^ | ← Rev. 2 →   +6 This is my solution and might be wrong1-Sort the A[] in descending order of cost (store it as pair)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 valuebinary 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 setThe flight with huge cost, the place wont change or change minimally..
•  » » » 14 months ago, # ^ |   0 I used that approach . but the problem was with calculating the total cost it was always wrong .
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 priority_queue + save index which have the same cost
•  » » 14 months ago, # ^ |   +1 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.
•  » » » 14 months ago, # ^ |   0 why is this similar approach giving TLE on test case 6? code
•  » » » » 14 months ago, # ^ |   +6 Your TLE lies in this linelower_bound(st.begin(),st.end(),c[i].second);should best.lower_bound(c[i].second)code
•  » » » » 14 months ago, # ^ |   +1 That was the exact mistake I made. Use set's lower_bound, not the generic one.
 » 14 months ago, # |   0 I misread the statement of Div2.D that there will be flights between the cities. Then I went to an intricate solution using ternary search + visual vertexes + shortest path on a reconstructed graph and a transposed one. Failed to finish the implementation.Maybe I should improve my reading. The previous round is ruined for I misdeemed that given points A,B,C can be exchanged.
 » 14 months ago, # |   0 I can't debug 1B out... Goodbye div1...
•  » » 14 months ago, # ^ |   0 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
•  » » » 14 months ago, # ^ |   0 I still can't find the problem, probably we coded wrong on some different places and WA'ed on the same pretest
 » 14 months ago, # |   +15 Anyone with probably correct solution to Div1 E?
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 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 ti, 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).
•  » » » 14 months ago, # ^ |   +10 How do you compute in O(n log n) for a triangle?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 We can assume that the triangle is (0, 0), (0, 1), (1, 0) by changing the base. We have points (xi, yi), and queries (ai, bi), (ai, bi + ti), (ai + ti, bi). With a single sweep along x + y, it is possible to compute values in O(n log^2 n). With a sweep along x + y, and a sweep along x, I think it is possible to reduce it to O(n log n) by computing #(x + y < ai + bi + ti) - #(x + y < ai + bi + ti, x < ai) - #(x + y < ai + bi + ti, y < bi) + #(x < ai, y < bi). (I will try to draw something to explain it).
•  » » » » » 14 months ago, # ^ |   +10 It is correct, but kind of an overkill.You may express the original polygon as a sum of 2k half-infinite trapezoids, some of which are added and some are substracted. A number of points in a trapezoid of fixed shape may be found in O(n log n).
•  » » » » » » 14 months ago, # ^ |   +10 Sorry, I don't see how you would decompose the polygon into the trapezoids. Could you explain?
•  » » » » » » » 14 months ago, # ^ |   0 Shoot a downwards ray from each vertex of the polygon. Each side of the polygon along with its two rays forms a half-infinite trapezoid
•  » » » » » » » » 14 months ago, # ^ |   0 Okay. But in what way is this easier than a triangle, with one base of length zero?
•  » » » » » » » » » 13 months ago, # ^ |   0 Well with similar trapezoids you can transform them all into rectangles. Then counting the number of points inside a rectangle can be done with a single sweep + fenwick tree. I think doing this with triangles is a lot more complicated.
•  » » » » » » » » 13 months ago, # ^ |   0 What kind of transformation makes it a rectangle?Also, couldn't some of the regions become triangular when you draw the downward lines?Sorry for the questions, just have never seen this technique before.
•  » » » » » » » » » 13 months ago, # ^ |   +3 Perhaps calling it a trapezoid is confusing? The trapezoids have no bottom edge, as the downwards rays extend to -infinity. The idea is that for each side of the polygon, we want to sum all the points underneath it. Then to get the sum of points inside the polygon, we add up the points below the upper hull and subtract away the points below the lower hull.All the trapezoids are two vertical lines and then a sloped line. Half-infinite trapezoids with the same slope can all be transformed into half-infinite rectangles with a change of basis. So if the side of the polygon is the vector (a, b), the transformation (x, y) -> (x, ay-bx) works (it makes the sloped side horizontal).
•  » » » » » » » » 13 months ago, # ^ |   +3 Oh, okay. I thought the "trapezoids" were real 2D trapezoids, which cannot be affine transformed into rectangles, but it all makes sense with infinite trapezoid. (I guess a triangle is a sum/difference of two or three trapezoids, then.)Thanks for taking the time to explain.
 » 14 months ago, # |   0 Why doesn't system testing start right after the contest ends?
•  » » 14 months ago, # ^ |   +28 I shouldn't be the one posting this but the problemsetters :D
•  » » 14 months ago, # ^ |   -8 unDERSTANDAble haᵥₑ ₐ ₙᵢcₑ daY
•  » » 14 months ago, # ^ |   0 I just wanted to know why it doesn't happen. Why are you making fun of it ?
•  » » » 14 months ago, # ^ |   +1 You'll understand that once you decide to handle your own round :)
 » 14 months ago, # |   +5 I solved Div1 D like this and hacked. Is there any counterexample?1) Try buying first k with money only 2) Try buying first k with money only, except the last "1000" of them
•  » » 14 months ago, # ^ |   0 You're missing the case of buying first k plus the first "1000" after them.
•  » » 14 months ago, # ^ |   0 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).
•  » » 14 months ago, # ^ |   0 Accepted now, thank you all!
 » 14 months ago, # |   0 How can i know for which input was my DIV2B hacked?Thank you
•  » » 14 months ago, # ^ |   0 Page of hacks: http://codeforces.com/contest/854/hacks. Just find yourself by nicknameYour hack-case: 15 6. You write 1 12, right: 1 9
 » 14 months ago, # |   +47 Today I learned: if s is a set, lower_bound(s.begin(),s.end(),v) is not guaranteed to be logarithmic. Use s.lower_bound(v).
•  » » 14 months ago, # ^ |   +5 I learned that in an official contest :') , AFAIK in worst case it can run in O(N^2)
•  » » » 14 months ago, # ^ |   +1 Yep. Got TLE on problem A today because of it. Luckily some frantic Googling let me fix it in time :)
•  » » 14 months ago, # ^ |   0 http://en.cppreference.com/w/cpp/algorithm/lower_boundThe 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.
 » 14 months ago, # |   +38 Mike Bought a nitro for the systest :D
•  » » 14 months ago, # ^ |   +8 Fastest system test I've ever seen!
•  » » » 14 months ago, # ^ |   +7 Maybe this is the reason the contest was extraordinary! :O
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +32 Shut up morty, let me do the talking. burrrp
 » 14 months ago, # |   +5 Bugatti CF Systems
 » 14 months ago, # |   +1 can someone tell me what is wrong with my code 30156568 for 2D(1B)?
•  » » 14 months ago, # ^ |   0 I am also getting WA on same Test case :(
•  » » 14 months ago, # ^ |   0 I think you miss a condition int your get_ans(): from 1 to i there must be n flights with different departure cites, and also from i + k + 1 to the last day, there must be n flights with different arrival cities.
•  » » 14 months ago, # ^ |   +3 I found that your code had some small mistakes: var "myINF" was declared as a 32-bit integer, but exactly it should have declared as a 64-bit integer. the answer could equal 1e12, so the INF should be a little bigger. the max suffix or prefix ans may be updated more than once in one day, so in the function goright dpr[i]=dpr[i]-prev+sumright[num]; is correct. this is the correct version 30160358
•  » » » 14 months ago, # ^ |   0 thanks.
 » 14 months ago, # |   +5 Can anyone tell me if there is a way to make 30158579 faster? In each query I use 6 calls to 2D Fenwick Tree, so the complexity is O(Q log^2 N).
•  » » 14 months ago, # ^ |   0 Maybe compressing the coordinates and not using a unnordered_map.
•  » » 14 months ago, # ^ |   +3 Good day to you,Firstly, such 2DFenwick also has "hash-map-complexity" which can't be neglected.Well there were some other greedy solution for this problem anyway to keep problem, simply replace fenwick, you can:Use some segment-structure, whic could answer: Number of numbers on "[L → R]" lesser/equal then "X" (if you want rectangle [L,X]→[R,Y]), you can ask [L,R,Y]-[L,R,X-1].First structure, which could do it in "clear" O(logN^2) is merge-sort tree (segment tree with sorted number in each node. You use it as classical segment tree with binary searches)Second — probably faster — way is Persistent Segment Tree (you can simply add "1s" in order of their heights). This works in O(log(N))Hope it is understandable.In case you are interested in anything (or it was not undestandable), don't hesitate to ask.Good Luck & Hope it helped,Have nice day!~/Morass
•  » » 14 months ago, # ^ |   0 Instead of storing a pair in unordered_map, try using an array of unordered_maps. Although 6 calls to 2D Fenwick tree seems unlikely to pass given the constraints and time limit.
•  » » 14 months ago, # ^ |   +3 I managed to make a 2D Fenwick Tree pass using the query logic of another submission:http://codeforces.com/contest/853/submission/30166694 my 2D Fenwick Treehttp://codeforces.com/contest/853/submission/30149861 original submission for the logicTurns out you can calculate everything using only 4 queries.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 I managed to narrow down my answer for one question to two queries to fenwick tree, but still it wasn't good enough, probably this map/unordered_map is too much.Edit: Nevermind, forgot about two corners, it's 4 calls.
 » 14 months ago, # |   0 What did the "rated extraordinary" mean, for this contest?
•  » » 14 months ago, # ^ |   +2 The rating will increase / decrease by a factor of 500 today. For example, in any other contest, if u get , today you will get
•  » » » 14 months ago, # ^ |   -9 what does that mean ??? you mean for example +500 rating ??
•  » » » » 14 months ago, # ^ |   +27 Hint : I was sarcastic
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 lol i thought you were one of the problem setters my bad
 » 14 months ago, # | ← Rev. 2 →   -42 i guess the contest is unrated :/
 » 14 months ago, # |   0 Why using arrays here took 826 ms while the same code using vectors here took 264 ms.
•  » » 14 months ago, # ^ |   +6 you used scanf. It's more fast than cin
•  » » 14 months ago, # ^ |   +3 scanf faster than raw cin
•  » » 14 months ago, # ^ |   0 Oh thanks!, Got it
•  » » 14 months ago, # ^ |   0
 » 14 months ago, # |   0 so is it rated？
•  » » 14 months ago, # ^ |   0 my fault. rating updated when i refresh the website.
 » 14 months ago, # |   0 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?
 » 14 months ago, # | ← Rev. 2 →   0 Weak testcases ( in Pretest ) in DIV2-D. No integer overflow upto 75 testcases. Got overflow in testcase 76 due to int declaration :(
•  » » 14 months ago, # ^ |   +9 LOL, since when do people call testcases "weak" when they manage to fail their codes?
•  » » » 14 months ago, # ^ |   0 (Edited) Weak Pretests actually. If there were overflow cases in pretests, may be I could manage to figure out mistake during contest.
 » 14 months ago, # |   0 Can someone tell me why this does not get a TLE ?http://codeforces.com/contest/854/submission/30162063
•  » » 14 months ago, # ^ |   +5 because c++ is clever :D this while is O(1) :long long test = 1000000000000000000; while(test) { test--; }and anythings like these are O(1) too is c++ : int ans = 0;for(int i = 1 ; i <= 1e9 ; i++) ans++;orint ans = 0;for(int i = 1 ; i <= 1e9 ; i++) ans += i;my teacher M.Mahdi said these to me :)
•  » » » 14 months ago, # ^ |   0 Thanks a lot man... I tried to hack a solution containing similar type of loop and failed. at least learnt something new :)
 » 14 months ago, # |   0 what is the case 83 in div2.d ? any special case or overflow reasons ?
 » 14 months ago, # |   +25 wxh_ak ( first in div 2 ) . First contest encrypted submission. 25623055
•  » » 14 months ago, # ^ |   +14 Doesn't it violate Codeforces' "Can't-do"s (here)?Point 4 of "Can-do's and Can't-do's":It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work.
•  » » 14 months ago, # ^ |   +13 He is mcfx.You can compare their code style.
 » 14 months ago, # |   -40 I really want to thank you for your great post. Keep doing like this. Godaddy \$1 Web Hosting is one of the best web hosting services in the world. Thank you.
 » 14 months ago, # |   0 I was in doubt if I would attend to a class or do the contest. It seems that it was worth taking the contest =D Thanks for the congratulations!
 » 14 months ago, # | ← Rev. 6 →   0 Did you see that in the prolog to the contest [gritukan:http://codeforces.com/profile/gritukan] is grikukan. Is it corrigendum?
 » 13 months ago, # |   0 I want to learn data structure and dynamic programming logic easily. please, give me some helpful codeforces blog or others link.