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
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"
yes
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).
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?
We don't do that here.
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 does my $$$\tt{Edge}$$$ browser show $$$\text{404 Not Found}$$$ when I click on the link
http://www.ideone.com/dPS5N?For B, I understand basic knapsack but how can I understand the problem as a knapsack? I cannot make the connection between being able to steal item while the clerk is scanning an item -> knapsack.
While the clerk is scanning an item $$$(t_i, c_i)$$$, you can steal up to $$$t_i$$$ items. So, the sum of $$$t_i$$$ of the items you paid for must be at least the number of items you stole. Equivalently, if you increment $$$t_i$$$ by one, the sum of $$$t_i$$$ of the items you paid for must be at least $$$n$$$.
So, your new task is to choose some items such that:
I appreciate the answer but this is flying over my head right now. I think I need to build my intuition up from lower rated dp problems :sob:
Do you see the connection between knapsack and the reformulation I gave at the end of my comment?
I looked at it longer and I can understand from your second sentence how when you increment all the t's by 1, it would turn into a knapsack problem. But now I am trying to understand how to come up with incrementing t's by 1 and why it works.
I can see that you have to make $$$t_i$$$ that are 0 into 1 because items with 0 weight would mess up the calculations and when all your $$$t_i$$$ are equal to 0, logically it makes sense that you would have to take all of them. But when you increment the $$$t_i$$$ (that are >= 1) by 1, I am not sure what to understand what the new value represents. I can see that I have to perform this action because I cannot only increment the $$$t_i$$$ that are equal to 0.
The best I can come up is if the incremented $$$t_i$$$ is 3, I would be able to have 2 items to steal and have bought 1. The cost of the bought item can now be compared to be lowest cost to take 3 items.
editorials sure looked different back then