### YuukaKazami's blog

By YuukaKazami, 10 years ago, ,

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
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
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)....

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

• +6

 10 years ago, # |   0 Why sizes of letters are not equal?
•  10 years ago, # ^ |   0 I don't know how to use the editor.. I'm  trying to make it look nicer:)
 9 years ago, # |   -6 Orz...
•  8 years ago, # ^ |   -13 What does it mean? Is it some Chinese abbreviation?
•  8 years ago, # ^ |   0 I've found it myself.. "orz, a posture emoticon representing a kneeling, bowing, or comically fallen over person"
 9 years ago, # |   0 ym WJMZBMR!!!
 9 years ago, # |   0 lovely english.....
 9 years ago, # |   0 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).
•  7 years ago, # ^ |   0 @Martin , Can you pls explain your solution more briefly ?
 » 7 years ago, # |   +1 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?
•  » » 3 weeks ago, # ^ |   0 We don't do that here.
 » 3 years ago, # |   +5 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.
•  » » 3 years ago, # ^ |   +5 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 :)
•  » » » 7 months ago, # ^ |   0 I think you're wrong here. There will be $M*10$ pairs. Consider we have $3$ indices $i, j, k$ for a character, where $i \le j \le k$. If the pair $(i, j)$ is a repeat and also $(i, k)$ is a repeat, then, we don't need to store $(i, k)$. This is because the pair $(i, j)$ has a smaller length and will be processed first after which, the substring starting at $i$ will be deleted. So, $(i, k)$ will never be processed. So, for every position $i$, we need only the closest position to the right $j$, s.t. $(i, j)$ is a repeat, i.e., substring of length $(j-i)$ starting at $i$ = substring of length $(j-i)$ starting at $j$. So, there are only $M*10 \sim N$ pairs, that we need to store.
 » 23 months ago, # |   0 why problem B you increase every t[i] by 1 ?
•  » » 21 month(s) ago, # ^ |   -8 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]
•  » » » 21 month(s) ago, # ^ |   0 Thank you
•  » » » » 21 month(s) ago, # ^ |   0 why ?
 » 21 month(s) ago, # | ← Rev. 2 →   -18 problem b is very good !