Can someone please explain problem A?

I think F can be solved in $$$O(n*log(n))$$$. My idea is probably different from the author's one, and I will try to improve the code.

Edit: tutorial on $$$O(N*log(N))$$$ solution: link

F can be trivially solved in $$$O(n \; log^2\; (Wn))$$$ by simply using linkret trick, well known in Croatia (yes, not China :P).

https://codeforces.net/blog/entry/49691

I’m so mad, I solved E 5 mins after contest ended ;(. I can’t solve anything in contest.

Please add the proof of solution of problem C.

Can’t E be solved faster by just checking where the two cities would intersect and then connecting cities in each x and y?

Here's how I solved C:

1. Since we can choose any arbitrary permutation of symbols in s, we might just as well sort it.
2. Because we need such a tmax that is bigger than it's reversed counterpart we are going to construct our "almost" palindrome string that it's first half is only slightly bigger than the reversed second half.
3. Iterate over first 2 characters in s, if the characters are equal — add each to the prefix and suffix of our answer string. If after this step we have only one or no more characters left in s — we are happy because we have our palindrome which is the answer.
4. Otherwise, first time we encounter an unequal pair of characters, pretend that they are equal too and add each one of them to the prefix and suffix of our answer again (we have to remember the original character, the substitute one and the position of the replacement at the suffix of our answer).
5. Fill in the rest of our answer with what's left of the sorted string s.
6. Now we have to find the optimal position for our original character which we have substituted (the lesser one), it's either the original position, or s.length() / 2 if the condition that tmax >= reverse(tmax) still holds.

I have found an $$$O(N*log(N))$$$ amortized solution to F. Code: 195201483

The idea is simple. First, we sort the array in decreasing order.

$$$O(N^2)$$$: We iterate over to how many elements from the beginning we will apply both operations. After that, we know that there are $$$n-both$$$ elements to which we can apply at least one operation. We take $$$k1-both+k2-both$$$ greatest elements after $$$both$$$ taken elements from the array. Now, we apply operation 1 to all of them. We must apply $$$k2-both$$$ operations of type 2, so we choose $$$k2$$$ elements with biggest delta $$$cost2(a_i)-cost1(a_i)$$$ where $$$cost1$$$ and $$$cost2$$$ are functions that return an integer after applying operation 1 and 2 respectively.

$$$O(N*log(N))$$$: note that there are not a lot of changes if we calculate answer for some $$$both$$$ and $$$both+1$$$. We can use ordered_set of deltas $$$cost2(a_i)-cost1(a_i)$$$ in order to maintain to which numbers we apply 1 or 2 operation.

I believe I have a solution to E in $$$\mathcal{O}(nm)$$$ which also solves the problem for arbitrarily many cities/components (not just two). It consists of two simple steps:

1. Find the minimum bounding rectangle of the cities, and let this be the preliminary answer. We will try to cut down on this answer by chipping away at the corners.
2. Add each of the four corners of the bounding rectangle to a queue. While there exists a corner which is not part of a city in the original grid, we remove that corner and add any new corners created to the queue. Repeat until no removable corners are left. I claim this is the minimum connected convex cover of the cities (convexity is the property which is equivalent to the Manhattan distance rule), so we are done.

Just be careful not to accidentally disconnect the cities again when removing corners, and you should be good. Here's a link to my submission: https://codeforces.net/contest/1799/submission/195179223

I haven't thought about a rigorous proof of correctness yet, so I welcome any hacks to my solution if any such hacks exist!

Where's H editorial?

Another way to solve D2 1799D2 - Hot Start Up (hard version), define dp[i][same cpu with i-1 ?] = min time

if use cold, then dp[i][true/false] = min(dp[i-1][true],dp[i-1][false]) + cold[a[i]]

if use hot, let t[a[i]] be the a[i] last exist time.

• if t[a[i]] + 1 == i, dp[i][true] = min(dp[i-1][true],dp[i-1][false]) + hot[a[i]]
• if t[a[i]] + 1 < i, then t[a[i]] + 1..i-1 is using same CPU, so that dp[i][false] = dp[t[a[i]]+1][false] + sum(cold/hot[t[a[i]]+2..i-1]) + hot[a[i]], the middle sum can be precaculate with prefix sum,

in this way there is no need for segtree

I have a different $$$O(n + k)$$$ solution for the problem 1799D2 - Hot Start Up (hard version).

Let's say we currently need to run program $$$x$$$ and we want to run it in $$$hot_x$$$ seconds. To do this, we can use the same CPU that we used for the previous $$$x$$$, and use the other CPU for every program between these two. If the index of previous $$$x$$$ is $$$i$$$ and current $$$x$$$ is $$$j$$$, this means $$$i$$$ and $$$j$$$ will have the CPU 1, and every program in $$$[i + 1, j - 1]$$$ will have the CPU 2, or vice versa.

So, if we know the answer to finish the first $$$i$$$ programs we can calculate the answer for $$$j$$$. To calculate the amount of time needed to use the other CPU for the tasks $$$[i + 1, j - 1]$$$, we can use prefix sums where the $$$kth$$$ program takes $$$cold_k$$$ seconds if it's different from the previous program and $$$hot_k$$$ seconds otherwise.

However, there is something we're missing here. Please try to find it on your own.

             i          j
..., y, ..., x, y, ..., x, ...
     2   1   1  2   2   1

Here is my implementation: 195175862

I tried to write it as clear as possible. However, I was in contest so if there is a mistake I'm sorry.

Please let me know if you have any questions or if there is any mistake.

what is wrong with this submission? failing on test case 8

https://codeforces.net/contest/1799/submission/195211040

I also have a different O(n + k) solution for D2 with a very simple implementation: 195175038

If you are interested, you can watch my video: https://www.youtube.com/watch?v=oOyPQL16x1M

What's intended for problem G? I solved it by counting it directly using DP, but everything that I know about solutions like this points to this dp being O(N^4), is it possible that it is O(N^3)?

https://codeforces.net/contest/1799/submission/195217087

Edit: I think that I managed to prove it being O(N^3). Basically for the transition at the first state being "i", we have at most (a[i] + 1) * (b[i] + 1) transitions. The sum of a[i] * b[i] is at most O(N^2). For each i, dp[i][j] has at most O(N) valid j's, so it ends up being O(N^3).

For E, you could do the “filling” as stated in the editorial last and find the intersection point first. You can just put a # there and then fill it. 195194226

Why is the title of question B in the English answer in Russian?

Bad problem ABC

Why is the constraint of the G problem so small? I thought this problem could be solved using formal power series in $$$\mathrm{O}(N\log^2N)$$$.

my submission:https://codeforces.net/contest/1799/submission/195220905

Hi guys you can check video editorial for

Problem A , Problem B, Problem C, Problem D here — https://youtu.be/AGIrdT_cQuY

I think the solotion for E maybe $$$O(nm)$$$?

Actually, we can use $$$2$$$ times filling operation to make a connected component meet the requirements.

Here's my submission.

How do you approach Problem G?

Passed E with $$$O(nm^4)$$$ and some Chinese kung fu(small constant) again! Can it be hacked?

Link: https://codeforces.net/contest/1799/submission/195236064

Can anybody explain to me why my code won't give a correct output for D1? I'm stuck on it for hours and can't convince myself why it is wrong. my submission for D1

E,How to prove (i1,j1),(j2,j2) any Manhattan shortest path is right

In f, why can’t just pick k1 biggest elements to apply halve, then pick k2 biggest elements to apply subtract?

Here's how I solved problem G.

In such problems with some restrictions, using inclusion-exclusion often helps us. In this problem, we have the condition that people cannot vote for someone from the same team.

Suppose $$$s[i]=\sum_{j=1}^{i} c_j$$$, where $$$s_0=0$$$.

First of all, let's see what valid voting looks like. Assume that we have put $$$n$$$ boxes such that number $$$i$$$ is written on the boxes at positions $$$s_{i-1}+1$$$ to $$$s_i$$$ from the left. Notice the boxes having the same numbers are indistinguishable. Suppose $$$b_i$$$ is written on the $$$i-$$$th box from the left. Consider a permutation $$$p$$$ of length $$$n$$$ such that $$$p_i$$$ cast his vote in the $$$i-$$$th box. In a valid voting, $$$p_i$$$ and $$$b_i$$$ should not belong to the same team.

So our restriction is that $$$p_i$$$ and $$$b_i$$$ should not belong to the same team.

Suppose $$$dp[i]$$$ gives the number of permutations $$$p$$$ such that $$$p_j$$$ and $$$b_j$$$ belong to the same team at atleast $$$i$$$ indices.

Now calculating $$$dp[i]$$$ is easy. Suppose set $$$S_t$$$ denotes the players of team $$$t$$$. Assume $$$V(S_t)=\sum_{x \in S_t} c_x$$$. So there are $$$V(S_t)$$$ boxes containing the number of team members $$$t$$$.

How many ways are there to cast a vote, such $$$l$$$ people from team $$$t$$$ cast their votes in $$$l$$$ boxes belonging to people from the same team? It is $$$\binom{|S_t|}{l} \cdot \binom{V(S_t)}{l} \cdot l!$$$. Let us denote this by $$$W(S_t,V(S_t),l)$$$. How to get this? First, we decide which $$$l$$$ people out of $$$S_t$$$ to take. We get $$$\binom{|S_t|}{l}$$$ for that part. We must select $$$l$$$ boxes out of $$$V(S_t)$$$ boxes. We get $$$\binom{V(S_t)}{l}$$$ for that part. Now we can permute these $$$l$$$ people in any way, as all $$$l!$$$ permutations satisfy our condition. We are not focussing on the remaining $$$S_t-l$$$ people right now.

So $$$dp[i]=(n-i)! \cdot \Pi_{t \in T} W(S_t,V(S_t),f_t)$$$, where $$$T$$$ denotes the set of available teams and $$$\sum_{t \in T} f_t = i$$$. How to get this? First of all, according to our definition of $$$dp[i], $$$ atleast $$$i$$$ people should vote for people from the same team. $$$\Pi_{t \in T} W(S_t,V(S_t),f_t)$$$ gives us the number of ways such that exactly $$$i$$$ people vote for people from same team. Now $$$n-i$$$ people are left. They can cast their vote without any restriction. Note that $$$n-i$$$ boxes are left. So we can permute $$$n-i$$$ people over $$$n-i$$$ boxes. Thus we get $$$(n-i)!$$$ for this part.

Suppose $$$ans[i]$$$ gives the number of permutations $$$p$$$ such that $$$p_j$$$ and $$$b_j$$$ belong to the same team at exactly $$$i$$$ indices. Now $$$ans[i]=dp[i]-\sum_{j=i+1}^{n} \binom{j}{i} \cdot ans[j]$$$. Now how to get this? So $$$dp[i]$$$ gives us the number of permutations for all atleast $$$i$$$ indices. We need to remove the permutations in which more than $$$i$$$ people vote for people from the same team.

Suppose $$$d$$$ is a permutation of length $$$n$$$ such that $$$d_k$$$ and $$$b_k$$$ belong to the same team at exactly $$$j$$$ indices. How many times would we have counted $$$d$$$ in $$$dp[i]$$$? We would have counted it $$$\binom{j}{i}$$$ times. So we got $$$\sum_{j=i+1}^{n} \binom{j}{i} \cdot ans[j]$$$ this way.

Are we done? Not yet. Did you notice that the boxes with the same numbers are indistinguishable?

We would have overcounted.

So if $$$final[i]$$$ denotes the number of votings such that exactly $$$i$$$ person(s) vote person(s) from same team, $$$final[i]=\frac{ans[i]}{\Pi_{i=1}^{n} c_i}$$$.

Our answer is just $$$final[0]$$$.

Time complexity is $$$O(n^2)$$$(thanks to AbdelmagedNour for pointing it out).

void solve(){ 
    ll n; cin>>n;
    vector<ll> c(n+5),t(n+5);
    for(ll i=1;i<=n;i++){
        cin>>c[i];
    }
    for(ll i=1;i<=n;i++){
        cin>>t[i];
    }

    vector<ll> S(n+5,0),V_S_t(n+5,0);
    for(ll i=1;i<=n;i++){  
        S[t[i]]++;    
        V_S_t[t[i]]+=c[i];
    }

    vector<ll> dp(n+5,0);
    dp[0]=1;
    for(ll i=1;i<=n;i++){
        vector<ll> adp(n+5,0);
        for(ll lft=0;lft<=n;lft++){
            if(dp[lft]==0){
                continue; 
            }
            for(ll cur=0;cur<=S[i];cur++){
                ll ways=(nCr(V_S_t[i],cur,MOD)*nCr(S[i],cur,MOD))%MOD;
                ways=(ways*fact[cur])%MOD;  //ways correspnd to W(S_t,V(S_t),cur)
                adp[lft+cur]=(adp[lft+cur]+ways*dp[lft])%MOD;
            }
        }
        swap(dp,adp); 
    }
    for(ll i=0;i<=n;i++){
        dp[i]=(dp[i]*fact[n-i])%MOD; 
    }

    vector<ll> ans(n+5,0);
    for(ll i=n;i>=0;i--){
        ans[i]=dp[i];
        for(ll j=i+1;j<=n;j++){
            ans[i]-=nCr(j,i,MOD)*ans[j];
            ans[i]%=MOD; 
        }
        ans[i]=(ans[i]+MOD)%MOD;
    }
    
    vector<ll> final(n+5,0);
    for(ll i=0;i<=n;i++){
        final[i]=ans[i];
        for(ll j=1;j<=n;j++){
            final[i]=(final[i]*inv_fact[c[j]])%MOD; 
        }
    }
    cout<<final[0];
    return;                             
}                

My doubt is related to problem A. In sample test case number 8. There are 16 unique new posts. And in my code I printed "-1" n-set.size() times (4-16 times which actually should not print "-1" at all). But it is giving TLE. When I printed the value n-set.size() in my terminal. It prints the value 18446744073709551604. Shouldn't it print -12 ?

can someone elaborate on why we pick the smallest and largest elements greedily at each step in problem B

Where is tutorial for problems G & H?

I found C to be a lot more intuitive when solved recursively.

My idea was first, sort the string lexicographically from least to greatest. Then, iterate over every 2 characters.

$$$s = c_0 c_1 \dotsc c_n$$$

Let $$$f(x)$$$ return the minimum of $$$\text{max}(x,\text{reverse}(x))$$$ (in other words, the problem statement; we want $$$f(s)$$$ )

Let our answer $$$a$$$ be an empty string for now. If $$$c_0 = c_1$$$, then it's clear that $$$a = c_0 \underbrace{\dotsc \dotsc \dotsc \dotsc}_{\text{remaining characters}} c_1$$$ minimizes the lexicographic maximum because any other arrangement would have one orientation be clearly greater. For example, if $$$s = aabbb$$$ then placing any character on the ends other than $$$a$$$ would be worse than just placing $$$a$$$ on both ends.

So, the problem now recurses, we need to find the minimum of $$$\text{max}(c_2c_3\dotsc c_n,c_nc_{n-1}\dotsc c_2)$$$ to fill in the remaining characters of $$$a$$$, aka $$$f(c_2c_3\dotsc c_n)$$$

So, our answer in this case would simply be $$$f(s) = c_0 + f(c_2c_3\dotsc c_n) + c_1$$$, where $$$+$$$ is string concatenation.

Now, if $$$c_0 > c_1$$$, then we have two choices. We can either have

Case 1. $$$a$$$ = $$$c_1 c_2 c_3 \dotsc c_n c_0$$$, because $$$\text{max}(a,\text{reverse}(a)) = a$$$

Case 2. $$$a$$$ = $$$c_1c_3c_4 \dotsc c_0 \dotsc c_nc_2$$$

I claim that case 2 will only be better if and only if there are exactly two different letters left and $$$c_1 = c_2$$$. Let's take an example $$$s_1 = abbbbb\dotsc b$$$

We can write case 1 as $$$a_1 = bbb\dotsc ba$$$, and case 2 as $$$a_2 = bb\dotsc a \dotsc b$$$

Let's look closely as my claim for case 2 being better than case 1.

$$$c_0 > c_1$$$, only two types of letters, and $$$c_1 = c_2$$$.

This immediately tells us that $$$c_0$$$ is the only letter of its kind. If it wasn't, then $$$c_0$$$ can't be greater than $$$c_1$$$. We can also deduce that there are at least two letters of the second kind, since $$$c_1 = c_2$$$ (we assume $$$c_2$$$ exists in this context).

Let's call $$$c_0 = a$$$ and $$$c_1 = c_2 = \dotsc = c_n = b$$$ to make things a bit more clear.

If we use up our only $$$a$$$ and delegate it to the back of our answer, then we won't be able to use it anywhere else (this should be obvious, since we only have 1 $$$a$$$, we should treasure it). $$$\text{max}(c_0 c_1 \dotsc c_n,c_n c_{n-1} \dotsc c_0)$$$ will just be the side starting with $$$b$$$, and our $$$a$$$ will only be in use at the end. So our string in case 1 will just end up looking like $$$bbbbb\dotsc bbba$$$

We can clearly do better. Since $$$\text{max}(c_0 c_1 \dotsc c_n,c_n c_{n-1} \dotsc c_0)$$$ is going to start off with a $$$b$$$ anyway, why not just place $$$b$$$ on both sides and use our precious $$$a$$$ when it really counts. Well, we get one shot with using it and we want to put it in the best spot such that no matter if the string is reversed, it'll be as close to minimum as possible. If we decide to place our $$$a$$$ early up (suppose $$$bbbabbbbbbb\dotsc b$$$), then it's clear that $$$\text{max}(a_1,\text{reverse}(a_1))$$$ will just be $$$bbbbbbbabbb$$$, which is definitely far from the smallest we can do.

Seeing that we want to minimize the worst that we can do, it makes sense to place our $$$a$$$ smack dab in the middle, so that no matter whether the string is reversed, it won't be significantly worse than our original. $$$f(s_1) = \underbrace{bbbb\dotsc}_{\lceil{\tfrac{s_1\text{.size()} - 1}{2}}\rceil} \underbrace{a}_{1} \underbrace{bbbb\dotsc}_{s_1\text{.size()} - 1 - \lceil{\tfrac{s_1\text{.size()} - 1}{2}}\rceil}$$$

195387468

Turns out H is just basic dynamic programming over a tree's edges in $$$O(N \cdot 3^K)$$$. For each edge with direction, which defines a subtree, we find the number of ways to assign a subset of the $$$K$$$ operations to some edges in its subtree, then we find the number of ways to assign all $$$K$$$ operations for each possible root of the final subtree. Merging two such DP rows for two edges from the same vertex takes $$$O(3^K)$$$, and if we want to assign an operation to a specific edge, it just has to come after all operations "below" it, so accounting for that takes $$$O(K \cdot 2^K)$$$.

Auto comment: topic has been updated by subscriber (previous revision, new revision, compare).

Since F was tagged with flows, can someone explain their flows solution? Curious which insights from the editorial solution (if any) are needed to make it work.

Can someone help where did my code/logic go wrong in D1 submission 195189579

Is $$$sz_v$$$ in solution H means the size of the subtree after removing parts appeared in current mask? If it stands for the size of the subtree, then there could be some operation-valid edges missed(consider this case: edges:{{1, 2}, {1, 4}, {2, 3}, {4, 5}, {5, 6}}, s:{5, 4, 2}, where edge{1, 4} can be removed as operation 3, yet neither $$$n - sz_4$$$ nor $$$sz_4$$$ is 2)

Submission1 Submission2

Can someone explain the difference in the complexity of the two codes? Thanks.

In problem D1 , I've made several submissions but all of them received TLE and here is one of them TLE.

But when I just changed the variable MLong from (2**63-1) to (2**62-1) , it was accepted .
I usually make MLong assigned to (2**63-1) since it's equivalent to sys.maxsize but I dont't know why it gives TLE .
Is that because of using of Big integers in python or another issue ?

Ugly alternative solution to problem F (but easier to prove?):

• For the block of elements $$$\geq 2b$$$ (in increasing order), it's optimal to use both operations $$$1$$$ and $$$2$$$ on a suffix.
• For the block of elements in $$$[b+1, 2b-1]$$$, it's optimal to use operation $$$1$$$ on a suffix, and operation $$$2$$$ (in order of priority) on a suffix of the remaining elements, and on a suffix of the whole block.
• For the elements $$$\leq b$$$, it's optimal to use operation $$$2$$$ on a suffix, and operation $$$1$$$ on a suffix of the remaining elements. Moreover, it's never optimal to operate on elements $$$\leq b$$$ if you can still operate on elements $$$\geq 2b$$$.

So, you can iterate over the number of moves of both types applied to the block $$$[b+1, 2b-1]$$$, and the rest is uniquely determined.

AC submission: 206143039

b can be solved with log(max(a[i]))*nlogn

For D1, Why does this give TLE? Submission: my_submission