zltzlt's blog

Codeforces Round 968 (Div. 2) Editorial
By zltzlt, history, 3 weeks ago, In English

Thank you for your participation!

Rating Predictions

2003A - Turtle and Good Strings

Hint
Solution
Code

2003B - Turtle and Piggy Are Playing a Game 2

Hint
Solution
Code

2003C - Turtle and Good Pairs

Hint
Solution
Code

2003D1 - Turtle and a MEX Problem (Easy Version)

Hint
Solution
Code

2003D2 - Turtle and a MEX Problem (Hard Version)

Hint
Solution
Code

2003E1 - Turtle and Inversions (Easy Version)

Hint 1
Hint 2
Solution
Code

2003E2 - Turtle and Inversions (Hard Version)

Hint
Solution
Code
Bonus

2003F - Turtle and Three Sequences

Hint 1
Hint 2
Solution
Code
  • Vote: I like it
  • +112
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +136 Vote: I do not like it

ProofByACForces :)

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Proof by magic :)

    → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Problem d2

    for (int u = k; ~u; --u) {
	f[u] = u;
	for (int v : G[u]) {
		f[u] = max(f[u], f[v]);
	}
	if ((int)G[u].size() >= 2) {
		t = max(t, f[u]);
	}
}

    can any one explain the why this if statement is used to find max and how we will using it. I dont get the idea of why we storing.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I created video editorial for D1 and D2

      Note: This is not a detailed video editorial. Instead, I walk you through my thought process using which I arrived at the solution. Use it as a supplement to the official editorial.

      Update: I also added commentary for the DP Mindset require to solve the easy version of F.

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Bang on whatta explaination realy, but still I miss the fact what with the if statement. If you free pm me lets discuss this approach more thoroughly

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

        great as always .

        → Reply
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for fast editorial.

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

Thanks for the amazing contest :) What topics should I learn To solve D2?

→ Reply
»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

i panicked and got 2 WAs on A, and then got 2 unnecessary WAs on D1 with some spaghetti code. fml

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

    I found problem A very easy to misread as well. I wish the sample tests were better.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Same here, i didn't read For all i < j

      → Reply
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

very nice problem set.

enjoyed solving problem $$$D$$$.

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

    the worse case of input is already O(n^2)? Is my understanding wrong?

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

      if you read the problem statement it clearly says something along the lines of "sum of all l[i] across all testcases does not exceed 2e5"

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

Amazing contest and GREAT IDEAs !!!

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

In my solution to F, the probability of not obtaining the optimal solution is $$$(\dfrac{5!-1}{5!})^{600} = 6 \cdot 10^{-3}$$$ which is actually not very good. But there are only 65 tests so I passed pretests :)

Upd: Passed System test, seems that I'm lucky :)

→ Reply
»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

In problem C solution:

Begin by placing x−y instances of the most frequent character at the start.

Why is this optimal? Why not just alternate most frequent character not only with the second most frequent, but with others as well? The rest is obvious but this part is just an assumption basically.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Going further, does the order of frequencies really matter? Don't we just need to alternate characters in lexicographical order until there are no more left?

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

      that's what i submitted and it got AC, and i still dont know why:)

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

        Me neither. I just followed my instincts. xD

        → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      This does indeed work, because consider this algorithm:

      At the first position place any character. At the $$$i$$$-th position place any character that is different from the one that you placed at $$$i-1$$$-th position. This algorithm will stop only if you exhausted all characters, or if you have left only characters of one kind $$$c$$$. Then place all the remaining $$$c$$$'s at the end.

      In this way you will have at most 1 segment of the same characters of length more than 1 (at the end). I think this is the same result the editorial solution gets.

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

    I tried alternate most frequent character with all others, it passed pretests.

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

    It's not so hard. There's something much easier than this solution.

    Just sort the string then print them in an order like $$$1,n,2,n-1,3,n-2,\dots$$$, and that's all.

    But I just can't prove it.

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

      nice solution.

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

      I did the same thing. I wasn't too sure about my solution so I proved it and that made me submit the problem after one hour.

      I guess it works because you don't actually care too much about the characters themselves, but only about the changes.
      Define a change as the number of $$$i$$$ such that $$$s_{i}\neq s_{i+1}$$$.
      - If in a given substring you only have zero changes, then the first character is equal to the last and that is good.
      - If you have only one change then your substring looks like "aa...aabb...bb". Let $$$i$$$ be the only change, the only index such that $$$s_{i}\neq s_{i+1}$$$, you have that $$$s_{i}=s_{l}$$$ and $$$s_{i+1}=s_{r}$$$ (where $$$l$$$ and $$$r$$$ are the first and the last character of the substring), so $$$(l,r)$$$ isn't a good pair.
      - If there is more than one change it's good. If there are three or more different type of characters you can obviously find a change such that $$$s_{i}\neq s_{l}$$$ or $$$s_{i+1}\neq s_{r}$$$. If it is made only of two type of characters the substring has a block of characters of the first type, then a block of the second type, a block of the first, and so on... So if you take look at the second change you'll have that $$$s_{i}$$$ is of the second type and is different from $$$s_{l}$$$, and $$$s_{i+1}$$$ is of the first type so it is different from $$$s_{i}$$$. Note that it doesn't matter if $$$s_{i+1}=s_{r}$$$ because you know that $$$s_{i}\neq s_{l}$$$.

      Now, sorting the string as you said is optimal because you minimize the number of $$$i$$$ such that $$$s_{i}=s_{i+1}$$$ so you maximize the changes in every substring. And in particular there will be zero such indices unless there is a type of characters which occurs more than $$$\frac{n}{2}$$$ times, case in which you can't do better.
      In this sorting every substring will have one change only if the size of the substring is 2. Here you know you can't do better because in a substring with only two elements you can have zero or one changes, but having zero instead of one won't increase the number of good indices because regardless of the sorting, there are $$$x$$$ characters of that type and the substring with that character in the first and last position will always be $$$\frac{x(x-1)}{2}$$$.

      Hope that helps :))

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        I don't think this is true. Using order 1, n, 2, n-1, ... does not maximize the changes.

        Imagine the sequence 1, 2, 2, 2, 3. Using the order 1, n, 2, n-1, ... we would get 1, 3, 2, 2, 2. This is two changes. We can get five changes with the sequence 2, 1, 3, 1, 2.

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

      Doesn't this not work for initial string "baa" which makes the new string "aba" which has less pairs than the original?

      → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    OK, so I've thought about it, here's a better proof at least for me to understand. Let's just alternate characters, it's optimal because of the sum we need to minimize. If the most frequent character appears less than n/2 times in the string then we can alternate easily. Otherwise we can cap the most frequent character occurrence by n/2 and build an alternating string, but then we will have a block of the same characters left that we need to insert in the string somewhere. We can insert it only at the beginning or the end, because there it's going to be calculated in the sum only once.

    Pretty good problem actually, if you think about it, thanks.

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

Super fast Editorial...

btw problems were good <3

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

Anyone has a solution for F without using randomization? I tried to using some kind of meet in the middle, but it's too hard to merge the answer

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    Here's a deterministic solution:

    Let's refer to elements with the same $$$b_i$$$ as a "class".

    Loop through all possible values of $$$2^{nd}$$$ and $$$4^{th}$$$ numbers and check the validity of the pair. Now, we have three more elements to fill: the one to the left, between two numbers, and the one to the right. For each of these, we know the range of possible values of $$$a$$$.

    Notice that if we consider the five best classes of elements of a set (with the highest maximum cost of elements belonging to that class), then the best element to select in this set will always be among those 5 (the other ones can ban at most 4 classes). So, we need the five best classes for all prefixes with $$$a$$$ bounded from above by the next element, and for all suffixes with $$$a$$$ bounded from below by the previous element. This can be precalculated easily in $$$O(n^2)$$$.

    The interesting part is what to do with the middle elements (they have both upper and lower bounds for $$$a_i$$$). We can maintain a segment tree that works sort of like a merge sort tree, but only stores the 5 best classes. The "key" will be the value of $$$a$$$. The segment tree is cleared for each new value of second element, and as we iterate over the fourth elements, we add all the stuff that we already passed to the segtree. So, we can get the middle elements in $$$O(5 \log n)$$$.

    Finally, we just have to merge the three groups of $$$5$$$ values using $$$5^3$$$ time.

    The final time complexity is $$$O(n^2 \log n + n^2 5^3)$$$, or $$$O \left( n^{\lfloor \frac{m}{2} \rfloor} \left( m \log n + m^{\lceil \frac{m}{2} \rceil} \right) \right)$$$ in the general case, which is (barely) good enough.

    P. S. Please excuse my usage of numbers inside $$$O()$$$ notation here, it was just too convenient to write it like that :)

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I think this meet-in-the-middle solution works in $$$O(24 * n^2)$$$: 278171336.

      I maintain the top 3 answers for pairs ending at i as L[i], and for pairs starting at i as R[i]. Since all pairs ending at an index have the color of that index, we need to store the best 3 pairs of different second color. So L[i] would have answers with (x, b[i]), (y, b[i]), (z, b[i]).

      Now we can brute-force the 3rd element $$$i$$$ (when k = 5) and merge it with the best 1st and 2nd element across all L[j] (j<i) (there are at most $$$3\times (i-1)$$$ options stored). The only difference is that in this merge, we need to maintain the top 4 answers ignoring the color of $$$i$$$ itself. For example, if (x, y) are the colors of the best 1st and 2nd elements, we need to store the top answer for each of these 4 combinations: {includes x or not} $$$\times$$$ {include y or not}. This is because the best 4th and 5th elements may need x, y, or both of them.

      Finally we do the same but to the right, and then merge the left and right answers at each 3rd element $$$i$$$ and maximize.

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

      I got the same idea and had a bad time inplementing that :)

      The constant factor is too large for the segtree part and I can only store the 2 biggest values. Beside that some optimizations on the constant factor is also needed for me.

      Anyway the data was weak enough for that to pass 278190335

      → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +72 Vote: I do not like it

    The technique in Problem F can be directly derandomized.

    We need a family of hash functions $$$\mathcal{H} = \{ h_i \colon [n] \to [k] \}$$$ such that for any subset $$$S \subseteq [n]$$$ of cardinality $$$k$$$, there exists a hash function $$$h_i$$$ in $$$\mathcal{H}$$$ that satisfies $$$h_i(S) = [k]$$$. This is known as an $$$(n,k,k)$$$-splitter. Once we have such a splitter, we can solve the problem by trying each hash function $$$h_i$$$ from this family.

    Randomly selecting a hash function is likely sufficient with high probability when $$$|\mathcal{H}|$$$ is sufficiently large. Note that for each $$$S$$$, the probability that none of the $$$h_i$$$ splits $$$S$$$ is

    $$$ \left(1 - \frac{k!}{k^k}\right)^{|\mathcal H|}, $$$

    there are $$$n^k$$$ many such subsets, so we need

    $$$ n^k \left(1 - \frac{k!}{k^k}\right)^{|\mathcal H|} \leq n^k \cdot \exp\left( - \frac{k!}{k^k}|\mathcal H| \right) $$$

    is much smaller than $$$1$$$. We need to take $$$|\mathcal H| \geq \frac{k^k}{k!} \cdot k\log n$$$.

    The difference between the analysis above and the official solution is that, once you generates a good $$$\mathcal H$$$, it doesn't only works correctly for a current test case, it universally works for all test cases! One practical solution is to hardcode a random seed in your program that has been verified to generate a splitter $$$\mathcal{H}$$$.

    BTW, the explicit construction of an $$$(n,k,k)$$$-splitter is theoretically nearly settled by the paper "Splitters and Near-Optimal Derandomization". The authors show how to construct a family of size $$$e^k k^{O(\log k)} \log n$$$. Note that the probabilistic method gives $$$\frac{k^k}{k!} \cdot k\log n$$$, and since $$$\frac{k^k}{k!} \approx e^k k^{1/2}$$$, the explicit construction is quite close to the probabilistic bound.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      How Elegia's mind works

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

      I like the idea and firmly believe such splitters exist, but how to verify that the constructed $$$\mathcal{H}$$$ is indeed a $$$(n, k, k)$$$-splitter? Is there a deterministic approach or just checking a lot of subsets is enough? How many subsets should I check to verify that it is a splitter with 99.9999% probability?

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

        Good question, I'm not sure is there any algorithm significantly better than checking all the $$$k$$$-subsets...

        → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for your help, I have got AC using some kind of MITM :). Feel free to hack my submission!

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I have tried to uphack my submission which editing the magic constant MAX_HOLD into $$$15$$$ or $$$20$$$ but not successful. Can anyone help me to hack this and this, or prove that is enough for solving this problem? Thanks!

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

In the problem C, can we just rotate the character of array and just print it?? or missing something!?

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

    what do you mean by "rotate"? because if it means reversing the string then no, if so then the number of good pairs would remain the same.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      j guess by rotating they meant moving all characters one indice forward and sending the last character to the first place. for example "codeforces" would become "scodeforce"

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

      moving all characters one indice forward and sending the last character to the first place. for example "codeforces" would become "scodeforce"

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

        well, if you passed this problem, then this solution might as well be right, but otherwise i don't really think so, as the increment of good pairs count can't be more than n-1

        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          yes, it failed in test-case 2 Can you tell -What's does this means- wrong answer Participant's answer is worse than jury's: jans = 6, pans = 5. (test case 18) link — 278153049

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

            i think it means whilst your answer consists of 5 good pairs (pans means participant's answer), the jury's answer has 6 of them

            → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It wouldn't work. If you have, for example, "edddfg", you rotate and get "gedddf", but "gefddd" is better.

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

D1 was nice :)

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

    D2 is even nicer. Problem looks difficult. but all you have to do is, travel from left to right, and right to left. and keep propagating the maximum. that's it.

    → Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

got TLE on D at the last minute by using loop from 0->m :)

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

terrible contest! D is much easier then C, B can only be guessed, not solved.

Also I got RE26 on D2 using c++20 and WA30 using c++17, how can this be?

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

    Sorry to bother, could D2 be solved by using union-set to get maximal for each vertex?

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

      Idk, I used only dp

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

        also used dp and got rt, make sure that u are initializing dp to the longest size of l_i read

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

    B can be reframed that the person trying to minimise removes the largest number possible, and the person maximising tries removing the lowest number possible.. so in the end, after they cut off all of the numbers from both ends turn by turn.. only thing remaining is the median of the sorted array..

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    how can C and B (or D) be guessed

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

I tried constructing solution of B the way the game is played(now realized it wasn't optimal)still where has my solution gone wrong 278140256 .

Also can you guys suggest resources to build logic and concepts to solve upto div2 C,thanks in advance!

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

    Just practice more div2 C problems and learn the topics needed to solve them if you get to know about some new topic during practicing.

    → Reply
»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

My first contest with AC on div2C. ThankyouThankyouThankyouThankyou!

→ Reply
»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

W contest!

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

It was a great contest, and I'll soon achieve the "pupil" rank. The first three questions were easy, and I figured out the correct logic for the fourth one. I got a TLE on test 3, and I initially thought it was because I used a set, but later realized it was actually due to m being >= 1e9. Overall, it was a fantastic contest, and I'm looking forward to more like this in the future.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

It seems that the "In this version of the problem, you can choose the same integer twice or more" suggests the hint "choose the same integer twice" obviously. But D2 is a good problem for Codeforces div2 D. I guess the difficulty of it is *2000.

I want to mention that I do too much guesswork in this round. Especially B and C. Although it doesn't matter that this round is a good round for me. Thanks.

:D

→ Reply
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D is really cool!

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

solved A and B quite fast but C went right over my head, and the tutorial doesn't help either. I'll keep trying though, ain't no way I'm moving forward without an AC in problem C

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

Weak system tests for C.

My code: 278099825

A very stupid mistake, I forgot to sort the characters by how often they occur in s, as a result for the test:

1

4

ddbc

My code outputs: bcdd (which has 2 good pairs: (0; 2); (0; 3))

One of the correct answers: dbcd (which has 3 good pairs: (0; 2); (0; 3); (1; 3))

Despite this, my code has passed the system tests and got AC

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    you shouldn't count (0, 3) in dbcd since it's the same character so it wont count in the additional good pairs

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You code output has also one more good pair : (2,3)

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

      Yes, you are right. Thank you. I am sorry. I didn't notice that there exists pairs with len of 2 that can be a good pair

      → Reply
»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

I think it's harder to find the right strategy in C than in D1.

Thanks for D2. It was fun

(And yes, I will finally turn blue)

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

.

→ Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it +23 Vote: I do not like it

Alternate solution to E1 :

Lemma 1 : Every interval must have either exactly 1 0, or exactly 1 1(where the definition of 0s and 1s are same as editorial)

Proof : The optimum solution must be a local minimum. Fix the other segments and vary the number of 0s and 1s in one segment, it is a quadriatic function with central maxima. Hence, it is minimized at the ends of allowed ranges.

Lemma 2 : Some prefix of intervals will have 1 1, and some suffix will have 1 0, proof is left as an exercise

Just brute the prefix, and find cost to get O(m^2). Extending to E2 is trivial as left as an exercise. This can probably be extended to get a near-linear solution by computing cost(prefix + 1) — cost(prefix) fast, but i am too lazy to work out the details.

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

    Here's a $$$\mathcal{O}(m)$$$ solution for E1 278231107

    Proof of correctness
    → Reply
»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

This my first Div2 contest I solved 3 problems :)

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

in problem F, why is the probability of getting the optimal solution in one attempt is $$$\frac{m!}{m^m}$$$ ?

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider a set S = {s[1],s[2],...,s[m]} of all distinct b[i] in an optimal answer. To be able to get this answer from bitmask dp, all f(s[i]) must be distinct, where f(x) is mapping from x to a random number in [1,m]. The number of such mappings is m!*(m^(n-m)), m! is because f(s[i]) must form a permutation, m^(n-m) is because for any b[i] not included in S ,f(b[i]) can be any number and it doesn't affect answer. Number of all possible mappings is m^n, since for each b[i] there are m possibilities. Then, the probability of finding a mapping, where we can get an optimal answer is m!*(m^(n-m))/m^n = m!/m^m .

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

Hi, please check this 2 submissions, they have mostly the same code, the only difference is that the vectors are global in the first one. The second code gives TLE and by a big margin. Is this a bug or what? https://codeforces.net/contest/2003/submission/278156729 https://codeforces.net/contest/2003/submission/278156524

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

    Definitely not a bug. You're creating vectors of size 2e5 for every test case. It's a common mistake.

    → Reply
»
3 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

top 3 reason for depression

  1. breakup

  2. Substance Abuse

  3. WA in div2 A

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

I solved F deterministically in $$$\mathcal{O}(n^2 * k^3)$$$:

Let’s say we compute $$$dp(i,j)$$$ = answer if we have to take $$$j$$$ elements from the suffix of the array starting at position $$$i$$$. In order to avoid repeating some values from $$$b$$$, we also store the vector of chosen values (let’s call it $$$V$$$).

The issue is that choosing exactly those values may “block” you later. To prevent this, we also compute the best answer if we avoid using each of the values from $$$V$$$ separately. It’s easy to see that one of these $$$k+1$$$ candidates will be optimal.

Although my code’s complexity is $$$\mathcal{O}(n^2 * k^3)$$$, I believe it can be improved to $$$\mathcal{O}(n^2 * k^2)$$$. Given that I got AC in the last 12 seconds of the contest, I didn’t have time to even think about optimizing anything.

Here is my submission: 278149543 :)

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    Hacked with this test case:

    6 4
1 2 3 6 5 4
3 2 4 3 2 1
1 1 1 2 2 1

    When you get to the suffix starting with b = 4, you'll only keep {4, 2} and {4, 3} as options for your b-values. But you actually need to use {4, 1} because of the 2 and 3 on the left.

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

      Good catch! I’m surprised that there are over 60 testcases and none of them cover scenarios like this one you describe

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

I really can't get this: the first player can remove a number adjacent to a larger number, while the second player can remove a number adjacent to a smaller number.

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

    You can think of it as. 1 player can pick any 2 numbers and remove the smaller one, and the other player can pick any 2 numbers and remove the bigger one

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

Hey everyone, does anyone have any advice for coming up with proofs for problems (apart from solving more problems or working with smaller cases)? I have realized that I can often think of the solution, but can't prove it, so I don't end up implementing it. Any help would be greatly appreciated! :D

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

    well I think it's fine to try and implement a solution even if you haven't completely proved it. while implementing it, you might actually notice the flaw and then you can correct it, or start coming up with a new solution. this can waste a lot of time, if you're not efficient at implementing, but it's a decent approach if you find yourself not being able to prove easy problems

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

What topics should I learn to solve D1 and D2?

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

I got compilation error twice in B, when I was using g++20, but the same code got accepted in g++17. Why did this happen?

Compilation error 1 : https://codeforces.net/contest/2003/submission/278061013

Compilation error 2 : https://codeforces.net/contest/2003/submission/278072152

Pretests passed : https://codeforces.net/contest/2003/submission/278078881

delayed my submission from 8 mins to 22 mins :(

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

I guessed B and C

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

Can anyone please explain, how, in example 1 for problem D1, f(4) = 4

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

    just dont do anything? x is 4 and you can leave it be

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

    Oops!! I got it now.. We can do zero operations to get max value of x as 4 itself.

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

      it took me about 10 mins to understand why f(4)=4 :(

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

In D1 first test case

  • 3 4
  • 2 0 2
  • 3 2 3 3
  • 4 7 0 1 5

how is f(4) = 4, can someone explain? thanks

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

can someone help me with problem D1?

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    the result of mex(x,ai,1,ai,2,…,ai,li) for every sequence is only two possible mex!
    for example a0= {0, 1, 3, 4} the mex of this sequence is {2, 5}
    if(x == 2) mex = 5, else mex = 2. and since i can choose every sequence multiple times, then whatever the value of x is, i can get 5 (f(2) --> 5, f(number != 2) --> 2 --> f(2) --> 5)
    so calculate each two mex for all sequence and choose the max_mex then the result is
    (max_mex * numbers_less_than_or_equal_to_max_mex) + (max_mex + 1) + (max_mex + 2) + .... + m

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

278173974 (D2) I think the approach is similar to the editorial sol but I have no clue why it's failing, can someone help?

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

I made a big mistake of starting to code problem D before working the example cases to ensure i understood the problem. Too bad I missed a crucial part even after the notification during contest that we can pick multiple sequence and moreover we can pick the same sequence any number of times. This misunderstanding led me to solve a completely different problem.

→ Reply
»
3 weeks ago, # |
← Rev. 4   Vote: I like it +17 Vote: I do not like it

E1 (Edit: and E2) can be solved in O(n) time:

Solution for E1
Solution for E2

Implementation for E1 is very straightforward: 278182451. E2 is a little messier, but still not that bad: 278261466

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

Thank you for interesting problem.I've got +64!

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

Can someone help me with my solution of d2,which got WA on 27?

278147838

Thanks

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

I don't understand the solution for C problem, Can anyone explain what does ∑(i=1 to m−1) ai ⋅ ai+1 mean?, and how is it derived ?

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

what is ans for D1 for below testcase.

2 0

1 0

2 0 3

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

    3 50

    1 2

    3 1 2 3

    4 0 1 2 3

    And also ans to this.

    → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Your test case:
    2 0
    1 0
    2 0 3

    ans: 2

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      So the ans to

      3 50

      1 2

      3 1 2 3

      4 0 1 2 3

      is 3 ???

      → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      No Actually, I wrote 2 as the answer to the first case you asked. But you asked the second question exactly the same time when I replied to your first query. You also can see the timing is almost the same.

      Your case:
      3 50
      1 2
      3 1 2 3
      4 0 1 2 3

      The answer to the second case is 1285 (5*4 + sum(50)-sum(4))

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


In problem D2, how is the answer to the 3rd test case 1281?

Test case:
2 50
2 1 2
2 1 2
Answer: 1281

In my calculation, only 0 is the only value on which an operation can be made to get the 3. For other values (1 — 50), just take the value itself to get a better answer. So, it's the same as: 1+2+3+...+50. And, we'll get 1275 and +3 (that we got from the value 0). Then in total, it'll be 1278.

But I didn't understand how the answer was 1281. Where is this extra 3 coming from?

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

    For x = 1, 2. First apply the operation for i = 1. So x = mex(x, 1, 2) = 0. Now, you can apply the operation for i = 2, x = mex(0, 1, 2) = 3. So, optimal value for x = 0, 1, 2 is 3.

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

    For values 1 and 2 you can use the first sequence to get x=0, and then use the zero with the second sequence to get x=3.

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

Have a question about D1

3 2 3 3

for f(2) put mex(2,2,3,3) is 1 and put mex(1,2,3,3) is 4.Did I misunderstand the description?

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

    actually, you also have to consider 0 as well (non-negative). So, or f(2) put mex(2,2,3,3) is 0 and put mex(0,2,3,3) is 1

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

Can any one explain for 2003C - Turtle and Good Pairs, why PyPy3-64 is being slower here 278121635 and getting TLE and also the memory limit, when the same code works fine with Python3 here 278206914. Thought PyPy always works faster than Python, what am I missing?

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

in the first problem we can write this string "abcda" by your code it's (NO) , but we can split it into : ab cd a , so why ??

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

    First character of string ab is equal to the last character of string 'a' which is not good according to the problem statement so answer is no for this testcase.

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

Did the second example in D1 change during contest?? Or I am having Mandela effect...

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

https://codeforces.net/contest/2003/submission/278211183

this is my submission can anyone help me which case i am missing ??

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    if(expected==(int)het.size()&&flag==1){ expected++; } Just update this

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    hint
    answer
    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why my code Wrong on C test3

wrong answer Participant's answer isn't a permutation of the given string. (test case 267)

278220017

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

https://codeforces.net/contest/2003/submission/278254550

Can someone please figure out why it is giving TLE

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

Please can anyone explain to me Problem C's solution, I am unable to understand the intuition and the approach through the editorial given?

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

In problem B why is it always best for Turtle to remove the i'th smallest element and not to maintain the current count of the current maximum element? Same argument for Piggy

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

The solution of D1 was O(n * l) and 1 ≤ n ≤ 2⋅10^5, 1 ≤ l ≤ 2⋅10^5 then why it does not give TLE

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

I need some help with debugging my code, I seem to have every edge case covered, yet I find myself with a WA on Test 27 :( https://codeforces.net/contest/2003/submission/278263899

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

Solution to E1/E2 was a little hard to understand, so I'll write mine

Separation of numbers into small/big parts was also very hard to understand, so I'll write the explanation too

Consider the border of $$$max\ a_i = A$$$. Now, for some optimal answer convert every number into $$$0$$$ if $$$\leq A$$$ and $$$1$$$ otherwise. It's guaranteed by construction, that all numbers in the left parts are $$$0$$$ and right parts are $$$1$$$. On the other hand, if we have some 01 coloring, we can provide an answer greedily. That's why the iff (if and only if) statement is true.

Now let's solve the whole problem. What do we want the segments to comply with in a 01 coloring? The leftmost element must be $$$0$$$, the rightmost element must be $$$1$$$ and the numbers in the segment must be non-decreasing, or in the other words for each $$$i$$$ in $$$(l, r]$$$ $$$c_{i - 1} \leq c_i$$$ must be true.

Let's try and build some DP, in which checking this would be easy. We want to be able to check the previous number and update the total number of inversions. I think the most straightforward DP to try here is $$$dp[prefix][count\ of\ 1][last element] = \text{the max number of inversions on a prefix with given number of ones}$$$. The transitions are easy. If we add a $$$0$$$, it's the smallest number amongst the prefix, so we need to add $$$prefix$$$. If we add a $$$1$$$, it's the smallest number amongst ones, so we add $$$count\ of\ 1$$$.

Now, how do we check the conditions on the segments? Just don't iterate over states and transitions that are impossible. If the current number is fixed, just iterate over it. If we should check index $$$i$$$ to be not less than $$$i - 1$$$, do that. That's it.

Solution 278270951

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

Can anyone please explain to me how the following tc answer is 16 for D2? 3 4 2 0 2 3 2 3 3 4 7 0 1 5 isn't here f(0)=3, f(1)=3, f(2)= 2, f(3)=3, f(4)=4? and total is 15.

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

    In f(2), you find mex for 3-th sequence: mex(2, 7, 0, 1, 5) = 3 so you got f(2) = 3. (Sorry for my bad english)

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

Can anyone please explain the approach for problem D2

→ Reply
»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

O(N) solution for E1. The logic is based on examples and reasoning, despite not a complete and rigorous proof. https://codeforces.net/contest/2003/submission/278303362

The idea is to assign value 0 or 1 to a signature array that can be used to uniquely yield the optimal permutation (similar to the concept in tutorial). There are 2 separate passes. In the first pass, we handle intervals in head and tail and meet in the middle, and maintain counters for number of 0 in prefix and number of 1s in suffix. It is optimal to place 0111...1 in head if pre0 <= suf1 and otherwise place 00...01 in tail. In the second pass, we handle indexes not within any interval. In this phase, it is optimal to have value 1 at the index if pre0 < suf1 and 0 otherwise.

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

Hi, this is my first comp, but had a little trouble understanding q A. The editorial says, the answer is just comparing the first and last letters of the string, but couldn't you split the string up in such away, that substrings 1st and last letters would be different without the first and last letters being the same? For example the string "AABA", though the first and last letters do not match, cant we divide the string like this? — "A", "AB" and "A", such that i can just choose t0 to be "A" and t1 to be "AB", The first and last being different? Maybe I didn't properly understand qA?

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    U are right but T1=AB and T2=A, so the first and last character match for i=1 and j=2.

    As for the solution, it's standard greedy solution. If the first and last characters donot match, we can split the string in 2 parts. First part has all characters except the last one and second part has the last character from s.

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why wa test 2 ? [submission:https://codeforces.net/contest/2003/submission/278313212]

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why wa test 2 ? https://codeforces.net/contest/2003/submission/278313212

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Love the rating predictions! Would love to see those on more editorials

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why my solution of D1 is not Working?

https://codeforces.net/contest/2003/submission/278484674

I doing exactly The same thing as the editorial aren't i?

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

    the first number on every sequence is it's size not an elements in it

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D1 and D2 are beast... D1+D2 cost me 3 hours to upsolve it. DP on graphs are sure tough one.

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In the editorial solution for D2, why are we allowed run a loop from $$$0-\min(m,k)$$$? I think I am missing something obvious, but according to the constraints the maximum value for $$$m$$$ is $$$10^9$$$. $$$k$$$ from the editorial is the $$$mex$$$ so theoretically they can reach the similar range for $$$a_i$$$ which is also $$$10^9$$$. Would it not result it TLE?

→ Reply