By pikmike, history, 5 weeks ago, translation, In English

Hello Codeforces!

On Aug/14/2020 17:35 (Moscow time) Educational Codeforces Round 93 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Um_nik 7 111
2 tmwilliamlin168 7 119
3 neal 7 144
4 Farhod_Farmon 7 167
5 I_love_chickpea 7 178

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Amir_Reza 13:-6
2 dcordb 3
3 KnightKnight 4:-4

85 successful hacks and 696 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A System_2020 0:01
B tamahom1 0:02
C IAKWF 0:02
D shinigami11 0:09
E dorijanlendvaj 0:20
F nikolapesic2802 0:08
G tfg 0:22

UPD: Editorial is out

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

»
5 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

Month of contests...... thanks CF <3

»
5 weeks ago, # |
Rev. 2   Vote: I like it +71 Vote: I do not like it

14th Aug — educational codeforces round 93

15th Aug — atcoder beginner contest 175, Facebook hacker cup round 1

16th Aug — codeforces Global round 10

I am really excited!

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

    +1

  • »
    »
    5 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    14th Aug — educational codeforces round 93

    15th Aug — atcoder beginner contest 175, Facebook hacker cup round 1,Codevita

    16th Aug — codeforces Global round 10,Google Internship Test

    BUSY DAY's

    May I couldn't Perform well in these 3 days but i will learn many new things..

    I am also excited!

    All the Best

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

      Google Internship Test, is it online? Can you provide the link?

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

      bro, did you get the mail regarding google internship test.Since, I also register for internship but haven't got any mail regarding this.

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

    you forgot to mention this 13 Aug — (CodeChef) Dementia (Rated for Division 2). Set of problems was Awesome.

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

    Addition: 16th Aug — Leetcode Weekly Contest 202

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks to codeforces for back to back contests.

»
5 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

can anyone tell me the soultion approach of codeforces div 2 664 c problem. http://codeforces.com/contest/1395/problem/C

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

    You can just brute force the answer, i was pretty annoyed that i did not manage to solve it during the contest https://codeforces.com/contest/1395/submission/89732090 ...

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      but i dont understand the brute force logic

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +11 Vote: I do not like it

        Every element of the array a (i will use the definitions from my code) can be combined with any element from the array b. So for every element with index i from a (i = 0 , N — 1) you create an array arr of M elements where arr[j] (j = 0 , M — 1) = a[i] & b[j]. If i == 0 (we are at the first element of the array) we mark in the bitset as true every element from arr and if i > 0 we will iterate over the bitset and we will mark as true in a new bitset the values val | arr[j] where val is a value from the first bitset which was already marked as true. By doing this at every step i (i = 0 , N — 1) you will have marked in the bitset every possible result for the expression c[0] | c[1] | ... c[i] (c having the meaning from the statement). After that you copy the second bitset in the first one. The bitset from the end will have marked as true every value which is a possible answer for the problem.

        PS. 512 is the size of the bitset because the maximum possible answer is 511(2^9-1). I hope that my explanation is decent.

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

    you will find it in Competitive Programmer’s Handbook(by Antti Laaksonen), page no.102.

    I learned a lot from this book

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

    you should ask this in the editorial part of that round, this is not related to this round.

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Standard Div2 round vs Educational round , which do you think is tougher ?

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

    div 2 I guess

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

    for me educational rounds are easier than div2

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    Educational is meant to have more standard problems, so they are generally easier

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it

    Don't know which one is tougher. But for me, problems from educational rounds seem to be more interesting.

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

    It's different for me, I enjoy solving standard Div 2 more, I usually get pretty upset while solving Educational rounds.

»
5 weeks ago, # |
  Vote: I like it -51 Vote: I do not like it

Hope we would see cute ! cuter ! cutest ! tester here in ECR93 comment box also!!.

»
5 weeks ago, # |
  Vote: I like it -39 Vote: I do not like it

I want to upvote testers once again

»
5 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

where is the comment-As a Tester give me a contribution..LOL

»
5 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

what is the scoring distribution?

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

    In educational rounds, all the problems have same weight-age, therefore there is no scoring distribution.

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Lucky month for competitive programmer

»
5 weeks ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

good contest

»
5 weeks ago, # |
  Vote: I like it -51 Vote: I do not like it

As a participant give me contribution.

»
5 weeks ago, # |
  Vote: I like it +148 Vote: I do not like it

I got covid 19, I am on my fourth day of isolation. I'm not feeling very well, but codeforces has helped me a lot to distract myself, wish me luck in this contest

»
5 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

I don't really understand why they say "6 or 7 problems". Aren't they sure about the number of problems till the last minutes?

»
5 weeks ago, # |
  Vote: I like it -62 Vote: I do not like it

Let us see what are we going to have today, long queue, weak pretest, complicated problem statement, or all of these together.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

speed forces

»
5 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    Can relate, I had WA on test 6 but then got stuck at WA on test 7.

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

      WA on test case 6 LMFAO

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

        Test 6 failed then try this:
        1 3 1
        10
        8 5 3
        12
        Expected: 146

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

          my code gives output:146..... but i got WA on 6

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

            Ohh yes now I remeber there is some more issue. I changed my entire approach instead of doing greedy I went to DP.

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

              can you please explain why the greedy logic does not work in problem D

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

                I dont know fully. The test case I mentioned clearly show we have to do some case work when 2 colors with 1 pair and one with more than one remains. So may be some more such case work would be required to make it work. Has anyone solved this using Greedy, if yes please comment your submission id.

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

            Try 2 2 2
            2 2
            2 2
            2 2
            ans: 12

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

          Thanks

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    For those wondering: test 7 could be something similar to

    4 2 2
    3 3 3 3
    4 4
    4 4
    

    Some greedy approaches print 32, but the answer is 48.

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

    so true, this is something exactly happend with me.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I only one who couldn't access codeforces for almost an hour during the contest? (I posted this and got downvoted, idk why).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems nowadays codeforces has better problems than atcoder... — aid

just look at problem G today and you'll find you were wrong.

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

    Why don't you like problem G? For an educational round, it is fine. I dislike E and F much more.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Could you explain your solution? I look at your code but cannot get it. Thanks in advance.

      UPD: Nevermind, I understood it now. I think your sieve-like code for handling the largest divisor is so smart.

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

      Will u plz tell , were E and F too boring or among the standard ones ??

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

        They were definitely not standard problems, and for an educational round that wouldn't even be an issue. I didn't really like how E was pretty much an implementation exercise. Looking back, F wasn't actually that bad.

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

          Yup .. Personally i also think that F was good , and also E was heavy implementation (especially for me who did coordinate compression and segment tree) .

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

It was really an educational round reminded me to study ..

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

I got problem A wrong, than was stuck on it to realise my initial idea was correct. Skipped B and went to solve C, cause I couldn't improve ranking at that point. Never solved C, I'm starting to believe I am dumb at this point...

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

    Don't be shy bro. Most of us started like that if you don't want to believe, just check my rating graph

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

      True inspiration man! I've seen a few people with very slow progress get to the top, but never people who drop that low and rise to blue. Keeps me going, already. :)

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

    I can relate to this & it even become worse when no one is there for help. Just keep practicing & don't hesitate to look for editorial & video solution. In case you need any help in A & B you can refer this

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

What a nice contest but I think D is a little easy with typical DP

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

    Could you please explain the states of your dp?

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

      F[i][j][k]=maximum sum from first i largest R, j largest G, k largest B.

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

      I'm not good at explaining things so sorry in advance if people feel my explaination harsh

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

    You need to do some greedy before this typical dp. This costed me 2 WA.

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

      as I said before, you must DP with i largest, j largest, k largest so you must sort three arrays before dp

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

        Yeah, that's why it's not a classical dp. You need to be clever enough to get the idea.

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

          Oh. I tryed to use dp but missed some status trans

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

        Can you explain the state transition also?

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

    I don't think this was an easy problem. Maybe it's not hard to guess that the solution is dp but if you want to be sure that this solution is correct you need to prove that in the maximum total area obtained by using i red sticks, j green sticks and k blue sticks there exists a rectangle with sides (ri, gj) or (ri, bk) or (gj, bk). Maybe I'm missing something but it wasn't trivial and took me a while to prove.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

how to solve C please help

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

    You subtract 1 from every element and it becomes a standard problem. https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/

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

      Elaborate , coz i still dont get it.

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

        When you subtract 1 from each element, the problem becomes counting the number of subarrays whose sum is 0.

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

          OMFG. There is no way u came up with this during the contest. You had to have solved this type of problem earlier. Anyway,Thanks man!

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

            how i realized it during the contest instead of writing it as

            $$$\sum_{l}^{r} ( a_i ) = r-l+1$$$

            write it instead as

            $$$\sum_{l}^{r} ( a_i ) = \sum_{l}^{r}(1)$$$

            which is equivalent to

            $$$\sum_{l}^{r} ( a_i ) - \sum_{l}^{r}(1) = 0$$$
            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              This is so beautiful <3

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

              mpily really liked your thought process man... appreciable!!!

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

              I saw the solution and was unable to digest why subtract by 1. Now it's clear. Thanks man.

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

              your explanation is superb

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

          to improve my rating i have to solve standard problems from geeksforgeeks or solve [roblem from codeforces,atcoder etc

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

      Could you elaborate more?

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

        The problem asks you to count the number of subarrays whose sum equals to its length right. So imagine if we subtract 1 from every element of that subarray, we end up subtracting the length of the subarray from the sum of its elements! If that subarray satisfy the condition of the problem statement then this new sum must be 0. That is why after subtracting 1 from all elements we count the number of subarrays whose sum is 0. Hope it helps.

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

      Why are you adding map[cursum] everytime to the answer?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +12 Vote: I do not like it

    first create prefix array then

    then this should be true for subarray of (l,r) to be good.

    prefix[r] - prefix[l - 1] = (r -l) + 1

    l - prefix[l - 1] = r - prefix[r] + 1;

    try to understand this part on your own
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution was a bit more complicated than cote's solution, but I think it is worth sharing. Let $$$p_i$$$ be the sum of the interval $$$a_{1, \ldots i}$$$ for all $$$i$$$ (prefix sums). Now let $$$c_i = p_i - i$$$. Notice that the number of good intervals starting in $$$1$$$ is the number of ocurrences of $$$0$$$ in $$$c_i$$$. For that we will keep a map $$$cnt$$$, where $$$cnt[x]$$$ is the number of ocurrences of $$$x$$$ in $$$c_i$$$. Now, we will "remove" the first element and update the prefix sums and $$$c_i$$$. Notice that all values of $$$c_i$$$ will change by a same value

    $$$d + c_i = c_i - a_0 - (i - 1) \Rightarrow d = -a_0 + 1.$$$

    Then we have that the

    $$$cnt[x] = cnt[x - d]$$$

    . So it is sufficient to keep a variable d and update it in each iteraction (and thre is no need to update $c_i$ or $$$p_i$$$). Submission: 89922879

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D.... why????

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Solutiom of C in less than O(n^2)..??

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

    i think it should be O(n) using hash map or something

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

    linear solution or n(log n) solution is required

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    After getting the prefix sums
    Basically what you need to find is $$$pref[r] - pref[l - 1] = r - l + 1$$$
    Equating that it becomes $$$pref[r] - r = pref[l - 1] - l + 1$$$
    So at index i you need to count the indices $$$j <= i$$$ with $$$pref[i] - i == pref[j - 1] - j + 1$$$

    Code
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can convert it to pref[r]-pref[l] = r-l

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

      pref[i] — i = pref[j-1] — j+1 pref[i] — i = pref[j-1] — (j-1) So basically find such pairs i & j (i!=j) such that this is tru?

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

      Why dp[1]=1 ?Thanks

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

        Notice for all $$$i$$$ I increase $$$pref[i - 1] - i + 1$$$
        So for $$$i = 0$$$ $$$pref[i - 1] = 0$$$ and $$$pref[i - 1] - 0 + 1 = 0 - 0 + 1 = 1$$$
        So basically I increase for $$$i = 0$$$ at the beginning

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was testcase 7 of problem D?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    test:

    4 2 2

    3 3 3 3

    4 4

    4 4

    your ans = 4 * 4 + 4 * 4 = 32

    correct ans = 3 * 4 + 3 * 4 + 3 * 4 + 3 * 4 = 48

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

    I got WA on test 7 too and couldnt figure out where I went wrong. But then I realized this test case gave me a WA-

    3 3 3 3 3 3 3 3 3 3 3 3

    The answer to this should be 36 but it gives me 27. I hope this might help.

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

Getting AC in D in like 10 mins but not getting any logic whatsoever for C hurts a lot.

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

    sum(l,r)=r-l+1

    sum(l,r)-(r-l+1)=0

    v[l]-1 + ... + v[r]-1 = 0

    so just subtract 1 from every element, and find all sub arrays with sum==0

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

I think C is more difficult than D...T^T.. How to solve C?

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

    Calculate the prefix sums p[i]. If p[i]-p[j] = i-j, then j+1..i is a good subarray. However, this equation can be rearranged to p[i]-i = p[j]-j. It suffices to find all values of p[i]-i and use some math to calculate the number of pairs.

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

      oh...Thanks for your kind comment.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +47 Vote: I do not like it

    Here's a nice transformation:

    $$$ \begin{align} & \sum\limits_{i=l}^r a_i = r - l + 1 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - (r - l + 1) = 0 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - \left( \sum\limits_{i=l}^r 1 \right) = 0 \\ \implies & \sum\limits_{i=l}^r (a_i - 1) = 0 \end{align} $$$

    Becomes much easier to code because the goal sum doesn't change.

»
5 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

It was really good round, my nickname is lying :)

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

How to solve E? Can it be solved using set and priority_queue.

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

    Implemented segment tree and got WA on test 4.

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

    Coordinate Compression + Segment Tree I saw other peoples' code also and they implemented it using set only but i don't know about it .

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please anyone tell what's wrong in my solution in D (it's giving WA on test#7)

https://codeforces.com/contest/1398/submission/89953351

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

    test:

    4 2 2

    3 3 3 3

    4 4

    4 4

    your ans = 4 * 4 + 4 * 4 = 32

    correct ans = 3 * 4 + 3 * 4 + 3 * 4 + 3 * 4 = 48

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is test 5 in problem C!!!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me out? I can't figure out why i failed test case 2 for problem c. I have created a consecutive sum array(i dont remember the actual name) and then checked for windows of all sizes.89943421

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

    also will codeforces tell the failed test case 2 if i submit after the contest has ended?

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

    There are about 10^5 * 10^5 = 10^10 windows of all sizes. 10^10 things to do is too much for this time limit.

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

      but I didnt get tle. I got incorrect answer. I can't figure out whats wrong.

»
5 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Video Editorial for C. Good Subarrays

»
5 weeks ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

C is a standard problem often asked at AtCoder beginner rounds.[the idea is just to use prefix sums]

Edit: finally question reduces to find (i,j) pair such that j>i && pre[j]-pre[i]=j-i which can be easily solved using map.

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

    Can you explain a bit elaborate please :)

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 4   Vote: I like it +17 Vote: I do not like it

      Let $$$sum_{i}$$$ be the sum of elements till position $$$i$$$.

      If you have two positions $$$i$$$ and $$$j$$$, $$$i \lt j$$$, if $$$sum_{i} - i = sum_{j} - j$$$, re-arranging the terms we see that $$$sum_{j} - sum_{i} = j - i$$$, i.e, the sum between their positions is clearly equal to the distance between them. So we just need to keep track of the count of elements with equal $$$sum_{i} - i$$$.

      Now we note that since between all pairs with the same $$$sum_{i} - i$$$ the sum of elements must be equal to the distance between them, if the cnt of $$$sum_{i} - i$$$ occurs $$$k$$$ times, we have $$$k - 1$$$ subarrays which are adjacent to each other from which we want to form a subarray. So there are $$$k - 1$$$ ways of choosing $$$1$$$ continous subarrays, $$$k - 2$$$ of $$$2$$$ continous subarrays and so on, which is just the sum of the first $$$k -1$$$ natural numbers, or $$$\frac{(k - 1) \times k}{2}$$$ possible subarrays.

      My submission: 89890437

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

    In educational rounds problem can be standard it is OK

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

    I thought of using prefix sums to get sum of range in O(1) but still for every subarray to consider it will be O(N*N), Can you help me in understanding this a bit?

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

      What you need is pre[r] — pre[l-1] = r — l + 1. You can rewrite this equation as pre[r] — r = pre[l-1] — (l-1), so for every good subarray, pre[i] — i is constant at the ends of it. Now you just have to make pairs

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

    Can you tell me what is the need for a[i] to be between 0 and 9? It confused me a lot and consumed a lot of my time.

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

      for higher values of a[i] algo still works.

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

        Yes, that 0 to 9 constraint created a lot of confusion for me.

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

      There is no need. I think it was just to throw you off... All that mattered was subtracting 1 from every element and then doing prefix sums, and checking for 0.

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

        Yes, that really threw me off. Wasted an hour on C ;_;

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

Any idea what is test case 2 of E or what is wrong with my idea?

My idea was as follows:

If after any operation we have $$$k$$$ lightning spells, then we need to keep track of the sum of the $$$k$$$ most powerful spells, while ensuring at max $$$k - 1$$$ of those are lightning spells (use a fire spell of power 0 as a dummy spell if needed). We can maintain the non-doubled spells using multisets in descending order and the doubled ones using multisets in ascending order for both types of spells. Change in sum can be tracked at the time of transistion of elements between these sets. Is the idea wrong or did I go wrong somewhere in implementation?

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Hello, what was the idea in problem D? I assumed that it's always optimal to choose the first two biggest sides of different collor and add the area to the answer. I am really curious to know the problem since I got wrong answer on test 6!

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

    same here bruh

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

    There is the case where some of the sides are equal.

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

      That is not a problem since a square is also considered rectangle as we can understand from the test samples!

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

        Suppose the largest side lengths in red and green are both 6. Do you take the pair from green or the pair from red? This decision may have an effect on the final answer, and it is not necessarily clear which one to pick just using a greedy algorithm.

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

    I used 3d dp to solve it. Sort all the r, g, b arrays.

    Now for state solve(i, j, k) => we can have 3 possibilities

    1. solve(i-1, j-1, k) + r[i]*g[j]
    2. solve(i, j-1, k-1) + g[j]*b[k]
    3. solve(i-1, j, k-1) + r[i]*b[k]

    Take max of all the three. You will have your answer.

    Here is the link to code using above approach https://codeforces.com/contest/1398/submission/89925922

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

      This is a great idea, thank you. Probably my mistake was that I haven't found any counterexample during contest so I assumed that there is no need for backtraching stuff. (Or 3d dp)

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

        using greedy is wrong because by doing so you might end up with a lesser number of rectangles ,which in turn might reduce the final output. For example lets say we have red array of size 20, green of size 20 and blue of size 190, using greedy u might use all the elements of red and green arrays first (resulting in just 20 rectangles) but there is a possibility of having 40 rectangles if u also choose elements from the blue array.

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

      do we need to sort the array if i apply this logic, 1. solve(i-1, j-1, k) + r[i]*g[j] 2. solve(i, j-1, k-1) + g[j]*b[k] 3. solve(i-1, j, k-1) + r[i]*b[k] 4. solve(i-1,j,k) 5. solve(i,j-1,k) 6. solve(i,j,k-1)

      89945848 mine logic without sorting, can u point out where am i going wrong

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

    3 2 1 3 4 5 5 6 7

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

    Check for this testcase

    2 2 2

    5 1

    5 1

    4 4

    Correct Output (DP) : 41

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why greedy does't works for D??

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Check out this test case:
    1 2 2
    7
    5 3
    6 2

    Greedy gives 52 as an answer, but the correct one is 53.

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

      cool. How did you come up with this counterexample?

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

        during the contest, when I kept on getting WA on test 6 (and eventually never got it)

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

          I kept getting WA on test 6 too but I couldn't think of any counter example. So I believed that greedy algorithm should work. I spent 40 min staring at my code trying to find stupid implementation mistake xD.

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

      A simpler one :

      1 1 2

      5

      4

      3 2

      if we take 5 and 4 we can't include (3 and 2).

      so optimal answer is 5*3+4*2

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

      Could some one explain how come dp doesn't work without sorting the arrays?

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

    I tried greedy too but failed miserably.

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

    try this 2 1 4

    3 2

    3

    2 2 2 2

    greedy will give (3*3)+(2*2).But,we get a better answer if we take (3*2)+(3*2)+(2*2)

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

    My Greedy solution for D was taking all the combination of 3 types of triangle. Since there can be 3 types of triangle, there are 200*200*200 combinations to choose from. Each combination tells how many triangles I will make of each type. I only worked with the valid combinations so that I don't get TLE. Then I am greedily taking the maximum product and not taking any more triangles of a type than what my combination says. Can anyone tell me why it does not work?

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

      tryed the same dude, now i know its wrong on 4 2 2 3 3 3 3 4 4 4 4

      Correct output : 48 We got : 32

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

        My solution is giving the correct output 48. Still don't why it won't work. Here's my last submission 89977686

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the test 4 for problem E? I was using two sum segment tree one for lightning spells with twice the value of d and another for fire spell for value d. Also tracked minimum of lightning spells and maximum of fire spells by set and then computed the answer. Resulting WA on test 4.
89951160
In my submission, vectors are defined as sum -> lightning, sum2 -> fireball, v -> lightning, v2 -> fireball, st1 -> lightning, st2 -> fireball

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Really nice Problemset :-)

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

In E I had to query the sum of the k largest elements. Is there a data structure that supports this?

I used a messy combination of segment and fenwick trees and the fact that we know all elements before.

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

    You can do it with just two sets. First set will contain k largest elements, and second set all other elements.

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

      Can you please explain the approach.

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

        Since k can change by at most one, you will need to remove\add only 1 element. Also after inserting element you need to swap elements if minimum of first set is smaller than maximum of second set.

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

    Treap can easily handle that.

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

    Why k largest elements? Isn't it 2 * (sum of lightning) + sum of fire + maxfire — minlightning and if there is no lightning then simply sum of fire

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

      My approach definitely wasn't the simplest

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

        I see, I asked why my one is wrong? I am getting WA on test 4 implementing segment tree using this idea

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

          Sometimes it is optimal to cast lightning, fire, lightning, fire, etc.

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

      Is it so? Consider the case where you have 3 lightning spell with damage 1,2,3 and 3 fire spell with damage 10,20,30. I believe the maximum damage should be 126 but your formula evaluates to 101.

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

    you can do that offline compressing all values and using segment tree.

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

    Policy based data structures can also work (but I ended up getting WA for some reason)

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

    You can write a Segment Tree for this. Main an a segment tree with each node having 2 attributes --> Sum and Count. Initially mark sum = 0 and count = 0.

    Code for Add function

    Now, since you have stored sum and count in each vertex, you can binary search of over it to find the sum of first k largest elements:

    Code for query function

    The code provided is psuedocode.

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

educational.jpg

»
5 weeks ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Ciao Rating !

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This game really pisses me off

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

In question D, why do we have to sort the arrays before applying DP, i code it without sorting but it was giving wrong ans but after sorting with same logic it was giving right ans?

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

    code without sorting 89945848 give wrong ans. code with sorting 89955750 gives right ans.

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

    Because you need to find the maximum area this could only be achieved when you consider longest pairs first.

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Too sad, I can't implement E in time (in 30 mins) :((. How can I improve my coding speed

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

About problem C: Let's consider s[l], s[l+1], .., s[r] so if s[l]+s[l+1]+..+s[r] = r- l + 1 then s[l..r] is good s[l]+s[l+1]+..+s[r] = 1 + 1 + 1 + .. + 1 (r — l + 1) s[l] — 1 + s[l+1] — 1 + ... = 0 so the problem switches to finding the number of subarr (after decreasing by 1 each element) which has sum = 0 (can be easily done by map)

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

It seems testcases are weak on problem E, this slow solution passes. Go ahead and hack it! 89956850

»
5 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

Here's a simple alternate for C: Decrease all the values in the array by 1, and now you need to find the number of subarrays which has sum equal to 0.

Btw, how to solve F?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    Let's try to find the answer for each len $$$l$$$.

    • Let $$$f(pos, len)$$$ = maximum possible number of sets that could have already finished considering $$$s[pos::]$$$ and number of contiguous rounds required is $$$len$$$.

    • Now, If $$$s[pos], s[pos+1] ...s[pos+len-1]$$$ doesn't contains both $$$1$$$ and $$$0$$$ then $$$f(pos,len) = 1 + f(pos+len, len)$$$.

    • Otherwise, find the minimum index $$$idx$$$ in $$$(pos, pos+len-1)$$$ such that $$$s[idx], s[idx+1]..s[pos+len]$$$ doesn't contains both 1 and $$$0$$$ and then $$$f(pos, len) = f(idx, len)$$$.

    The time complexity of the solution will be $$$O(N+N/2+N/3...) = O(Nlog(N)).$$$

    • The solution was simple but I was not able to prove that time complexity is $$$O(N(log(N))$$$ but the the basic proof is that lets in one iteration you are going from $$$pos$$$ to $$$idx1$$$ where $$$idx1$$$ can be $$$pos+1$$$ but in the next iteration you will definitely jump from $$$idx1$$$ to $$$idx2$$$ such that $$$idx2 >= pos + len$$$ thus at max total $$$2 * (N/len)$$$ iterations will be there for a single $$$len$$$.
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you perform step 3?

      I use Segment Tree, so the total complexity is O(n*log(n)^2), and my submission runs in ~1.9s, nearly TLE.

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

        For every index, Calculate the previous index such that it has one and also the previous index such that it has zero.

        • $$$if(s[pos+len]== ?)idx = min(prev_zero[pos+len], prev_one[pos+len]) +1$$$

        • $$$if(s[pos+len]==1)idx = prev_zero[pos+len] + 1$$$

        • $$$if(s[pos+len]==0)idx = prev_one[pos+len] + 1$$$

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

    Can you elaborate more on this?

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Short proof:

      $$$ \begin{align} & \sum\limits_{i=l}^r a_i = r - l + 1 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - (r - l + 1) = 0 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - \left( \sum\limits_{i=l}^r 1 \right) = 0 \\ \implies & \sum\limits_{i=l}^r (a_i - 1) = 0 \end{align} $$$
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for this proof

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

        I understood this proof but why we use frequency to calculate the total answer ?

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

          The goal is to find all possible $$$l$$$ s for our current $$$r$$$.

          Let $$$prefix(i) = A[1] + A[2] + ... + A[i]$$$. Suppose our current prefix sum $$$prefix(r) = x$$$. Since $$$prefix(r) - prefix(l-1) = A[l] + A[l+1] + ... + A[r-1] + A[r]$$$, then for all $$$j < r$$$ such that $$$prefix(j) = x$$$, we know $$$prefix(r) - prefix(j) = 0$$$. We keep the frequency of every $$$prefix(j)$$$ to search for how many of them are equal to $$$x$$$.

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

            Thanks very much . i understood this approach very will.. but in general how can i know like these proofs by myself in the contest !? any suggestions to improve my skills ?

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

              The trick with using prefix sums to calculate subarray sums is very common because it has so many uses. This particular problem is one that comes up every so often. You just need to keep practicing so that you'll learn these new techniques and remember them for future contests :)

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

    think of the brute force solution then optimize it, you can find the answer for any x in O(n) like this

    pseudocode

    this obviously takes $$$\mathcal{O}(N^2)$$$ but we can make it $$$\mathcal{O}(N * log(N))$$$, first for each i compute X[i] = biggest x such that $$$[i, i + x - 1]$$$ doesn't contain both 1s and 0, this can be done in O(n log n) using binary search and prefix sums, now in the loop above replace i += 1 by i = find(i, x) where find(i, x) returns the first j > i and X[j] >= x, this can be done using disjoint-set (initialize the parent[i] as first j > i with X[j] > X[i]) and modify the find function slightly

»
5 weeks ago, # |
  Vote: I like it +59 Vote: I do not like it

could E BE more boring ?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i see the answer for "C. Good Subarrays" in this content but i still can't understand it can any one help me?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell me what i'm missing in Problem D , Locally on G++ 17 all sample test case gave right answer but on CF it is giving WA on 2nd testcase while using G++ 14 and WA on 3rd test case while using G++ 17 . Link to the Code for Problem D : https://ideone.com/i0idJr

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

W

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D why is it important to sort. . . . My thinking, If I'm using exhaustive search using dp, it should give the optimal answer, int this case max area, without even sorting. Please clarify this for me. Thanks

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

    Let's say we have two pairs of one type with lengths $$$a_1, a_2 (a_1 \le a_2)$$$, and two pairs of another type with lengths $$$b_1, b_2 (b_1 \le b_2)$$$, then it's optimal to create a rectangle of sides $$$a_2, b_2$$$ and a rectangle $$$a_1,b_1$$$. This is easy to prove.

    So, after sorting once we pair $$$i$$$ on first array with $$$j$$$ on second array, we'll never pair $$$k < i$$$ on first array with $$$z > j$$$ on second array. So we keep a classic DP.

    $$$dp[i][j][j]: $$$max total area using pairs till $$$i$$$ on first array, till $$$j$$$ on second array and till $$$k$$$ on third array.

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

    If I'm using exhaustive search using dp

    No we are not doing exhaustive search , if we are pairing one from red and one from green , they must be of highest length in there category .

    Did you asked yourself how transition will take place (i.e how we will find $$$dp[i][j][k]$$$ with the help of some lower $$$i,j,k$$$) ?

    $$$dp[i][j][k] = max(dp[i-1][j-1][k]+A_i*A_j,dp[i][j-1][k-1]+A_j*A_k,dp[i-1][j][k-1]+A_i+A_k)$$$

    while taking $$$A_i*A_j$$$ , we will take the maximum ones and thus we need to sort.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please provide a test case where Greedy approach in problem D fails

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve $$$G$$$ without bitsets? Faster than $$$O(X^2/32)$$$

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

    fft

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

      Nice! Karatsuba also works.

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

        Can you please explain your complete approach ?...

        I know that if we have (a[i] — a[j] == t) for some i,j(i > j) and t then we can use an approach similar to sieve and solve... but not getting the fact what is the exact purpose of using fft ?

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

          FFT can be used to get these values $$$t$$$. For this we should calculate $$$(x^{a_0} + x^{a_1} + ... + x^{a_N})*(x^{-a_0} + x^{-a_1} + ... + x^{-a_N})$$$. If coefficient at $$$x^{t}$$$ $$$!=0$$$, then there are exist $$$i$$$ and $$$j$$$ such that $$$a[i]-a[j]==t$$$.

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

    How to solve G with bitset?

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

Problem C becomes so beautiful after realizing its logic.

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

    One more solution to solve such types of problems.

    Let $$$pref[i] = s[1] + s[2] ... + s[i]$$$

    Thus required subarrays $$$(s[L...R])$$$ will follow this property,

    • $$$pref[R] - pref[L-1] = R-L+1$$$

    • $$$pref[R] - R = pref[L-1] - (L-1)$$$

    Or, Basically you can choose any two index such that their $$$pref[i]-i$$$ is samefor both of them. Now, it's basic $$$O(N)$$$ task, using $$$C(freq, 2)$$$ for every frequency of $$$pref[i]-i$$$.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have submitted 2 identical solutions for problem C. Solution A: 89960181 Solution B: 89960214 The only difference between the two is on line 22: In one approach I use an integer to represent the index while in the other I use a long long. I also use in both cases a long long to represent an index in line 53.

Why does one solution pass while the other doesn't? I've already read many forums regarding the indexing on arrays in C++. Nowhere did I found that it says that a long long will cause problems when indexing with it.

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

    You didn't initialize variable out 89961488

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

      Thnx dude I mean I broke my head to figure it out. It is weird thought the fact that 89960214 gets AC. I mean I do not initialize out and because I used an integer for indexing it works for some reason XD

»
5 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

O(n) solution of C with HashMap 89943214

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why the greedy solution of D — "pick two largest pair every time" fails?

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

    Counterexample:

    R: 3 4 5

    G: 5 6

    B: 7

    If you take 2 biggest elements of different colours you'll end up with: 7 * 6 + 5 * 5 = 67

    Though the optimal split is: 7 * 5 + 6 * 4 + 5 * 3 = 35 + 24 + 15 = 74

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

    -> That greedy pairs the both 10 instead of 9,10 + 9,10.

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

      spooky mah boi , why you oscillate between colors so much ?

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

        The crazy problem setters create weird problems ;)

        No seriously, one limitation for me is the ability to concentrate, I am sometimes not able to implement simple tasks, like todays C, even if I know how it works.

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

          When you fell from CM to specialist, I just thought that you are trying to get a record of biggest rating change.
          Yeah, problem setters set such problems that if you get some WA, debugging would take a lot of time. This affects me too.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my approach for C failing? My approach: Every good subarray should start with some index, so i'll brute force for every index checking it for lengths (1,2,...9) . Time complexity O(9*n). It failed for many, example => s = "11140000000090000000002111" , correct ans = 37 , my ans = 29

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

    Consider an array full of 1's. In your solution you ignore good subarrays of length more than 9, which is not correct

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in c i storedd arr[i]-1 for each array and counted the no of subarrays with sum 0 balancing excess with shortage!

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

why my code for D is giving TLE. It is using same approach as DP solution.

code
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Close enough, but learn dp, you'll see why it fails.

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

      i have tried to do DP problems but most of the times i fail to think of a DP solution

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

        You are passing whole copy of vector in the function. Just use an integer for index.

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

    I think rgb() is called for same vectors several times. It's same as when you find the nth element of Fibonacci sequence by iterative method or recursive method.

    The other thing is that whenever you call rgb() it will copy all data from current vector to the next function but in DP no.

    (Sorry for my bad English)

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

      ok i will try to implement DP solution then. my bad i couldn't think of it during contest(sad emoji)

      Spoiler
»
5 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

My screencast, if you want to enjoy my fingers suffering from typing so much (video solutions for A-E included)

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

Why are the hacks shown on the hacking page in reverse order, like the most recent hack is at the end?

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

If anyone has used memoization for D pls do share your code.It would be a great help for a beginner like me as i am learning dp . Thanks in advance

»
5 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it
#include<bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define fi first
#define se second

const int mod = 1e9 + 7;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef double ld;

const int N=210;
int a, b, c;
vll arr(N,0), brr(N,0), crr(N,0);
ll dp[N][N][N];

ll func(int i,int j,int k)
{
	if((i>=a and j>=b) || (i>=a and k>=c) || (j>=b and k>=c))
	{
		return 0;
	}
	if(dp[i][j][k]!=-1) return dp[i][j][k];

	return dp[i][j][k]=max(arr[i]*brr[j]+func(i+1,j+1,k),
							max(arr[i]*crr[k]+func(i+1,j,k+1),
							brr[j]*crr[k]+func(i,j+1,k+1)));

}


int main()
{

	fastio

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	memset(dp,-1,sizeof(dp));

	cin >> a >> b >> c;

	int len=max(a,max(b,c));

	for (int i = 0; i < a; i++) cin >> arr[i];
	for (int i = 0; i < b; i++) cin >> brr[i];
	for (int i = 0; i < c; i++) cin >> crr[i];

	sort(arr.begin(), arr.end(), greater<int>());
	sort(brr.begin(), brr.end(), greater<int>());
	sort(crr.begin(), crr.end(), greater<int>());

	cout<<func(0,0,0);

	return 0;

}

what is the problem in my code for D question? can anyone help me?

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

    Here is my code that passes everything:

    CODE

    I believe your mistake is this line:

    if((i>=a and j>=b) || (i>=a and k>=c) || (j>=b and k>=c)) return 0;

    Instead using ternary operators, like I did solves it. Why? Here's an example. If we take this line into consideration:

    arr[i]*brr[j]+func(i+1,j+1,k)

    We only care if either i or j is greater than a or b in your case. This means that we should not check for (i >= a && j >= b), but for (i >= a || j >= b), since one element is already out of bounds and there is no solution but your code cares only whether both elements are out of bounds, that allows space for error.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Got WA on Test 6 in Question D. The 6th test case given is not intuitive.Can anyone help me out with a intuitive test case similar to the test which is used in testing.My solution is a greedy approach, but not a general one.So test cases such as the below test case will result in correct answer.This is my solution 89953296.

4 2 2

3 3 3 3

4 4

4 4

This test case results in correct answer for my solution.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    3 3 3

    2 8 5

    1 10 5

    9 9 3

    Correct answer : 10*9 + 8*9 + 5*5 + 2*3 = 193

    Your answer : 182

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

I guess people are making fake ids just to hack those submissions afterwards. Deliberately a stupid if case is added to be hacked afterwards XD.

89940459

The hacked guy likes 78788 a lot I guess. One more of his solutions from another contest using his fake id Noob_is_back got hacked. See this 87193319 and you'll find 78788 again in the code. The hackers are still grey :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why we use frequency in problem C ?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My hack has been on "waiting" since this morning. It's not just when I'm logged in, it shows up like that on an incognito tab as well.

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

In the meantime before editorial is published and for those interested, here is the 3Blue1Brown styled visual editorial for Problem C, visualizing tmwilliamlin168's code (89883985). I have also given a somewhat formal proof before visualizing 1st input of Test Case #5

Link to visual editorial here

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to check the time it takes for the submission when hacking?

»
5 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I love problem D very much!!

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

    How to solve E?

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

      I use the line segment tree (weighted segment tree). In fact, it is easy to find that the answer to problem E each line:ans = the sum of the largest number in the first K + the sum of all the numbers (here K refers to how many numbers can be doubled)

      Then we read all the values first, sort them (discretize them), and then read the input of the problem again (which has been changed by array storage in advance)

      We maintain the weighted line segment tree every time, that is, we ask the sum of the top k numbers in the 1-n interval every time. For example, to find the sum of the top 4 numbers, I will first ask whether the number of the right subtree (because the number stored on the right is larger than the number on the left) is less than 4. If so, enter it directly and return the sum of the top 4 numbers under the right subtree. If not, directly Select the sum of the prior numbers of the right subtree and add the sum of the first k = 4-num [RS] numbers under the left subtree (Num [RS] represents the first number of the right subtree),and then return it.

      In short, the answer is to ask the sum of the top k numbers on the line segment tree and add the values of all the current numbers

      (PS: but note that if the minimum value of all the numbers that can be doubled is greater than the maximum value of the number that can't be doubled, we can't simply choose the top k, but we should choose the top K + 1 and subtract the minimum value of the double number, because one can't double itself.)

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

      Maybe my expression is not clear, but you can find ideas from it. It must be feasible because I passed after the contest.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

any news about the tutorial?

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

why this code 89922404 for problem C won't get TLE

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

    The first three lines makes the code really fast.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are Educational Rounds always so late with editorials?

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

    Because of the 12 hour open hacking phase, I guess.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me in D. I used a 3d dp approach, which finds the maximum value using 6 cases. However, it failed on test 5. Here is the failed submission, while here is the one that passes. What does sorting do?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    It's always optimal to chose pairs with the maximum product. So we sort those three lists in decreasing order and take pairs from top of them. But when we have multiple options for pairs with the maximum product we don't know which one we should take without looking at the next values and that's why we do dp.

    $$$dp_{i,j,k} = max(dp_{i,j+1,k+1},dp_{i+1,j+1,k},dp_{i+1,j,k+1})$$$ = maximum area we can achieve when we have already taken first $$$i$$$, $$$j$$$ and $$$k$$$ values of the first, second and third array (according to $$$0$$$ based indexing).

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

      I found your explanation easy to understand, can you tell what does dp[i] [j] [k] stands for i.e what is the meaning of each cell of dp, can you please elaborate it more.

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

        $$$dp_{i,j,k}$$$ stands for the state where we have already used first $$$i$$$ values of first array, first $$$j$$$ values of second array and first $$$k$$$ values of third array.
        The value of $$$dp_{i,j,k}$$$ is the maximum area we can obtain using remaining values of these three arrays in this situation.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C using Binary search?

As there is a tag of binary search in Problem C.

»
5 weeks ago, # |
Rev. 2