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 t_{i} 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

What does it mean? Is it some Chinese abbreviation?

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

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

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

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?

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.

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

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.

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

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]

Thank you

why ?

problem b is very good !