neal's blog

By neal, 2 months ago, In English

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

1400A - String Similarity

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 Protagonist

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 - Binary String Reconstruction

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 - Zigzags

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 - Clear the Multiset

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-prime Substrings

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 - Mercenaries

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months 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!

  • »
    »
    2 months 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.

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

      I got it, thanks a lot again!

    • »
      »
      »
      2 months 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]'

      • »
        »
        »
        »
        2 months 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]$$$.

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

          thanks~

        • »
          »
          »
          »
          »
          2 months 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..

          • »
            »
            »
            »
            »
            »
            2 months 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.

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

              So first we are decreasing all array element by 1??

            • »
              »
              »
              »
              »
              »
              »
              2 months 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!!

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Deleted

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months 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.

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

          We should use a float array in this case, right? because sometimes the numbers get mapped to a float while compressing?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

»
2 months 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?

  • »
    »
    2 months 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$$$.

»
2 months 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$$$.

»
2 months 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.

:)

  • »
    »
    2 months 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
    
    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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. :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain me why the last test case in the third question is -1.I am not getting it.

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

    Because there isn't any string possible, which can give you s=110 (x=1). Try to build the answer by taking the answer string w=111. Now according to the rules given:

    1. s[0]=1 => w[0-1](does not exist), w[0+1]=w[1]=1 (Must be 1 because other index does not exist).
    2. s[1]=1 => w[1-1]=w[0]=1 OR w[1+1]=w[2]=1.
    3. s[2]=0 => w[2-1]=w[1] != 1 (this should not be equal to one as the answer string s has 0 at i position) and w[2+1](does not exist).

    Now look at statement 1, and 3. 1 says that w[1] must be equal to 1, while 3 says that w[1] must not be equal to one. So no string w exists to give answer string s according to the given rules.

»
2 months ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

upd:done

  • »
    »
    2 months 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.

  • »
    »
    2 months 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?

  • »
    »
    2 months 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?

»
2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me how to solve problem-B using binary search? Or are we using binary search along with greedy approach in the above editorial? Either way, I'm not able to gain the intuition.

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks for the editorial :)

»
2 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    2 months 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
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months 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.

»
2 months 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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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.

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

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

    • »
      »
      »
      2 months 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.

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/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.com/contest/1400/submission/90955591 but it is giving wrong ans

Thank you in advance

  • »
    »
    6 weeks 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

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

can anyone tell me where my code for problem B is failing(hidden testcase)

solution — https://codeforces.com/contest/1400/submission/91017902

Edit:- NVM got it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I think B and C should have been swapped.

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months 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.com/contest/1400/submission/91020704

    sorry for bad english.

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

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

      okay got it, thanksalot! really appreciate the help :-))

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

      How can we intuitively figure out that the algorithm of taking the maximum number of swords greedily is wrong? And justify that the iteration is necessary?

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

        We are doing iterations because we don't know whether it will be profit for us to take as many sword as we can have in our bag maybe if we take some war axe then we might get better result so this type of confusion may lead to iterative approach where we are checking for every amount of sword we take..... also this solution make many things clear to me.. Thanks priyanshu.code.

»
2 months 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?

  • »
    »
    2 months 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

»
2 months 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.

  • »
    »
    2 months 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.com/contest/1400/submission/91027103

  • »
    »
    2 months 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 .

  • »
    »
    2 months 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!

    • »
      »
      »
      2 months 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]$$$.

  • »
    »
    2 months 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 (:

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have a binary search solution for problem B?

»
2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My idea for A was to calculate no. of 1's and 0's and which ever is the maximum , print it n times

Code can be found at: https://codeforces.com/contest/1400/submission/91002140

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, in problem D My idea was — loop i and k (k>i) and for each (i,k) pair i'm trying to find freq of elements in-between those — freq of elements betwn i and k and freq of elements betwn k and n (end of the array)

I know this is Brute Force of N^3. But want to know my approach. Help me out.

»
2 months 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.

»
2 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

Your way explaining is so simple and covers different approaches.

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Simple, short and to the point explanation!

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

trash pretest and trash me

»
2 months 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.com/contest/1400/submission/91026040

  • »
    »
    2 months 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???

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

Problem-D

https://codeforces.com/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

»
2 months 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??

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be an official editorial as well?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

@neal In problem B, what if the counts of swords and axes are huge? What will the solution be then?

»
2 months 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;
}

  • »
    »
    2 months 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.

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

      Done that already. If I fix code for test case 1, it fails for the other one. I’m confused what I’m doing wrong in the solution as I’m following what others have mentioned in the comments.

»
2 months 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?

»
2 months 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.com/contest/1400/submission/91036632

»
2 months 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.

»
2 months 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:)

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you for this unofficial editorial!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone who did problem B using binary search?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please somebody help me with my code for the problem C-Binary String Reconstruction. the code is running fine on the test cases but shoes wrong ans;

Approach- I firstly created a string ans of same size as string s with each element to be 'a'. Then I itereate over string s and if s[i]=='0' then I put ans[i+x] ='0' (if i+x is within length of s) and ans[i-x] = '0' (if i-x is within length of s).Then I iterate over s once again ,if s[i]=='1' then if ans[i+x]='0' (if i+x is within length of s) and a[i-x]='0' then i set flag as 1; at last iterate over string ans and replace all the remaining 'a' with '1'; At last if flag=1, print -1 else print ans;

https://codeforces.com/contest/1400/submission/91052214

please help me out

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1400/problem/A for creating w you can just pick up odd positions char form s(1,2,3,..,2n-1) and make string w like if s=0101101 then w=0011

»
2 months 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

  • »
    »
    2 months 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

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

    It is parent array's minimum/previous minimum,which affects the new child array's minimum,thus should be subtracted,isn't it ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have problem D python solution. BF solution is getting TLE

»
2 months 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!

»
2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me why my solution for problem C is invalid. Thanks!

http://codeforces.com/contest/1400/submission/91075357

»
2 months ago, # |
Rev. 9   Vote: I like it 0 Vote: I do not like it

*****************Why a O(2n) code getting TLE in problm C****************

Can anyone tell me please why this submission 90966915 is showing TLE? It was accepted till final standing and after final standing I've submitted the same code in offline also & which was accepted, see here 91082748 . I can't understand whats wrong with me. advance thanks.

neal

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

    I copy-pasted your submission 91117140 and it ran in $$$1918 ms$$$ and then I submitted it again with some comments and got TLE on test 7 91117335.

    Basically your code is slow because of the for loop you make to ans+='0'.

    Instead, using resize makes it run on $$$31 ms$$$.

    You got lucky that your code got accepted at all after the contest. These are minor fluctuations in judging time say ~$$$150ms$$$. Your code is basically slow.

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

Now I wanted to generalize problem D. A few days ago I solved a question where we had to calculate all the substrings of length 2 and in a way where we can later query all the results for each pair and I came up with the following approach :-

Code

Now inspired by problem D from this contest, I would like to ask how would we solve if we later had to do an operation query(i, j, k, l) and get the count for the tuple (i, j, k, l), where a[i], a[j], a[k] and a[l] have values independent of each other ? Any help would be really appreciated...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

could D be done using seg tree's ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1400/submission/90956921 Can someone please explain that why is this code not working for C part.

»
2 months 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?

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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!

»
2 months 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.

»
2 months 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.

»
2 months 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 ;-)

»
2 months ago, # |
Rev. 3   Vote: I like it -12 Vote: I do not like it

I solved 1400E - Clear the Multiset 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

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

    I would like to know why downvotes.

    • »
      »
      »
      2 months 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!

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    2 months 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
»
2 months 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.

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

neal 1400E - Clear the Multiset 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.

»
2 months 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.

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

In Problem E, I have used a logic similar to the editorial. I have tested with several test cases. Can't identify the error. Can someone help me here? https://codeforces.com/contest/1400/submission/91254239

I used a similar logic for Painting Fences https://codeforces.com/problemset/problem/448/C Got Accepted: https://codeforces.com/problemset/submission/448/91261876

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    2 months 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.

»
5 weeks 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

»
7 days 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!