Codeforces Round #715 (Div. 2) ABCDE Solutions

A. Average Height

Solutions:

Put all odd number together. And then put all even number together.

Code:

Submission #113257892 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. TMT Document

Solution:

Greedy. Firstly, let's count the number of M as count_m. And we mark first count_m T as leading T (the first T in TMT). And mark remained T as ending T (the last T in TMT).

Scan the string once.

  • If we meet a leading T, then count_first++.
  • If we meet a M, then count_first--;count_m--;count_last++.
  • If we meet a ending T, then count_last--.

In this process, all these three counts can't less than 0. And after this process, all these three should be 0.

Code:

Submission #113257923 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. The Sports Festival

It is a normal DP problem. We maintain the segment state. After sorting, just look at the smallest sum for a segment.

Codeforces Round #715 The Sports Festival - DP
Solution:Sort $a$ first.We can easily find that on any day, the members inside must be a continuous segment of $a$.
See more details

D. Binary Literature

Simple structure problem. Find the proof for the existence of the answer first. And based on the proof, the solution can be given almost immediately.

I forgot to find the longest common sub-sequence during the contest. After the contest, I thought about it again. And I found that: it's easier to build based on the number of 0 and 1 by brute force.

Codeforces Round #715 Binary Literature - Construction
Solutions:It is very simple to prove that the string which length is 3n can be obtained.Let’s get two string which length is 2n, one is 000000, another one is 111111.

E. Almost Sorted

A little complex. Can split to two parts for this problem.

One part is the preprocessing of all the possibilities in the permutation of length $n$.

The second part is to construct the result based on the number of all the permutations.

The logic is a bit complicated, and you can think of a solution if you think about it.

Codeforces Round #715 Almost Sorted - DP+Construction
Solution:Generally, Get the total number of almost sorted permutations of length $l$ by DP. And continuously split $n$ and $k$ into sub-DPs.
See more details
Show Comments
DigitalOcean Referral Badge