280.md (8824B)
1 Source: https://codeforces.com/blog/entry/6939 2 3 # Overview ... 4 5 In DIV 1, there are 3 normal tasks accompanied with 2 challenge tasks. About 40 competitors solve first three tasks during the contest and I believe there will be more if we extended the duration a little bit. 6 7 Task D is a standard data-structure problem hidden behind a classical maximum cost flow model. This kind of problem are usually trick-less, but hard to implement especially under the pressure. Because of this, it becomes tonight's draw-breaker. 8 9 Task E is a extended version on a classical DP && Math problem. There are many solutions to the original problem, one is giving a global view under the state transition, and using a data structure to handle it carefully. However, this one is even more harder, few people have ever tried it except [Jacob](/profile/Jacob "Candidate Master Jacob"). (Although is wrong.) 10 11 As a seasoned competitor, [Petr](/profile/Petr "International Grandmaster Petr") took the C-B-A order which proved to be the best choice through out the night. And after quickly solved C and B, he has sunk into problem A, it takes him about 45 minutes to cut-the-knot and got 2 **Successful Hacking Attempt** as a reward. 12 13 On the other hand, [peter50216](/profile/peter50216 "International Grandmaster peter50216") gave his response to Problem A straightly! It only took him about 15 minutes to write a code which is full of trigonometric function and if-else. And on top of this is another 15 minutes to solve the successors. After that, he gave 2 **Successful Hacking Attempt** on A and 1 **Successful Hacking Attempt** on B as the end. 14 15 While we were marvelling at [peter50216](/profile/peter50216 "International Grandmaster peter50216") for his solid skill in geometry, [al13n](/profile/al13n "Grandmaster al13n") gave the first attempt to problem D among the game. Unfortunately his solution get **TLE** on the pretests. 16 17 This is a **O(mk^2logn)** algorithm, and we think it is hard to optimize it to pass the pretests even for our setter. And abandoned the **O(mk^2logn)** solution and totally reconstructed the **O(mklogn)** from the sketch now became more difficult and audacious. 18 19 While we were praying to [al13n](/profile/al13n "Grandmaster al13n"), [Jacob](/profile/Jacob "Candidate Master Jacob") gave the first solution and the only solution for Problem E among the whole game! It cost all of his time and led him no time to solve others. It sounds like a miracle .. 20 21 We were all sooooooo excited and opened his code and look carefully, but, actually I myself got quite confused by his solution, and didn't know why it can work at all. 22 23 While all we setter and tester were checking the solution carefully. [UESTC_Nocturne](/profile/UESTC_Nocturne "Grandmaster UESTC_Nocturne") **(XHXJ)** gave the first correct solution among the game for problem D. It is a huge code more than 12kb, and perform as same as our std solution. Although he haven't solve A && B, this break-through has already establish his winner position. 24 25 After the contest, I interview her to "how can you solve this problem so quick", and replied as “I have solved the simplified problem, and have thought about this method before.” 26 27 At the same time, we found that [Jacob](/profile/Jacob "Candidate Master Jacob")'s solution was wrong, we generated a few maximal random data, and it return **WA** about one-quarter of them. After some discussion we decided to add one of them into the tests. 28 29 In both problem D and E, our pretests intended to be as strong as possible. How I wish to let [Jacob](/profile/Jacob "Candidate Master Jacob") know about his solution is wrong so he can quickly get out of the impasses and get **Accepted** in the end... . 30 31 [al13n](/profile/al13n "Grandmaster al13n") also pass from the pretests after [UESTC_Nocturne](/profile/UESTC_Nocturne "Grandmaster UESTC_Nocturne"), we are relieved to hear about it at first, but found it is a **O(mk^2logn)** solution with a wrong optimization soon, this solution will definitely fail in system test, but he may didn't aware of it at the time. 32 33 There are other three correct solutions for Problem D near the end of the game, among them [FattyPenguin](/profile/FattyPenguin "International Master FattyPenguin")'s solution is the fastest one, and he make it in ten minutes ago before the contest end and [liouzhou_101](/profile/liouzhou_101 "International Master liouzhou_101")'s solution actually is a **O(mk^2logn)** one but with some dramatic optimizations. It is hard to block this kind of solution or it could cause some trouble for our Java Users. 34 35 # Tutorial ... 36 37 [http://assets.codeforces.com/statements/280-281/Tutorial.pdf](//assets.codeforces.com/statements/280-281/Tutorial.pdf) 38 39 * [Problem 2A. Word Capitalization](https://codeforces.com/problemset/problem/281/A) 40 * [Problem 2B. Nearest Fraction](https://codeforces.com/problemset/problem/281/B) 41 * [Problem A. Rectangle Puzzle](https://codeforces.com/problemset/problem/280/A) 42 * [Problem B. Maximum Xor Secondary](https://codeforces.com/problemset/problem/280/B) 43 * [Problem C. Game on Tree](https://codeforces.com/problemset/problem/280/C) 44 * [Problem D. k-Maximum Subsequence Sum](//codeforces.com/problemset/problem/280/D) 45 * [Problem E. Sequence Transformation](//codeforces.com/problemset/problem/280/E) 46 * [Backstage](http://www.bilibili.tv/video/av500562/): The screencast of my screen during the contest, you can see what happened behind the scene if you are interested, just have fun ~. 47 * [CMHJT's tutorial](http://www.13331.org/420.html): Another tutorial written by one of the setters for C, D, E.(Chinese!) 48 * [roosephu's tutorial for D](//codeforces.com/blog/entry/6957): Tester's tutorial for Problem D. 49 * [Seter's tutorial for E](//codeforces.com/blog/entry/6952): Tester's tutorial for Problem E. 50 * [......](http://blog.renren.com/blog/271960376/897411882): A brief overview release after the contest end.(Chinese!) 51 52 # Sidelights ... 53 54 * There are some disputes about the problem A, but personally I like it very much, this is a basic problem(surely it is evil), can be described in one picture, and all of us could solve it if they are careful. Some people say it is harder than A so it should be swap with Problem C, but I insist on put it at A, because, we all think Problem B && C needs some idea, but A needs only basic knowledge we learned in middle school. And it can be solved in a different style if you have a well-implemented Geometry Template. Some competitors are just good at this kind of problem while others are not. And after all, this is the only problem which has trick in this contest. :) 55 * In problem B, some people got confused in “bitwise excluding OR = XOR or OR?”, they are only familiar with "XOR" but get into confused with something like "bitwise excluding OR". Well, as a Non-English speaker, I can only expressed my understanding, we didn't intend to do that. In the original statement we write "XOR" but during the translate process it became "bitwise excluding OR", and I did not think it could cause such trouble. Here we can only recommend you read more English book, because such things will occur from now on and keep up. 56 * [tourist](/profile/tourist "Legendary Grandmaster tourist") lost his target (Rating above 3000) after the contest. But we all think he'll return soon. 57 * [rng_58](/profile/rng_58 "Legendary Grandmaster rng_58") didn't participate in the contest but took a virtual participation on the next day. He can't solve D && E and get Rank 5 along after [Petr](/profile/Petr "International Grandmaster Petr"). 58 * [tclsm2012](/profile/tclsm2012 "Expert tclsm2012") as a purple, also solve Problem D during the contest, but failed at A && C at the expense. 59 * Both the winner and the runner-up failed on problem A. 60 * [UESTC_Nocturne](/profile/UESTC_Nocturne "Grandmaster UESTC_Nocturne")'s A solution was hacked by [scottai1](/profile/scottai1 "International Master scottai1"), the latter, also failed at the system test after a while. 61 * One of our setter ... came in the hospital after setting problems. 62 * We were adding tests against submitted solutions during the contest. 63 * **Daniel Sleator** (A professor at CMU who invented many data structures such as [splay trees](v), [link-cut trees](https://en.wikipedia.org/wiki/Link/cut_tree), [skew heap](https://en.wikipedia.org/wiki/Skew_heap) and discovered [amortized analysis](https://en.wikipedia.org/wiki/Amortized_analysis), [see Wikipedia ...](https://en.wikipedia.org/wiki/Daniel_Sleator))participated in Div 2 and get promotion to Div 1 after the contest. And he checked our Div 1. E and write a miraculous DP solution[1](//codeforces.com/contest/280/submission/3297237) [2](//codeforces.com/contest/280/submission/3313283) in [Ocaml](https://en.wikipedia.org/wiki/Ocaml) which based on a conclusion.