YuukaKazami's blog

By YuukaKazami, 8 years ago, In English,

I find that no one write a solution about this contest..So I write one..

A. World Football Cup

I think is' just a problem about writing code 

quickly and correctly.Just follow the statement.

if you use c++ STL will make you life easier

B. Checkout Assistant

First,for every i increase ti by 1..then you will

 see that statement require sum of t of the items

 bigger or equal to n..and their sum of c should 

be minimal..so it's just a 0-1 knapsack problem.

C. Deletion of Repeats

First let's generate all repeats.In a repeat,the
 first number and the middle number must be the 
same, so we just look at all pair of postion which 
have same number..Thank to the statement..There 
are at most O(10N) such pair..And use suffix array 
to check if each pair can build a repeat...Then 
just sort all the interval and go through then to 
get the answer...
http://en.wikipedia.org/wiki/Suffix_array
maybe you think suffix array is hard to code..you 
can use hash and binary search to do the same..
my code here 
http://www.ideone.com/N5zPS

D. Points
First of all,do the discretization.Then the biggest 
value of x is n,so we can build a Segment Tree to 
Ask the question "what is the first place from  
postion x and its value is bigger than y"..if we 
find such postion we just find the smallest Y-value 
bigger than y in such postion--it can be done using 
set's operation upper_bound...
http://en.wikipedia.org/wiki/Segment_tree
so the algorithm is clear..For every possible value 
of x use a set to store all y value in it..And every 
time the action is "find" or "remove" just change 
this set and update the Segment Tree..otherwise use 
Segment Tree to find the answer..

my code here http://www.ideone.com/4iNol

E. Fairy
It's a interesting problem.If you for every edge, 
try to remove it and check if it is a bipartite 
graph..I think it will get TLE..so let's analysis 
the property of bipartite graph..
http://en.wikipedia.org/wiki/Bipartite_graph
After reading it...we know..
It should never contain a cycle of odd length...
and it can be 2-colored..
so first build a spanning forest for the graph..
and do the 2-color on it(Tree can be 2-colored).
for convenience.
Let TreeEdge={all edge in forest}
NotTreeEdge={All edge}/TreeEdge
ErrorEdge={all edge that two endpoint have the same color..}
NotErorEdge=NotTreeEdge/ErroEdge..
First,consider a edge form NotTreeEdge,remove it 
can't change any node's color..so..

if |ErrorEdge|=0 of course we can remove all NotTreeEdge

if =1 we just can remove the ErrorEdge

if >1 we can't remove any from NotTreeEdge
Now,Let consider a Edge e from TreeEdge..
Let Path(Edge e)=the path in forest between e's two endpoints..
if there is a Edge e' from ErrorEdge that Path(e') 
didn't  go through e..it will destroy the bipartite 
graph..
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..
so now we need to know for every edge,how many such path go through it..it require a data structure...
one way is to use heavy-light decomposition then we can update every path in O(LogN^2)...
another way is to use Link-Cut Tree..It can do the same in O(LogN)....
if you didn't see Link-Cut tree before,you can read this

http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf
or my code..use heavy-light decomposition 
http://www.ideone.com/dPS5N

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why sizes of letters are not equal?
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I don't know how to use the editor.. I'm  trying to make it look nicer:)
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it
Orz...
  • 7 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    What does it mean? Is it some Chinese abbreviation?

    • 7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've found it myself.. "orz, a posture emoticon representing a kneeling, bowing, or comically fallen over person"

7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
ym WJMZBMR!!!
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
lovely english.....
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
As a matter of fact, CF19E does not need a data structure, since we need not update it on-line. We can do it off-line with an easier way.
Path u-v can be divided to u-lca and v-lca, so add u, add v, and decrease lca by two. and that works.
More easily, we can use dfs-tree, to avoid looking for lca.
So the algorithm is O(n + m).
  • 5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @Martin , Can you pls explain your solution more briefly ?

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Anyone know if D can be solved using an augmented (self-balancing) binary search tree? To me, it does but I can't get a working solution. Any thoughts?

»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for the solution!

In problem C, I think there are N*45 such pairs. // C(10,2)=45 Because you want not only the adjacant pairs. We need no suffix array nor hash. Just brute-force to compare the substrings is enough, thanks to the "no more than 10 times" constraint.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sorry this should be M*45, where M is the number of different letters appeared. So ~ N*4.5 in worst case. Thanks kokosha for pointing out :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why problem B you increase every t[i] by 1 ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    suppose the assistant is processing the i_th item , then you can pick t[i] items with you + that item which the assistant is processing !

    so number of items we can take away with us is 1+t[i]

»
2 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

problem b is very good !