ivan100sic's blog

User editorial for Codeforces Round #135 (Div. 2)
By ivan100sic, 12 years ago, In English

The contest was well balanced — scores for tasks were very close to standard scores. I hope you will find this editorial useful.

A :: k-String

Count the occurrences of each character. If any character appears a number of times not divisible by K, obviously, there is no solution. Otherwise, form the solution by first making the string B. The string B can be any string with the following property: if some character ch appears q times in the string B, the same character appears q***K** times in the given string. Now, just print that string K times.

B :: Special Offer! Super Price 999 Bourles!

The following observation will help you code the solution:

The largest number smaller than p ending with at least k nines is p - p MOD 10^k - 1 If the result turns out to be -1 , you can not reach a positive number with k or more nines. I will not explain the solution in detail — be careful when coding and have all the task statements in mind.

C :: Color Stripe

There are two cases to consider , when K=2 and when K>2. For K=2 there are only two possible solutions: the string "ABABAB..." and "BABABA..."

For both strings, simply count the number of differences between it and the given string and print a string with fewer differences.

For K>2 , decompose the string into contiguous single-colored sequences. Observe one such sequence. If it has an odd number of characters, say 2m+1, replace m characters with some other character in the following fashion:

AAAAA

becomes

ABABA

It can be observed that by changing less than m characters doesn't remove all pairs of adjacent identical characters. Similarly, for sequences of even length, say 2m characters, observe a character in the original string right after the last character of the observed sequence, and choose a character different from both. Example:

AAAAAAB

becomes

ACACACB

Again, it is sufficient and necessary to change m characters.

D :: Choosing Capital for Treeland

Arbitrarily root the tree at some vertex, say vertex 1. Now, all the edges are oriented either up (towards the root) or down (away from it). We will call upwards oriented edges red, and downwards oriented edges green. Now, with a single depth-first search, for each vertex, calculate its distance from the root (in number of edges) and the number of red edges along the path to the root. Also, count the number of red edges in the entire tree.

Now comes the interesting part: Observe that all edges outside the path from the root to vert should turn green, and those on the path should turn red.

The number of edges that need to be flipped if vert is chosen as a capital is given by:

RedEntireTree - 2*RedOnPath[vert] + RootDistance[vert]

E :: Parking Lot

Use a heap to maintain sequences of empty parking spaces as intervals. The comparison function for such intervals should return an interval which could store a car farthest from any other car, and if there is a tie, it should return the leftmost such interval. When inserting a car, pop the heap, look at the interval, place a car in the corresponding space and push two new intervals onto the heap. When removing a car, you should be able to find the two intervals which end at that car, remove them from the heap and push a new interval which forms when the two merge.

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

Comments Comments (23)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks very much.

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

When removing a car, you should be able to find the two intervals which end at that car.

I think find the element in heap is O(n)...

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

    In fact, you should use balanced tree here(like set in c++ or TreeSet in Java)

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

      Priority_queue is okay

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

        Well, i used a segment tree, so any heap-like implementation is okay.

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

Very nice solution given for problem D. Here is an alternative (but still similar in complexity) solution. If C[i] denotes how many edges need to be flipped so that i becomes capital, we can observe that |C[i] — C[j]| = 1 if there is an edge (i, j). Wether C[i] = C[j] + 1 or C[j] = C[i] + 1 depends on the direction of the edge bettween i and j. Now we have N unknowns, and N — 1 equations between them. By solving C[0] using some method we have all the information that we need. C[0] can be calculated using depth first search starting from node 0. Similary, by depth from search from node 0 we can use the above equations to calculate the rest of C[i]

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

I am getting tle with the above mentioned algorithm. Please sm1 help. Mysubmission — http://mirror.codeforces.com/contest/219/submission/7340082

Thanks.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it 
        for (int i=1;i<n;i++){
        cin>>a>>b;
        temp = ar[a];
        while(temp->next!=NULL){
            temp = temp->next;
        }
        temp->next = new Node(b, 1, 0);

    When you repeatedly follow the next pointer of your node, you have to visit each node along the path until you find one where the next pointer is null. But there are O(n) nodes on this path in the worst case, and you repeat this step n times -- leading to O(n^2) performance.

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

      Thanks for ur comment.

      I corrected it and it got accepted.

      For some time I was making adjacency list in previous way, but now i could insert node in linked list in constant time.

      Here is my submission — http://mirror.codeforces.com/contest/219/submission/7342040

      do you think if there is any better way to create adjacency list?

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

        Glad it worked. Here's how I typically make one:

        struct node
{
    vector<node*> edges;
} nodes[big_number];

...

for (int i = 0; i < number_of_edges; i++)
{
    int a, b;
    scanf("%d%d", &a, &b);
    nodes[a].edges.push_back(nodes + b);
    nodes[b].edges.push_back(nodes + a);
}
        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That is really a nice way.. Thanks for sharing. I would practice with that now.

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

Can someone help me on how to solve 219C using DP ?

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

HELP...!!!! My following solution on DIV 2 C is getting TLE on test case #17. Solved using DP. Can anyone help me out? Can't find out what am I missing.......

My Submission

Thnx.

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

How do I get rid of MLE in my dp solution for div2 problem C ?

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

My dp solution for problem div2 C.
The complexity is $$$O(n*k^2) \approx 338000000$$$, it's quite big but it still pass system tests with time about 1.5 seconds.

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

    and also space complexity is O(n*k) which is roughly 13000000 in worst case how your solution is passing?

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

My rerooting approach for D, with the explanation.

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

"Observe that all edges outside the path from the root to vert should turn green, and those on the path should turn red."

Can anyone please explain why this is true?

The number of edges that need to be flipped if vert is chosen as a capital is given by: RedEntireTree — 2*RedOnPath[vert] + RootDistance[vert]

How has this been derived?

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

    "Observe that all edges outside the path from the root to vert should turn green, and those on the path should turn red."

    I believe this is because we will go upwards from the vert to the root (thus, all nodes must be red on the path), and from the root we will go out to other vertexes (thus, all nodes outside the path must be green).

    The formula can be rewritten as: 

      RedEntireTree — 2*RedOnPath[vert] + RootDistance[vert]
= (RedEntireTree - RedOnPath[vert]) + (RootDistance[vert] - RedOnPath[vert])
=           RedOutsidePath          +            GreenOnPath
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why do all the other paths need to be green?

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

        Green is when the edge is oriented downwards. After you go from vert to root using the red path, now you are at the root, and from the root, you can only go downwards to other vertexes.

        → Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

thanks, edutorial to D was v helpful for me!

→ Reply