codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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>