neal's blog

Unofficial Editorial for Educational Round 94 (Div. 2)
By neal, 4 years ago, In English

Haven't done one of these for a while! Here are my approaches to the problems:

1400A - Похожие строки

We just need to make sure our string of $$$n$$$ characters matches each of the $$$n$$$ substrings in at least one spot. The easiest way to do this is to take every other character from $$$s$$$. Code: 90908018

Another fun solution: we can generate random strings and check them until we find one that matches everything. This works because the probability of failing to match any particular substring is $$$\frac{1}{2^n}$$$, so as $$$n$$$ gets bigger the probability of failing gets extremely low. Code: 90999219

1400B - Главный герой RPG

First iterate on the number of swords we will personally take. Then we should greedily take as many war axes as we can until we run out of money. At this point, our follower needs to take as many items as possible. They can do this by greedily taking whichever of swords or war axes are cheaper until they run out, followed by taking the more expensive of the two. Code: 90918673

1400C - Восстановление бинарной строки

Note that $$$s_i = 1$$$ means "either $$$w_{i - x} = 1$$$ or $$$w_{i + x} = 1$$$," whereas $$$s_i = 0$$$ means "both $$$w_{i - x} = 0$$$ and $$$w_{i + x} = 0$$$." We can greedily solve this by starting out our string $$$w$$$ with all 1's, then marking $$$i - x$$$ and $$$i + x$$$ as 0 whenever we are forced to because $$$s_i = 0$$$. Then we can simply check whether all of the $$$s_i = 1$$$ conditions are valid to confirm. Code: 90915688

1400D - Зигзаги

We can rethink this as counting the number of equal pairs $$$(a_i, a_j) = (a_k, a_l)$$$ where $$$i < j < k < l$$$. To do this we loop over $$$j$$$ from right to left and make sure we have all $$$(a_k, a_l)$$$ pairs where $$$k > j$$$ counted in a map. Then we simply iterate over $$$i$$$ and add up the number of occurrences of each $$$(a_i, a_j)$$$ in the map.

For implementation details, note that we don't actually want to use a map and make our code slower. We can just use an array of size $$$n^2$$$ and convert the pair $$$(a_i, a_j)$$$ to the number $$$a_i \cdot n + a_j$$$ since the $$$a_i$$$ are in the range $$$[1, n]$$$. As a bonus, even if the $$$a_i$$$ were larger than $$$n$$$, we could just compress them down to $$$[1, n]$$$ and repeat the solution above. Code: 91019003

1400E - Очистите мультимножество

Notice that we can reorder the operations in any way we want without affecting the result. So let's do all of the first-type operations before the second-type operations. Then it's clear that the number of second-type operations we'll need is the number of nonzero elements left over after the first-type operations. So we just want to choose first-type operations to minimize the number of first-type operations plus the number of nonzero elements left after we're done.

Let's say we have an array $$$a$$$ where $$$a_m$$$ is the minimum value (if there is a tie, you can pick any tied index). I only have a messy proof for this at the moment, but it turns out we only need to consider two options: either take all $$$n$$$ second-type operations, or use $$$a_m$$$ first-type operations on the entire array and then recursively solve $$$a_1 - a_m, ..., a_{m - 1} - a_m$$$ and $$$a_{m + 1} - a_m, ..., a_n - a_m$$$ separately. This leads to a simple $$$n^2$$$ solution: 90999997.

Note that by using RMQ we can improve this to $$$\mathcal{O}(n \log n)$$$ or even $$$\mathcal{O}(n)$$$. The idea is very similar to the solution to problem G here.

1400F - x-простые подстроки

The key observation is that since $$$x$$$ is only up to 20, there can't be that many different $$$x$$$-prime strings total--turns out there are only about 2400 for the worst case of $$$x = 19$$$. So we can generate all of them and perform a DP where our state is represented by the longest prefix of any of the strings we currently match. We can do this by building a trie of all of the $$$x$$$-prime strings. We then need to be able to transition around in this trie; it turns out this is exactly what Aho-Corasick does for us. In particular, knowing which node of the Aho-Corasick tree we are currently at gives us the full information we need to determine whether or not we will match one of the strings after adding more characters later. This leads to a fairly simple DP: 90977148

1400G - Наемники

In order to take care of the $$$l_i$$$ and $$$r_i$$$ constraints, we can iterate on the number of mercenaries we'll choose and find the number of choices for each count. The key constraint in this problem is that $$$m$$$ is at most 20, which means that there can only be a few connected components that aren't just a single node. In particular, the largest possible connected component size is 21 (since a connected graph with $$$m$$$ edges has at most $$$m + 1$$$ nodes).

This means that for each connected component we can iterate over all of the subsets of nodes in that component and check whether the subset is a valid choice (i.e., is an independent set). We can then do a DP for each component where dp(mask, k) = the number of submasks of mask that have k ones and represent a valid independent set subset of the component.

Finally we can iterate over the total number of mercenaries we want. We can then do a knapsack over each of the components, making sure to only consider nodes in each component where $$$l_i$$$ and $$$r_i$$$ work with our number of mercenaries. Finally we determine how many valid $$$l_i, r_i$$$ mercenaries are available outside of our components, and the rest is a simple choose function. Code: 90977154

  • Vote: I like it
  • +416
  • Vote: I do not like it

Comments Comments (112)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1400/submission/90994198 , this solution just got hacked can someone help me find my mistake?

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

    For test case n = 1, arr = {0} it returns 1 instead of 0 because your solution for all test cases where n = 1 returns 1.

    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

neal Can you explain the implementation in D again? I couldn't get how did you convert the pair(a[i],a[j]) to a[i]*n+a[j]. Thanks, in advance!

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

    The idea is if $$$a$$$ and $$$b$$$ are both numbers in $$$[0, n)$$$ (meaning at least 0 and at most $$$n - 1$$$), then $$$an + b$$$ maps the pair $$$(a, b)$$$ to a unique number in $$$[0, n^2)$$$. This is the same idea as how 2D arrays work.

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

      I got it, thanks a lot again!

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

      neal Can you explain the implementation in D 'if the ai were larger than n, we could just compress them down to [1,n]'

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

        This is the standard idea of coordinate compression, where the actual values of the $$$a_i$$$ don't matter, only their relative comparisons (<, =, >). So we can replace every $$$a_i$$$ with their index in the sorted array instead. For example $$$[5, 12, 9]$$$ -> $$$[0, 2, 1]$$$.

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

          thanks~

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

          Neil can you clear how you made this formula ai * n + bi because if at some indexes if both ai and bi are N then it can overshoot N^2 isn't the size of array should be (N^2+N) both for upper bound?? Correct me where I am wrong I m confused in it..

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

            The easiest thing to do is subtract one to convert $$$[1, n]$$$ to $$$[0, n)$$$, but making the array go up to $$$n^2 + n$$$ is also fine.

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

              neal In Problem D Can you please explain why j is made to move from N-1 to 0 and not from 0 to N-1?

              Thanks in Advance!!

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

                Deleted

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

                  Obviously the algorythm works the same if going from left to right, it is just a choice.

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

      The problem can easily be done in O(n) space complexity

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry, I understood only the ones I solved anyway.

D, what is "we loop over j" here, and what are "pairs coming after j"?

E, I tried to implement something similar, solving for segemnts. I still do not get how we take minimum here, minimum of what?

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

    D: updated the description to try to make it clearer.

    E: we are taking $$$a_m$$$ as the minimum element of the array $$$a$$$.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Interesting! I have independently reconstructed the Aho-Corasick DFA in the past but did not know its name. My solution to problem F is superficially very different, using a bitmask-DP, but I expect that the reachable bitmasks are nearly in one-to-one correspondence with the states of the Aho-Corasick DFA. The $$$k$$$-th bit in a mask corresponds to whether or not there exists a substring ending at the current position with sum $$$k$$$ and no internal substring with a proper factor of $$$x$$$ as its sum.

The transitions can be performed fairly easily and quickly for any fixed $$$x$$$ using bitwise operators and a pre-computed mask describing the factors of $$$x$$$ without knowing anything about the trie. See 91004935 for a not-very-clean implementation of this idea. Since no two consecutive bits are set in any accessible mask (since 1 is a factor of $$$x$$$) and since the least-significant bit was always set, I estimated the worst-case number of accessible states was at most $$$F_{19} = 4191$$$, also for $$$x = 19$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Actually, the question 1400E is the same as question 448C.

You can use 448C's code to pass question 1400E.

:)

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

    Unfortunately, they are not same.

    I just submit 448C's code and got Accepted during contest. However, I was hacked by FelixArg with the data below

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

      This is because of a tiny difference in the constraint.

      For 448C, the lower bound of values in the array is 1, whereas for 1400E the lower bound is 0.

      It depends whether your code handles this corner case.

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

        You are right.

        My submissions can Accepted 1400E and 448C lol.

        but I didn't submit 448C's code to pass 1400E. :)

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

upd:done

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

    For a segment, you are reducing each element by the minimum but adding only 1 to the answer whereas the minimum value should be added to the answer ( Read statement of operation 1 carefully ) . Also you are not considering cases like 10 10 10, you will add 10 to the answer, but the optimal answer is 3 as in one move you can make any one element zero by operation 2.

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

    Here you even have to use the operation 2 to make any number 0. Have you considered that?

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

    Here you even have to use the operation 2 to make any number 0. Have you considered that?

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

Can someone please explain me the nlogn approach for the problem E? I solved it in O(n^2) after the contest. I did not understand the nlogn approach in the editorial.

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

Thanks for the editorial :)

→ Reply
»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Other solution of A — Just take nth character n times.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Um the problem E was in this contests. https://codeforces.net/problemset/problem/448/C

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

    However I submitted 448C's code, only to be hacked by FelixArg with the data below

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

      yes the only difference was 0 <= ai <= 1e9 in this problem.

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

        I can't agree more.

        However, the only difference makes it possible for the multiset to be empty in the very beginning. In the case, my programme may print 1 instead of 0.

        → Reply
»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

For D, there's another way with DP (though it barely fits under memory limit). Consider this separate question — given a string, find the number of subsequences of the form "abab". This can be solved in $$$O(n^2)$$$ with $$$dp_{a,b,len}$$$ , where $$$len$$$ is the length of the subsequence so far — 0 if $$$a$$$, 1 if $$$ab$$$, 2 if $$$aba$$$, and 3 if $$$abab$$$

See this submission

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

    I had to stare at your code for a good 10 minutes to understand the DP transitions. You're a genius.

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

      i spent 30 min still don't get it.. could you please explain it?

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

        Bit tough to explain in words, but I'll try my best.

        The outer loop iterates over all the array elements. Let a[j] be $$$val$$$. In a subsequence of type "abab", $$$val$$$ could be either $$$a$$$ or $$$b$$$. We need to consider both cases.

        First, let us consider the case where it is $$$a$$$. One possibility is this is just the first element of our subsequence — so dp[val][i][0] needs to be incremented for all possible i. since any of them could become our $$$b$$$. The other possibility is that this is the third element. Now, let us check — how many subsequences of type "ab" have I found already? That's dp[val][i][1]! So let us add that to dp[val][i][2]

        Next, we consider the case where it is $$$b$$$. I'll leave that to you, it should be clear from the previous discussion. The reason it can be confusing is the order in which I made the updates is a bit weird — this is because $$$a$$$ can be equal to $$$b$$$. This update order makes sure we don't count things multiple times.

        Something else is that the answer will be the sum od dp[i][j][3] for all i and j. But you can't do that because of the memory limits, so we can just add directly to the answer.

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

    Could you please explain what is dp[i][j][k] store??

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

      It stores the number of subsequences of type "ijij" of length k+1. As in, k = 0 stores the number of subsequences of length 1 which would just be "i", k = 1 stores number of subsequences of length 2 which would just be "ij", etc.

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

    Awesome solution! and thanks for sharing.

    Do you think there is a way to implement this type of DP recursively rather than iteratively? Just trying to gain some more intuition on this sort of DP method.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1400/submission/90939112 can anyone please tell why this is wrong?

also in C I used logic that if s.i-x!=s.i+x then its impossible else i tried to make ans greedily https://codeforces.net/contest/1400/submission/90955591 but it is giving wrong ans

Thank you in advance

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

    I also confused at first in Problem C but point is that given string is s.(result of process, not w) so your greedy logic's counter example (x=1) here

    w : 1101011 <- original

    s : 1110111 <- result of process, you are given this with x=1

    when i==2, s.i-x != s.i+x (each values are 1, 0)

    but w is 1101011, possible

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1400/submission/90948235 can someone help me to find why I am getting WA in this

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think B and C should have been swapped.

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

    I couldn't agree anymore. I took much more time to solve problem B.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody elaborate more on B, it would be really helpful , thankyou.

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

    we have two bags A and B of capacity p and f respectively now we go to store we have cnts swords of weight s units each and cntw war axe weight w units each now we have to take maximum amunt of weapons in our bags....

    My approach is same as given in editorial:-

    At first let us iterate over no of sword we can take(0 to cnts) then for each iteration(suppose i = 3) so we are left with p-i*s unit capacity of our bag so we can take min(cntw,p/w) units of war axe.(in this way our Bag A will be filled)

    now we are left with Bag B which has f units so first check which of swords and war axe has less weight(because if we take less weight things our bag will be filled with max weapon consuming less space)

    suppose s<=w:-

    fill the bag B with min(cnts,f/s) and decrease f by min(cnts,f/s)*s then add no of war axe we can take which is min(cntw,f/w)

    so this will be your ans for each iteration then print he max answer for each iteration.

    for more clarity you can see my solution:- https://codeforces.net/contest/1400/submission/91020704

    sorry for bad english.

    Edit :- also you have to decrease the counts as per steps

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A. If I output from 0 to n-1 of string s why is it getting wa?

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

    1

    3

    10100

    for this case you print 101 but substring 010 there is no similar

    → Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

My idea is a bit different for A and D.

For A, notice that $$$s[n]$$$ is present in all the substrings. So, we can just set all the characters of $$$w$$$ to $$$s[n]$$$. Code.

For D, we can iterate over all $$$j$$$'s and all $$$k$$$'s. We iterate over $$$j$$$ from left to right, and for each $$$j$$$, we iterate over $$$k$$$ from $$$N$$$ to $$$j+1$$$, like two pointers. We maintain two frequency arrays, one for $$$i$$$ and one for $$$l$$$. Let's call the frequency array for $$$i$$$, $$$left$$$, and for $$$l$$$, $$$right$$$. Each time we shift $$$j$$$ to the right, we increment the count of $$$a[j]$$$ in our frequency array: $$$left[a[j]]$$$++. Each time we shift $$$k$$$ to the left, we increment the count of $$$a[k]$$$ in our frequency array: $$$right[a[k]]$$$++. Finally, for any pair $$$(j,k)$$$, its contribution to the answer will be $$$left[a[k]]*right[a[j]]$$$. Code.

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

    Splendid explanation !! In case anyone needs help in the c++ code https://codeforces.net/contest/1400/submission/91027103

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

    Yes , in D it is extremely simple to iterate over j and k and the rest is div2 B level problem .

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

    **left[a[k]]∗right[a[j]] ** can you please explain how contribution will be this?

    edit:- i get it .. thankyou for great approach!

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

      For each $$$a[j]$$$ and $$$a[k]$$$, $$$j<k$$$, we need to find the number positions $$$i$$$ and the number of positions $$$l$$$, such that $$$i<j$$$, $$$k<l$$$ and $$$a[i]=a[k]$$$ and $$$a[j]=a[l]$$$.

      Then, for each pair $$$(j,k)$$$, the total number of valid pairs $$$(i,l)$$$ which satisfy the condition will be the count of such positions $$$i$$$, multiplied the count of such positions $$$l$$$, as each of those valid $$$i$$$'s can be paired with each of those valid $$$l$$$'s and vice versa.

      $$$left[a[k]]$$$ stores the number of times $$$a[k]$$$ has appeared to the left of $$$j$$$, as $$$a[i]$$$ needs to be equal to $$$a[k]$$$, while $$$right[a[j]]$$$ stores the number of times $$$a[j]$$$ has appeared to the right of $$$k$$$, as $$$a[l]$$$ needs to be equal to $$$a[j]$$$.

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

    I did almost the same. Instead of keeping left and right I just made 2D dp preprocessing, which is basically prefix sums for each i. dp[i][j] is how many times value a[i] was appeared up to position j. 90946281 This preprocessing is additional $$$O(n^2)$$$ but solution is already $$$O(n^2)$$$ then why not? :) Also, notice that it actually works for any a[i] and it doesn't need coordinate compression if a[i] was bigger (:

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have a binary search solution for problem B?

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

    I don't see how binary search works directly. One way to do it is, iterate over number of swords you take, and then the problem is converted to "maximum number 1 person can carry", and for 1 person case, you can use ternary search.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well I guess you can change the blog name to "Official Editorial" now :D

→ Reply
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I have a different approach for problem G (though wasn't able to solve it during the contest), which uses Inclusion-Exclusion.It isn't hard to find for each $$$i$$$ in $$$[1,n]$$$, the number of people who are willing to form teams of size $$$i$$$. Lets call this $$$P_i$$$. From this we can calculate the number of teams that can be formed as $$$\sum_{i = 1}^n {P_i \choose i} $$$ when there are no fights between mercenaries.

But when there are fights we want to exclude certain teams we choose. This can be done by Inclusion-Exclusion. Iterate over a bitmask of size of $$$m$$$ and consider that we have a team which includes all the pairs of fights whose corresponding bits have been set. We can find the range of the sizes of the team so formed, and let's call this, $$$l_{mask}$$$ and $$$r_{mask}$$$. Now to include/exclude such teams formed, we just add/subtract $$$\sum_{i = l_{mask}}^{r_{mask}} {{P_i - x} \choose {i - x}} $$$, where $$$x$$$ is the number of people we have in the fights we are considering. Since $$$x$$$ can only be upto $$$2m$$$, its easy to precompute these values as prefix sums. Here is my code.

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

Your way explaining is so simple and covers different approaches.

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Simple, short and to the point explanation!

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

trash pretest and trash me

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

can anyone please tell me what is wrong in this https://codeforces.net/contest/1400/submission/91026040

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    if((i-k>=0) &&(i+k<n))
{
    if((ap[i+k]=='0')&& (ap[i-k]=='0'))
	      {
	           f=-1;
	           break;
	       }
}

    This paritcular line seems wrong to me. try to change if((ap[i+k]=='0')&& (ap[i-k]=='0')) to if((ap[i+k]=='0') || (ap[i-k]=='0')) Because we need to check only if any one of the value is 0 or not. But your code seems to be printing -1 only if both are -1

    	            if((i+k>=n)&& (i-k<0))
	            ap[i]='0';

    Also why did you do this???

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

Problem-D

https://codeforces.net/contest/1400/submission/91027517

Can someone please tell me why is this getting WA.

My approach — Store the frequency of each element upto a particular index i and also store the index of that element. Then iterate over the indexes of each element

Our main objective is to count number of tuples (i,j,k,l). So consider the index we are iterating over as k.

Then for each element we need to calculate the number of (i,j,l).

For calculating number of valid l, I just need to know the number of elements after our working indexes.(Which can be calculated from the frequency array that I have created).

As for number of(i,j) pairs, I am using dp to calculate those and than multiplying both number of pair(i,j) and (l) and then update the answer

But I am not able to understand why is this approach giving WA on test case 2

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F, I know how Aho-Corasik works, but can't figure out how to apply dp, can someone help me??

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with problem D. Why my code is wrong (it's gving WA for sample test case)

#include<iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        int arr[n];
        for (int i=0; i<n; i++) {
            cin >> arr[i];
        }

        int ans = 0;
        for (int i=0; i<n-1; i++) {
            int mid[3005] = {0};
            int right[3005] = {0};

            if (i+1 < n) mid[arr[i+1]]++;
            for (int j=i+3; j<n; j++)   
                right[arr[j]]++;
            
            int count = mid[arr[i+1]]*right[arr[i+1]];
            int k = i+2;
            while (k<n) {
                if (arr[i] == arr[k]) {
                    ans += count;
                }
                // increment k
                k++;
                mid[arr[k-1]]++; // as prev k will be in middle elements
                if (k < n) right[arr[k]]--;
                if (k < n && right[arr[k]] < 0) right[arr[k]] = 0; // frequency can't be -ve
                count += (right[arr[k-1]]); // asnewly added pairs due to increment of k
                if (k < n) count -= (mid[arr[k]]);
                if (count < 0) count = 0;
            }
        }
        cout << ans << endl;
    }

    return 0;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If it's wrong for the sample testcase, add print statements and debug it.

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

What is the problem with my approach to Question B : 90956692 Can someone help?

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

    I think you better see the test case by yourself , and reflect from that.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is mentioned that solution of D using map will be slow. It gives TLE at test case 26. But the complexity of the solution seems to be $$$n^2logn$$$ which should be sufficient for 2 second time limit. What is the reason for TLE using map?

https://codeforces.net/contest/1400/submission/91036632

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I confirm that solution for B is right, Yeah I know it's greedy but there should be a POC for that.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you please explain why you are calculating minimum — outside in problem E:)

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

Thank you for this unofficial editorial!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the wonderful explanation, neal but in Problem E, can you please explain the significance out the "outside" variable in your code and why are we subtracting it? 90999997

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

    If you analyze the solution, by the time we call solve(first, last), we have already subtracted max(A[first - 1], A[last + 1]) from the subarray, which is why we compute that.

    Alternatively, we could just pass in outside to the function (and switch to half-open intervals) like this: 91063322

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

      thanks got it now, but why should we take half open intervals?

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

        Half-open intervals are just generally nicer to code and think about.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone use the idea explained in EDU — Segment Tree — Problem 3D? It is not the fastest solution, it is $$$O(n^2 . log n)$$$ but it became very useful to me. Thanks Codeforces for everything!

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

For problem D we can also solve it with prefix sum array where the occurences will be saved. At first we will create prefix sum array for all the elements from 1 to n. Time complexity will be O(n^2) Suppose we have a tuple 1,3,1,3 (ai,aj,ak,al) We will iterate j from 0 to n and k from i+1 to n and set aj and ak as the jth and kth index respectively. Thus we need to find the number of occurences of ak before j and number of aj after k which can be done via prefix sum array.

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

In Problem F, what is the worst case string which has about 2400 x-prime substrings for x = 19?

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

    No no, you're misunderstanding. There are only about 2400 different x-prime strings possible for x = 19.

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

      Ahh.. I totally misunderstood, I see it now. Thanks for the reply and the editorial!

      → Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Thankyou so much neal.It took me an hour to understand the approach and implementation of Problem-D. Worth it.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In question E, padding the array with 0s was very clever. I was thinking of passing the current minimum value as an argument, but this looks better. I knew the idea but struggled to implement it during the contest.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I have tried to make editorial for this round . Language for communication : Hindi

code in c++

A — https://www.youtube.com/watch?v=e9pfuRz54cY&t=7s | English

B- https://www.youtube.com/watch?v=nm93QSZqvUM | English

C — https://www.youtube.com/watch?v=M6DRvxN7s-o. |Hindi

D — https://www.youtube.com/watch?v=jeX_1lNK6UA | Hindi

E — for now it is still in process ;-)

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -12 Vote: I do not like it

I solved 1400E - Очистите мультимножество with dp in $$$O(n^2)$$$. I thought someone described it already but no. I don't see

Idea is simple. Notice that without second action it's just sum of max of difference and 0. Why? Well, because it's similar to brackets depth. So, how second type may help to do it better? It may help to decrease some spikes/hills in less steps. Also notice that you don't need to apply twice second type of action on same position. This means that actually for any position there is: either we use second type, or we don't. Assume there is optimal solution. For any position where it wasn't use second type of action there is uniquely defined previous position of same kind (position where wasn't used second type of action). But this also means that all of positions between were using second type of action. This leads to dp. dp[pos] will tell how many actions of both types you need to make non-decreasing sequence up to pos without touching value at position pos. To calculate dp[pos] you need to try make it from each i < pos using greedy strategy for values between i and pos. it's just take minimum, sum, and difference. Minimum calculated based on idea that you may go backwards from pos and maintain minimum on this subarray. 90985209

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

    I would like to know why downvotes.

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

      Very nice explanation! Maybe you got so many downvotes because the first sentence reflects some arrogance but again you are CM so maybe you have the right to be arrogant. Thanks for the explanation though. The best one among all I read for this question and the fence painting one. Thanks!

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

        Can you explain in details why it does feel arrogant? Because I thought I said that I didn't see anyone that described similar solution. Is thinking that someone should have already described it — arrogant? Well, I said this because of my experience. Most of time I want to share my solution and it's already described by someone else.

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

    I decided to put more effort into much more detailed explanation of this solution. Here we go.

    More details
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me in C. Here is my solution 91134362. Please tell me where I did mistake.

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

    Now that the contest is over, it shows the reason your solution failed. At first glance it seems that you didn't check if j-x is greater than 0.

    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

neal 1400E - Очистите мультимножество solution without proof in editorial is trend nowadays? It's starting to get annoying. I did solve it in other way with proof of my solution, so at least I'm sure that both solutions give same answers on system tests. But I still don't think it's ok.

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

Hi, regarding problem E, I am unable to understand why the order of operations does not matter. Can you(or somebody else) please elaborate on that? Nevermind. Got it.

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

How to solve B if 'cnts' and 'cntw' are infinity?

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

    only choose elements with less weight

    that is if swards are lighter only choose sward else axes.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey neal, did you manage to prove the claim on the editorial for problem E? The claim makes much sense, but I'm struggling to prove it

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Honestly, Problem D is one of the most finely crafted Problems I've seen. Absolutely loved it!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My idea for Problem D if anyone interested:
Maintain frequency index vector for each integer from $$$1$$$ to $$$n$$$. Now let's say we want to find out number of pairs for $$$x$$$ and $$$y$$$. Let's say
$$$freq[x]= k_1, k_2, k_3, ...$$$
$$$freq[y]= l_1, l_2, l_3, ...$$$
Here $$$k_i$$$ is the index where $$$x$$$ occur and similarly for y. We want to merge these two lists and while merging we will maintain a string/array which consists of $$$0's$$$ and $$$1's$$$. We will put $$$0$$$ if we are taking from $$$x$$$ and $$$1$$$ if we are taking from $$$y$$$. Now the problem remains is as follows: We are given a string consisting of $$$0's$$$ and $$$1's$$$, we need to find number of subsequences of type $$$0101$$$ and $$$1010$$$ in this string which can be calculated with dp. Also, we can handle the case for same number (say $$$x$$$) separately. See my submission.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My proof for problem E

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

For problem E, will this work? First, I shall fix the number of type-2 operations, say $$$K$$$.

  • It's always optimal to do $$$K$$$-2nd type operation on $$$K$$$-largest numbers.
  • So, I removed $$$K$$$ largest number from the list and tried to find the number of type-1 operations required.
  • It turns out that the number of first-type operations is the maximum number in every mountain.
  • $$$a_i < a_{i+1} < a_{i+2} ... < a_k > a_{k+1}> a_{k+2} ..> a_j$$$ , I add $$$a_k$$$ to my answer.
  • So answer = $$$ min(k + \sum_{}{} a_k)$$$ for all $$$0 <= k <= N $$$
→ Reply
»
6 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I know the blog has been published a long time ago, I still want to give out a little more of details in problem F for people who try to upsolve it at the moment.

Denote $$$dp[i][u]$$$ as the minimum number of character you need to erase if you are at the position $$$i$$$, and standing at node $$$u$$$ of the trie. Before any transition, make sure the current node $$$u$$$ is not a terminal node of the trie (the leaf node, or the last character of a string in the trie), otherwise the current state form a x-string. For the transition to the next character ($$$i$$$ to $$$i + 1$$$), there are two possibilities:

  • Erase the $$$(i + 1)$$$ th character. In this case, the state $$$(i, u)$$$ will be transited to $$$(i + 1, u)$$$, because we will stay at the current node after erasing. Then $$$dp[i + 1][u] = min(dp[i + 1][u], dp[i][u] + 1)$$$ (adding one here because we perform the erase operation).

  • Not erase the $$$(i + 1)$$$ th character. In this case, the state $$$(i, u)$$$ will be transited to $$$(i + 1, v)$$$, where $$$v$$$ is the next node in the trie after we use the edge $$$s_{i + 1}$$$ ($$$s$$$ is the initial string). If $$$v$$$ is not a terminal node, then $$$dp[i][v] = min(dp[i][v], dp[i][u])$$$.

Hopefully this will help.

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

Problem E is the same problem as 448C - Про покраску забора with rating 1900

→ Reply