subscriber's blog

Codeforces Round #854 Editorial
By subscriber, history, 21 month(s) ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +124
  • Vote: I do not like it

Comments Comments (85)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain problem A?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    U are given some activities (n) starting from 1 upto n. Now u are given m other activities which are other than the previous 1-n ,i.e, n+1 to ahead. When a total new activity comes, u have to remove the oldest activity from back and if after sometime existing activity comes, u don't need to remove anything bcz there's already that activity ongoing.... Obviously 1 to n won't be there in the m activities, so we just have to print what activities still exists (-1 if they do) and if they have left the queue then at what time did they...

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use set in this question. Iterate the actions from starting and see if the element is present in set then do nothing if it is not present then you have to remove the last post and element in the set. You can use a counter for knowing which is the last element in the recent field.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I had the same idea and was very surprised with how easy problem F actually was. Like, it's just simple greedy which is easily provable and we don't even need to optimize it with down to $$$O(NlogN)$$$.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I bet that if they placed it as C or D, a lot of people would solve it

      → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +93 Vote: I do not like it

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.me/blog/entry/49691

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    how do we know it's not well known in China too XD?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +60 Vote: I do not like it

      Everything is well known in China, but this is also well known in Croatia as well xD.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I think that one is well known for everyone that you can call an "experienced contestant"

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +58 Vote: I do not like it

      TIL I'm an inexperienced contestant

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Ofc it's not a rule, as some people missed that problem. But for people that actually went around learning these tricks from problems, that's a huge problem that I'd be surprised if more people that were active at around 2017-2019 missed that problem than people that know it.

        Perhaps you're just so good at the basics that you don't look into these weird little tricks.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, to be clear I was being (mostly) sarcastic :) I also wasn't especially active on CF until around 2018 and wasn't regularly participating at a Div. 1 level until 2019, so there are still lots of problems that were standard back then that I just haven't run into :p

          → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Also well known in China, and it is often called "wqs binary search" in China. :)

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Looking through your submission history, I noticed that you received WA with the code from this blog (195181117), but got AC with some additional trick(195185134). Do you know why? I am facing simmilar issue, but I don't undestand why in this problem the typical implementation of this trick seems to fail.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      You can look at the blog for more details. Essentially the first solution doesn't handle some edge cases well and is less numerically stable because of the use of doubles. The second solution handles those better and uses fractions as well.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't notice Neal's comment at first. Thanks

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +43 Vote: I do not like it

Please add the proof of solution of problem C.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "This problem is trivial and the solution is easy to see"

    Is probably enough as an editorial in the opinion of the person that approved that problem.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

      Somehow this is literally the editorial for E.

      We need proofs!

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    1) Suppose there are only one 'a' and one or more 'b' and no other letters are left. If we consider how words are created depending on the location of a, we can see that the optimal is to place 'a' in the center.

    2) Suppose there are one 'a' and one or more 'b' and at least one 'c' are left. If a word starts with 'b' and ends with 'a', the optimal (in this case) is to place the remaining symbols in order from the front. Let's prove this word (say w) is optimal. Let x be a position 'c' is appear in w. Suppose that word does not end with 'a'. Then the word must end with 'b', and in order for the word to be less than w, 'a' must be located between position 1 and position x. (Note that positions 1 through x-1 in w are filled with 'b'.) However, when this happens, the word is smaller than its reverse, which is a contradiction.

    Sorry for my poor English.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I do operation two times not (n+m) times still accepted in E,I don't know why.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Technically 4 because the editorial is referring to filling the y and x as separate conditions. You only need to do it twice, but you don’t know whether to start with the y or x so it’s satisfactory to do it four times to fix orientation. This is because after you fill x or y, if it can be filled it will at most give some new x that also needs to be filled. When it fills x, this will be the last operation given the statements above are true because it will fill every x in each y it added or there would be a gap between the two cities which does not need to be filled. Since it’s doing this on each x in the connected component’s range, it also fixes each y. Same thing vice versa.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

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.
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay, so, after some time I came up with something which could be close to a concrete proof of this solution (or the explanation of the idea behind the tricky step number 6).

    Let's look at the example like aaabbbbcc. First, we would process the 2 equal characters at the start of the string s, after this step our answer string would look like this: a ******* a, where the characters in bold are the most recently added ones and the rest are 7 characters that we still need to figure out.

    Now the 2 most left characters in the sorted string s are not equal. However, for now, we are going to treat them as if they were equal characters. After this step the answer string is going to look like this: ab ***** ba, where the character in bold is the "lesser" character 'a' that we have temporarily replaced. We are going to figure out where that 'a' goes later, for now we just have to remember the position of the substituted character, the replacement character 'b' and the original character 'a'.

    Now we fill our answer string with what's left of the sorted string s: abbbbcc b a. In this case, since the rest of characters in the string is sorted and we have characters that are "bigger" than 'b', our "palindrome" is in a bad spot right now (we were trying to build one, remember): if we were to reverse it, the resulting string would be lexicographically bigger than our current answer, which is not what we want. So, our only hope is to substitute that bold 'b' back to a, resulting in our final answer.

    The step with the filling out the rest of the answer can have 2 total cases:

    • the rest of the string s is the same character, which is equal to our "replacement" character, then we can just pick a character in the middle of the answer and assign it our "lesser" character (ans[s.length() / 2] = first_character_with_no_pair);
    • the rest of the string doesn't consist of only "replacement" characters, and since it is sorted, we have to substitute our "bold" character back.

    This process is similar to what is described in the second point of the C solution in editorial, however, described trick with c times y and break seems to be a little bit out of the blue.

    Let's consider the most "annoying" cases, where the lesser character jumps in to the middle of the answer tmax, strings like abb, abbb, aaabbbbb. You can see, that according to this solution we would get the right corresponding answers: bab, bbab and abbbabba.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +64 Vote: I do not like it

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.me/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!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +56 Vote: I do not like it

Where's H editorial?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Thanks for sharing this, I was losing my head over my solution! I thought of the same but stupidly used dp[t[a[i]] when I should've been using dp[t[a[i]+1] as you mention; kept thinking of ways to get that working, gave up and just solved D1 instead.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share me your submission, please?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      195421246

      key part of the code

          rep(i,0,n) {
      dp[i+1][0] = dp[i+1][1] = min(dp[i][0],dp[i][1]) + cold[a[i]];
      if(i && a[i] == a[i-1]){
        setMin(dp[i+1][1], min(dp[i][0],dp[i][1]) + hot[a[i]]);
      }else if(t[a[i]] != -1){
        setMin(dp[i+1][0], dp[t[a[i]]+1+1][0] + (pres[i-1]-pres[t[a[i]]+1]) + hot[a[i]]);
      }
      t[a[i]] = i;
    }
      → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are genius!!

    → Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +138 Vote: I do not like it

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.

The Issue
What To Do?
How To Implement This?

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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Thanks for explaining so well. Your example helped clear it up for me, I was stuck on the same issue and dropped this idea mid-contest in order to solve D1 in time.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    nevermind got it my solution does not guarantee that all elements are same at the end

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you elaborate a bit more on your DP solution?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I'm not sure if tfg did the same, but I just upsolved it without inclusion-exclusion and I used dp too. I calculated $$$dp_{i,j} = $$$ number of ways to vote if we only use the first $$$i$$$ groups and among the first $$$i$$$ groups $$$j$$$ people voted. To make transitions you want to know two things: how much people will vote for the new group that are also from the prefix, and how much people from the new group will vote for someone who is already on the prefix. In total there are $$$4$$$ loops, so it might look like it's $$$O(n^4)$$$, but $$$\sum_{i=1}^n sum_i*sz_i \leq n^2$$$, so the $$$3$$$ internal loops are actually $$$O(n^2)$$$ and the solution is $$$O(n^3)$$$. You might want to see my code.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    My solution is $$$O(n^2)$$$ or $$$O(n\log^2 n)$$$(using divide and conquer FFT). I use inclusion–exclusion principle and calculate ways under $$$k$$$ fixed invalid votes.

    I'm a little confused with the constraint...

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -32 Vote: I do not like it

Bad problem ABC

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.me/contest/1799/submission/195220905

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually I have an $$$O(N^2)$$$ solution with (quadratic)polynomial convolution, but can be improved to $$$O(NlogN)$$$ with NTT, this is my submission 195224839

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    I think any time there's a question of why bounds aren't higher, the answer is usually that increasing the bounds doesn't make the problem more interesting, just more tedious, so then it's polite to keep it lower. I also solved the problem with inclusion-exclusion, and my code can be easily turned from $$$\mathcal O(n^3)$$$ to $$$\mathcal O(n \log^2 n)$$$ by iterating more precisely over sum of $$$c_i$$$ per team and copy pasting some FFT templates, but that doesn't make the problem more interesting and is not the main idea of the problem imo.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Hi guys you can check video editorial for

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you approach Problem G?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

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

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +55 Vote: I do not like it

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

Code
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    I want to say that your solution is not $$$O(n^3)$$$, actually it's better. It's only $$$O(n^2)$$$.

    Why that's true?

    In calculation of dp, you have 3 loops, the first go from $$$1$$$ to $$$n$$$, the second go from $$$0$$$ to $$$n$$$, but the third doesn't always go to $$$n$$$. It goes from $$$0$$$ to $$$S[i]$$$, and sum of $$$S[i]$$$ overall values of $$$i$$$ is exactly $$$n$$$.

    So the complexity is only $$$O(n^2)$$$.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Oh yes, thanks for mentioning it. I have edited my comment.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you use size_t or other unsigned type for n, then n - set.size() is also unsigned, and subtraction overflows yielding $$$2^{64} - 12$$$.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But I stored n in intwhich is by default a signed container.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        but set.size() is an unsigned int; when you perform an operation with an unsigned and a signed int, the latter casts to the unsigned type

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +39 Vote: I do not like it

Where is tutorial for problems G & H?

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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

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

    If you sorted the string $$$s$$$ then it should be $$$c_0 < c_1$$$ instead of the other way around. Thanks for the explanation.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    (I'm sorry that you're receiving notifications for this reply) Is there any way to follow a comment thread in CF? It'll really help if I could get notified if someone replies with a flow idea to this comment thread. I had to visit this comment a few times today checking for updates, and it's a bit inconvenient. I know I can mark this comment as a favorite, but I'm not sure if that'll notify me of any new updates.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Submission1 Submission2

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

→ Reply
»
20 months ago, # |
  Vote: I like it -10 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Apologies for the necropost, but in case you still want to know, it was because there were some points in the code where the 2**63-1 limit was temporarily exceeded (i.e. by dp+hot and dp+cold). Changing 2**63-1 to 2**63-1-10**9 works, while changing it to 2**63-10**9 does not.

    This addition overflow issue is also why many coders choose their "infinities" to be less than half the maximum value.

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

      I got the answer from conqueror_of_tourist. Anyway , Thank you bro and I appreciate it :)

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

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

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply