YuukaKazami's blog

Code Force Beta Round 19 Solution
By YuukaKazami, 14 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

Comments Comments (21)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why sizes of letters are not equal?
→ Reply
  • 14 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:)
    → Reply
13 years ago, # |
  Vote: I like it -6 Vote: I do not like it
Orz...
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    What does it mean? Is it some Chinese abbreviation?

    → Reply
    • 13 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"

      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
ym WJMZBMR!!!
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
lovely english.....
→ Reply
13 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).
→ Reply
»
12 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?

→ Reply
»
8 years 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.

→ Reply
  • »
    »
    8 years 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 :)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why does my $$$\tt{Edge}$$$ browser show $$$\text{404 Not Found}$$$ when I click on the link http://www.ideone.com/dPS5N?

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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:

    • the sum of their $$$t_i$$$-s is at least $$$n$$$;
    • the sum of their costs is minimized.
    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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:

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you see the connection between knapsack and the reformulation I gave at the end of my comment?

        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

editorials sure looked different back then

→ Reply