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.

Thanks very much.

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

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

Priority_queue is okay

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

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]

good idear～～

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

Thanks.

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.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://codeforces.com/contest/219/submission/7342040

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

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

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

can anybody share a proof or intuition of the solution to problem 219D? Though I have coded it, I am struggling to completely convince myself that this works.

dont know

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

dp【i】【j】=min（dp【i】【j】，dp【i-1】【k】+a【i】-‘A’==j?0:1）,(j！=k)

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.

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

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.

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

My rerooting approach for D, with the explanation.

I am not able to get the perfect solution of prob. A. I am getting wrong answer in test case 10. Please, someone who is willing to share their ac code, it will be very helpful.

104773193 here is my code for prob. A

"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?

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

Why do all the other paths need to be green?

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.