19.md (3843B)
1 Source: https://codeforces.com/blog/entry/559 2 3 I find that no one write a solution about this contest..So I write one.. 4 5 A. World Football Cup 6 7 I think is' just a problem about writing code 8 9 quickly and correctly.Just follow the statement. 10 11 if you use c++ STL will make you life easier 12 13 B. Checkout Assistant 14 15 First,for every i increase ti by 1..then you will 16 17 see that statement require sum of t of the items 18 19 bigger or equal to n..and their sum of c should 20 21 be minimal..so it's just a 0-1 knapsack problem. 22 23 C. Deletion of Repeats 24 25 First let's generate all repeats.In a repeat,the 26 first number and the middle number must be the 27 same, so we just look at all pair of postion which 28 have same number..Thank to the statement..There 29 are at most O(10N) such pair..And use suffix array 30 to check if each pair can build a repeat...Then 31 just sort all the interval and go through then to 32 get the answer... 33 [http://en.wikipedia.org/wiki/Suffix_array](https://en.wikipedia.org/wiki/Suffix_array) 34 maybe you think suffix array is hard to code..you 35 can use hash and binary search to do the same.. 36 my code here <http://www.ideone.com/N5zPS> 37 38 D. Points 39 First of all,do the discretization.Then the biggest 40 value of x is n,so we can build a Segment Tree to 41 Ask the question "what is the first place from 42 postion x and its value is bigger than y"..if we 43 find such postion we just find the smallest Y-value 44 bigger than y in such postion--it can be done using 45 set's operation upper_bound... 46 [http://en.wikipedia.org/wiki/Segment_tree](https://en.wikipedia.org/wiki/Segment_tree) 47 so the algorithm is clear..For every possible value 48 of x use a set to store all y value in it..And every 49 time the action is "find" or "remove" just change 50 this set and update the Segment Tree..otherwise use 51 Segment Tree to find the answer.. 52 53 my code here <http://www.ideone.com/4iNol> 54 55 E. Fairy 56 It's a interesting problem.If you for every edge, 57 try to remove it and check if it is a bipartite 58 graph..I think it will get TLE..so let's analysis 59 the property of bipartite graph.. 60 [http://en.wikipedia.org/wiki/Bipartite_graph](https://en.wikipedia.org/wiki/Bipartite_graph) 61 After reading it...we know.. 62 It should never contain a cycle of odd length... 63 and it can be 2-colored.. 64 so first build a spanning forest for the graph.. 65 and do the 2-color on it(Tree can be 2-colored). 66 for convenience. 67 Let TreeEdge={all edge in forest} 68 NotTreeEdge={All edge}/TreeEdge 69 ErrorEdge={all edge that two endpoint have the same color..} 70 NotErorEdge=NotTreeEdge/ErroEdge.. 71 First,consider a edge form NotTreeEdge,remove it 72 can't change any node's color..so.. 73 74 if |ErrorEdge|=0 of course we can remove all NotTreeEdge 75 76 if =1 we just can remove the ErrorEdge 77 78 if >1 we can't remove any from NotTreeEdge 79 Now,Let consider a Edge e from TreeEdge.. 80 Let Path(Edge e)=the path in forest between e's two endpoints.. 81 if there is a Edge e' from ErrorEdge that Path(e') 82 didn't go through e..it will destroy the bipartite 83 graph.. 84 if there is a Edge e' from ErrorEdge that Path(e') go through e and there is a Edge e'' from NotErrorEdge that Path(e'') go through e..it will also destroy the bipartite graph.. 85 so now we need to know for every edge,how many such path go through it..it require a data structure... 86 one way is to use heavy-light decomposition then we can update every path in O(LogN^2)... 87 another way is to use Link-Cut Tree..It can do the same in O(LogN).... 88 if you didn't see Link-Cut tree before,you can read this 89 90 [http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf](https://en.wikipedia.org/wiki/Link/cut_tree) 91 or my code..use heavy-light decomposition <http://www.ideone.com/dPS5N>