Processing math: 100%

Codeforces Round 893 (Div. 2) ABCD Solutions (Java/C++)

A. Buttons

Solution:

Both players will prioritize button cc. So, Anna can win an additional point if and only if cc is odd. Then, it only matters if abab is greater than zero. If it's less than or equal to 0, Anna will definitely lose; otherwise, she will win.

Code:

Java

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

C++

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

B. The Walkway

Solution:

Since he will definitely eat a cookie every d minutes at least, the influence of removing one seller is only between two adjacent sellers.
So, removing a seller ii changes the calculation from si+1sid+sisi1d+1si+1sid+sisi1d+1 to si+1si1dsi+1si1d.
Therefore, we only need to check which seller's removal has a bigger impact.

Code:

Java

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

C++

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

C. Yet Another Permutation Problem

Solution:

Firstly, it's not difficult to realize that there can be at most n2n2 different results.
Assuming there exists x>n2x>n2, the best scenario would be ai=xai=x and ai+1=2xai+1=2x, which ai+1>nai+1>n.

From this, it can be guessed that there are at most n2n2 different results. So, let's try to find a way to construct them.

It's not hard to see that n2n2 must be adjacent to 2n22n2. Because 3n2>n3n2>n.
Similarly, n21n21 must be adjacent to 2(n21)2(n21).
For example, if n=21n=21, then 10 is adjacent to 20, and 9 is adjacent to 18.

Thus, through this method, we can construct up to around n4n4. For example, 20 can be constructed to be adjacent to 6 and 12. But making 5 adjacent to 10 is not obvious, as 10 is already adjacent to 20.
However, it can be observed that 4 doesn't need to be adjacent to 9; instead, it should be adjacent to 24=824=8.
In this way, each number aiai only needs to be adjacent to 2ai2ai.

For n=21n=21, it would be [1,2,4,8,16]+[3,6,12]+[5,10,20]+[7,14]+[11]+[13]+[17]+[19]+[21][1,2,4,8,16]+[3,6,12]+[5,10,20]+[7,14]+[11]+[13]+[17]+[19]+[21]. In simpler terms, it's similar to the Sieve of Eratosthenes algorithm for finding primes.

Code:

Java

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

C++

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

D. Trees and Segments

Solution:

Firstly, considering the data constraints, n2=9106107n2=9106107.

Because the importance of l0l0 and l1l1 is not linear with the increase of a, for instance, l0=1,l1=100l0=1,l1=100 and l0=2,l1=90l0=2,l1=90 versus l0=5,l1=30l0=5,l1=30, the choice would differ as a changes.
For a=1a=1, 11+100=10111+100=101 is optimal, but for a=20a=20, 202+90=130202+90=130 is optimal. For a=100a=100, 1005+30=5301005+30=530 is optimal.

So, if we can calculate the maximum l0l0 for any given l1l1, we can obtain the result within the range of n2n2. In other words, we need to calculate a dp[l1]=max(l0)dp[l1]=max(l0).

The idea pauses here for now.
Obviously, l0l0 can be calculated within nk=n2nk=n2 as the longest contiguous substring of 0s that can be modified at most k times. That is, dpLeft[i][j]dpLeft[i][j] represents the longest contiguous substring for the i-th tree from left to right, modified at most j times.
Similarly, you can maintain a dpRight[i][j]dpRight[i][j] representing the longest contiguous substring for the i-th tree from right to left, modified at most j times.

Now, integrate all the parts together.
It can be considered that the longest contiguous 1s can be enumerated within n2n2.
Suppose the interval being considered is [left,right][left,right], and the number of operations required to change all numbers in any interval to 1 can be maintained as a prefix sum, denoted as count[right]count[left1]count[right]count[left1].
Let remian=k(count[right]count[left1])remian=k(count[right]count[left1]), then dp[rightleft+1]=max(dpLeft[left1][remain],dpRight[right+1][remain])dp[rightleft+1]=max(dpLeft[left1][remain],dpRight[right+1][remain]).

Code:

Java

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

C++

Submission #225689836 - Codeforces
Codeforces. Programming competitions and contests, programming community
DigitalOcean Referral Badge 蜀ICP备19018968号