By PikMike, history, 12 days ago, translation, In English,

Hello Codeforces!

On Jun/05/2019 17:35 (Moscow time) Educational Codeforces Round 66 (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 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 participants!

UPD:

Our friends at Harbour.Space also have a message for you:

Codeforces! What is the next step in your development?

We understand all about doing things by yourself — after all, we are a startup university, and our student body is exceptional in part because of it’s made up of people who didn’t wait for anyone to show them the way.

If this is you, you belong at Harbour.Space. The purpose of our University is to create a global community of these kinds of people, regardless of age or nationality, because when you’re working by yourself, you can change for the better, but when you work with others, you can change the world.

If you believe you have what it takes, we want you!

The curriculum is part of what makes the modules so special, and the other half? Our outstanding teachers who are leaders in their own respective industries.

Our scholarships are set in such a way that doesn’t require additional applications — we believe in merit and potential, and so what you put in your application to the university will be our criteria.

You could be just the diamond we’re looking for, but you’ll never know unless you apply!

APPLY NOW→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 mango_lassi 6 145
2 E869120 6 148
3 kefaa2 6 154
4 egor.lifar 6 154
5 Aria 6 157

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Radewoosh 97:-19
2 test_hack 56:-37
3 alvinvaja 30:-10
4 AryaKnight 48:-48
5 nikolapesic2802 30:-14
779 successful hacks and 1077 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Geothermal 0:01
B mango_lassi 0:05
C nuip 0:07
D Yushen 0:04
E Sehnsucht 0:20
F osaaateiasavtnl. 0:05
G LgndryGrandmasturbator 0:47

UPD: The editorial is out

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

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

[deleted]

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the consecutive contests! Wish that the problem statements will be neat and clean and short as the previous one. Eid Mubarak everyone!

»
12 days ago, # |
  Vote: I like it +515 Vote: I do not like it

»
12 days ago, # |
  Vote: I like it -42 Vote: I do not like it

Comment "Is it Rated?" if you want to gain contribution points! (In the negative direction)

  • »
    »
    12 days ago, # ^ |
    Rev. 3   Vote: I like it -51 Vote: I do not like it

    Let me do this job for you.

    Is is Rated (for Div1)?
    Ans seems Yes.

    MikeMirzayanov PikMike Please fix it.
    Everyone is registered as "Contestants".
    Mark me and others as "out of competition".

    Div1 in Comp.

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

      No, it is not rated for you. It is rated only for those who are below the master

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it +32 Vote: I do not like it

      It is not a bug. In Educational Rounds no one is out of contest everyone can compete officially but it is only rated for Div2. And after contest in the Final Standings there are options (div1,div2) to see standings

»
12 days ago, # |
  Vote: I like it +32 Vote: I do not like it

thank u, pik misha!!!!!!!!!!!!!!!!! i love you

»
12 days ago, # |
  Vote: I like it +15 Vote: I do not like it

I never really understood the concept of Educational Rounds. Don't we learn something new from every contest? Why exactly term it Educational?

  • »
    »
    12 days ago, # ^ |
    Rev. 3   Vote: I like it -28 Vote: I do not like it

    LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.
    Problems at usual contests: "use a segment tree with some trciky operations and tricky queries"
    Problems at educationals: "use a trivial segment tree, (yes) and queries are in the form of $$$[p_i,i]$$$
    didn't you feel that difference?"

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +63 Vote: I do not like it

      Finally found the person who uses the id LanceTheDragonTrainer.

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no, he uses id riela

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

          LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.

          marymarine is no longer my alt, we disbanded because he doesnt like twice.

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

      Yup, that makes sense. Thanks!

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

      And for us mortals, Educational rounds are ironically harder than the normal rounds, and the editorial comes the same way for both educational and normal rounds, so not even sure what's the point of calling it "educational".

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

        it is your fault if you fail to solve problems
        once more:
        edu rounds -> hard problems with classical ideas
        usual rounds -> hard tricky problems

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

          Yes, I'm just saying how ironic it is for a round that calls itself "educational" is as educational as any other round and it manages to make itself harder than an average round.

          I just don't get it, I literally don't get why it's called "educational", it has no special property what so ever that would make it educational.

          I'm talking about ABC tasks, I'm not qualified enough to talk about the difficulty of DEF...

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, DEF are actually educational

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              If educationals DEF are so much easier than normal round DEF then why does DEF get solved the same/less than in a normal round ? This EDU alone has only like 20 people who solved DEF, maybe 50 that solved DE, and the rest are D

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

                i didn't say they are easier, i meant they are with classic ideas

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You are not in Div2, so they may be classical to you, they're certainly not classical for Div2 users.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                The purpose of contests is for people to solve problems and learn from them I think.

                It doesn't matter if its name was "Educational" or something. If you are good you can solve problem. If you are not you need to learn more, tutorials is a good point.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I'm fine with the rounds, the more the merrier, just saying that EDU rounds are worse than normal rounds imo.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I enjoyed all of the problems. I mean we aren't allow to choose our life condition so we need to prepare for the worst.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I enjoyed the problems of this EDU as well, I'm talking about the previous EDU.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, I'm talking about every problem :)

»
12 days ago, # |
  Vote: I like it +18 Vote: I do not like it

PikMike is a boy or a girl?

»
12 days ago, # |
  Vote: I like it +30 Vote: I do not like it

yes
Konstantin Mertsalov is a nice man , we discussed some math problems with him through skype

»
11 days ago, # |
  Vote: I like it +43 Vote: I do not like it

Eid Mubarak to all Programmer.

»
11 days ago, # |
  Vote: I like it +172 Vote: I do not like it

»
11 days ago, # |
  Vote: I like it -70 Vote: I do not like it

First question has wrong limits on K!! Because of this I lost valuable time

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -53 Vote: I do not like it

    I wonder why im getting downvotes...am I wrong?

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

      what is wrong with the limits?

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it -16 Vote: I do not like it

        k = 1 in one test case but question says k>=2

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you see the test case? How do you know that?

          • »
            »
            »
            »
            »
            »
            11 days ago, # ^ |
              Vote: I like it -13 Vote: I do not like it

            I added the check for k == 1 and it passed

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

              Is that the only difference in your solutions?

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

              If you want to be sure add assert(k >= 2) right after your read input and submit again! If you are right you should get a RuntimeError verdict.

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

              You changed types from int to long long

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

          I don't think it's true. My accepted submission would loop forever on $$$K = 1$$$.

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

      Yes.

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

      because you wrote very trashy comment.

      you are just a pupil after 4 years and you said codeforces contest has a problem ??

      how did you decide to write this comment ?

»
11 days ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

Thanks for the round.

»
11 days ago, # |
  Vote: I like it -28 Vote: I do not like it

The worst B problem I have ever solved

»
11 days ago, # |
  Vote: I like it +7 Vote: I do not like it

I really liked D there's a relation between each possibility but I don't know how this is going to help :/ how did you solve it

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

    Expand the summation using prefix sums everywhere

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

      Is this correct k*ps[n] — (sum of small k-1 smallest prefix sum)

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah

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

          Too bad I cannot implement it. Though this problem looks like some DP optimization which I am not familiar with and started searching articles for it.

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

            don't forget to exclude ps[n] though, while finding k-1 smallest prefix sums.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B!! :'( made it the worst contest I gave on codeforces :/ and why cant we use python3 signal in codes :'/

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

    Problem B is just a simple stack based problem of evaluating parenthesized expressions.

    And as for signal, check the documentation. signal.alarm is unix only

»
11 days ago, # |
Rev. 3   Vote: I like it +19 Vote: I do not like it

I'm so sorry of that. I just wanted to laugh and maybe some upvotes. I didn't think reminding some old joke would be that annoying. Maybe this cause more downvote, but I want to talk some more words. I'm just a kid, please just don't make me cry. :( Last day I started commenting and I got contribution +3. But now it is going down to -4. I'm so depressed by now. I promise I won't write something idiot more. I'm sorry again. Can you help me get my contribution up to 0 again?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +44 Vote: I do not like it
    throw new JokeTooOldException();
    
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Just a reminder. :D

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Which site you use to upload photos there's alot of memes in my mind to post XD

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

          I just got this from another comment on CF

          But I found a site to upload.

          After that I disabled my antivirus and then something special happened to my desktop.(the backgroung and resolution changed suddenly)

          Be Carefull. Btw do you know how to get upvotes?

          • »
            »
            »
            »
            »
            »
            11 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Don't post all the jokes you think about because some of them aren't that funny
            the more unique and unexpected the joke is the more upvotes it will get also the right timing plays a role
            . Btw I did not understand what does the antivirus has to do with uploading a photo.

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

              After uploading I wanted to send it here. I copied the URL and posted it. Then the antivirus blocked it. Because I wasn't sure that it is sent correctly. I turned off the antivirus. And after a few moments that happened. It was my mistake to turn off the antivirus.

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

    D was quite solvable

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

    C is extremely hard to me. lol In my opinion D is easier than C. :)

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Agree. 38 minutes spent on C, mostly staring at piece of paper. 30 minutes for D, no idea why it took so long.

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E?

  • »
    »
    11 days ago, # ^ |
    Rev. 4   Vote: I like it +15 Vote: I do not like it

    Create sparse table such that nxt[i][j] is the maximum index sucht that [i, nxt[i][j] ] can be covered using atmost $$$2^j$$$ segments.

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

      Can be solved using binary lifting (this is the same, but actually easier to code).

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

        Don't we call binary lifting on arrays as sparse table?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how do u prove this?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      During the contest time I was thinking if I can create a sqrt decomposition solution.
      Couldn't find one. Can you think of one? ( I am pretty sure that the time limit can be tight)

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have one in mind. For all precompute the ans for all [i, j] such that $$$j - i < \sqrt{n}$$$. Then the queries for $$$y - x < \sqrt{n}$$$ can be answered in O(1) and for others in $$$O(\sqrt(n))$$$

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, I had similar in mind.
          But I realized, it can be troublesome when an interval ( say [li, ri]) lies inside 2 blocks (say, [√n+1, 2*√n] call it block1 and [2*√n+1, 3*√n] call it block2).
          Because, that time when we loop through block1 and block2, I am not sure how to combine their answers. Are you able to feel the difficulty? Or do you have a better approach to it?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Would you like to elaborate more on how do you use the sparse table to find the minimum number of segments?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    Let 1, x2, x3,...,n be index where new subarray starts. Then answer is f(1)×1 + (f(x2)-f(1))×2+....+(f(n)-f(x_k-2))×k. Open it. f(i) is prefix sum till i'th element.

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

    You can extend this proof to general k segments

»
11 days ago, # |
  Vote: I like it +7 Vote: I do not like it

can't we solve C using the ternary search?

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    No you can't 55147246

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but is there reason for it ?

      I mean isn't the function unimodal or some other reason ?

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

      Why go for ternary when you can do with binary?


      Ref: 55155030
      I used binary search on answer over f(x). Now if f(x) exists, it means that x must be equal array[i]+f(x) or arr[i]-f(x). Iterate over the array to find such possible 'i' where you get at least k-1 elements in the array which are less than or equal to f(x) (using upper bound). If you find any such 'i' then modify r, else modify l.
      f(x) = (l+r)/2 i.e. mid
      Hope it helps! :)
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. because the f(x) might be something like sin(x) (just for imagination!). suppose there are k + 1 points close to each other, then a huge gap then again k + 1 points close to each other, then a huge gap and so on...

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

      Ok. to clarify my idea let's see this test case

      4 0
      10 20 30 40
      

      k = 0 so $$$f_k(x)$$$ means the distance of the closest point to x for each integer x. the graph of $$$f_k(x)$$$ will be like this :

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C?

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

    Average of points which have k-1 given integers between them.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain the correctness of this approach?

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If the solution you get from that is not correct, that means you could move left or right. If you move left, you will be further away from the point on the right, which means you are no longer at the minimum. If you move right, you will be further away from the point on the left, which means you are no longer at the minimum.

        So, you just want to find the 2 given points that have k-1 given points between them, and the average of those 2 points will be your answer.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you need to find k nearest points (summ(a[j] — a[i]) -> min, j = from 0 to k) in array and calc its middle point

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

    My solution lets find minimal distance using binary search. Suppose the answer is X.

    Then, our answer point should be in the distance X for at least k points.

    Second part is just easy to check if there is a point where k segment intersect [a_i — X, a_i + X].

    Complexity O(n * log^2)

    But can be easily implemented in O(n * log)

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

      why are you using binary search? if you already knows the greedy approach to check the answer, you can just do it without guessing the answers ... just get the mininum distance that a X point have the elements. The X with this minimum distance is the answer.

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

        The problem that I don't know the minimum distance, I use binary search to find it.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the proof of correctness of C?

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

    Have you solved it? Well, supose X is outside the range we are right now. Then its better to put it inside the range, to decrease the distances of the k consecutives elements. The ans is the min middle point of all ranges with lenght K. (the best point is the middle one because it gives us the least k minimum differences).

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

when will tutorial soln for educational contest will come

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

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

    D̶&̶C̶ ̶D̶P̶ ̶o̶p̶t̶i̶m̶i̶z̶a̶t̶i̶o̶n̶ I'm actually not sure(there is no editorial for task, so I wrote what i remembered it was), thx for pointing it out

    By the way, the problem is not original, statement is only in romanian though

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

    I have an $$$O(NKlog)$$$ solution for G but still havent been able to implement it until now which ruins my rating as always :)

    So we lets denote $$$MAX(L, R)$$$ be the maximum value in the subarray $$$[L, R]$$$, and $$$F(i, j)$$$ as the minimum weight of splitting first $$$i$$$ elements to $$$k$$$ subsegments.

    By that, we have $$$F(i, j) = min(F(x, j - 1) + MAX(x, i) * (x - i + 1)))$$$ for every $$$x ≤ i$$$.

    Lets have an observation:

    We can separate $$$(i - x + 1) * MAX(x, i)$$$ to $$$(i - 1) * MAX(x, i) - x * MAX(x, i)$$$. As always, we will have some data structre like Convex Hull or Lichao Tree to query for the minimum $$$w* MAX(x, i) - x * MAX(x, i) + F(x, j - 1)$$$ for $$$w = i - 1$$$.

    Now, normally, one will always think of idea of iterating elements from left to right, maintaining the stack of maximum elements and trying to do something about deleting and pushing elements to that stack. As every time $$$MAX(x, i)$$$ changes, we will need to reset our Convex Hull or Lichao Tree over again.

    Lets fix $$$i$$$. Now our stack will represent the changes of the $$$MAX(x, i)$$$ if we iterates $$$x$$$ from $$$i$$$ to the left. And for every fixed $$$k$$$, the elements that satisfy $$$MAX(x, i) = k$$$ lies on a continuous subarray. So my main idea is for each $$$k$$$, i will first find the $$$x$$$ that minimizes $$$-x * k + F(x, j - 1)$$$ before we actually inserting it to our Lichao/Convex Hull.

    To do this, you can think of an segment tree which each of its node has a Convex Hull or Lichao tree to take this query. And we will use Convex Hull in this case. If we notice that every time we try to change the $$$MAX$$$ of some subarray by deleting some elements from our stack, their $$$MAX$$$ only gets bigger and bigger. So if we use Convex Hull, we can actually handle queries in $$$O(1)$$$ by using the pointer trick instead of binary searching.

    Now once we get the best $$$x$$$ for our $$$k$$$, we will insert a line $$$(k, -x * k + F(x, j - 1))$$$ to our Lichao Tree and take queries later.

    But another thing to notice is that if some elements are poped out from our stack, the Lichao tree should also be changed. But luckily, only the top elements are deleted from our stack so its prefix is still the same. Here, we can use a persistent Lichao Tree to handle this case.

    So my time complexity is actually $$$O(NKlogC)$$$ for building the segment tree of ConvexHull and $$$O(Nlog)$$$ memory for having a persistent Lichao Tree.

    Since this solution is pretty much disgusting, I hope its not author's solution. But i dont want his solution to be $$$O(Nkloglog)$$$ either cause I didn't expect it to pass and spent all my contest thinking of a better (not the one above lol) one.

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

      "...I hope it's not the author's solution..." - Your hope is futile.

      On the other hand, I was sure, that there would be much better solutions.

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it +29 Vote: I do not like it

        Here's a similar solution but maybe easier to implement.

        Denote $$$D_{i, j}$$$ as the minimum cost to split prefix $$$i$$$ to $$$j$$$ subarrays. we fix $$$j$$$ and solve the layer in $$$\mathcal{O}(n \log n)$$$.

        We compute the answer for all $$$i$$$ in a D&C fashion; to compute the answer for all $$$l \le i \le r$$$, first recursively solve for $$$[i, m], [m + 1, r]$$$ where $$$m = \frac{l + r}{2}$$$, and then we consider transitions between the two halves.

        define $$$A_i = \max(a[m+1...i]), B_i = \max(a[i...m])$$$, the transition is

        $$$D_{i, j} = \min_{k \le m} (D_{k, j-1} + (i - k) * \max(B_k, A_i))$$$

        Notice that due to monotonicity of $$$A, B$$$, for fixed $$$i$$$ there is a suffix of the first half where $$$A_i$$$ is larger, and a prefix where $$$B_j$$$ is larger. We can solve both cases independently;

        $$$D_{i, j} = \min_{k \le m} (D_{k, j-1} + (i - k) * A_i) = \min_{k \le m} (D_{k, j-1} - k * A_i) + i * A_i$$$

        We have a linear function inside (for constant $$$k$$$), so we can maintain those in a cht. When we increase $$$i$$$, the suffix in which $$$A_i$$$ dominates increases, and we repeatedly add functions with smaller slopes, so we can do this in $$$\mathcal{O}(n)$$$.

        The case when $$$B_k$$$ dominates is almost identical, same analysis.

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it +14 Vote: I do not like it

        Here's another boring solution.

        As many said, DP formula should be like $$$dp(i, R) = \min(dp(i - 1, L - 1) + (R - L + 1) \cdot \max(a_{L}, a_{L + 1}, \ldots, a_{R}))$$$ $$$(L \leq R)$$$.

        Now let's rewrite this formula using $$$a_{M}$$$ $$$(L \leq M \leq R)$$$ as any maximum element in that subarray, and then we can boost the transmitting process of $$$L \to M$$$ and $$$M \to R$$$ separately.

        Denote $$$[left(M), right(M)]$$$ as the maximal subarray that contains $$$a_{M}$$$ as its maximum element. For each $$$M$$$, we first calculate $$$f(M) = \min(-(L - 1) \cdot \color{red}{a_M} + dp(i - 1, L - 1))$$$ $$$(left(M) \leq L \leq M)$$$, and then we update $$$dp(i, R)$$$ $$$(M \leq R \leq right(M))$$$ by $$$(a_M \cdot \color{red}{R} + f(M))$$$.

        In both parts, we only need to answer the minimum inner product for a query 2D vector (e.g. $$$(a_M, 1)$$$ or $$$(R, 1)$$$) with one vector (e.g. $$$(-L + 1, dp(i - 1, L - 1))$$$ or $$$(a_M, f(M))$$$) selected from a certain set.

        To implement easily, we can maintain two segment trees of convex hulls offline. Since we don't need to support insertion and query for segments simultaneously, and we can sort the points in increasing order of the first coordinate, we can solve the problem in $$$\mathcal{O}(n k \log n)$$$.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    It can be solved with ordinary segment tree. With time complexity O(NKlogN). Our dp will dp[k][n], where k is number of groups, and n is representing last added to some group. Now let's focus on solving only one dp layer in terms of group. Update segment tree by setting cost of each index to value of dp[prevgroup][that_index]. Now iterate from left to right, suppose that we are at index i now. Each index will have some cost in segment tree. Now our reccurence will be dp[i] = min dp[j] + cost(j,i). This can be easily found if we can calculate efficiently cost(j,i). Instead of calculating it each time, we will somehow update it efficiently. We can do so by grouping elements by maximum element from them to our i. Now one can see that when moving right, we can find where this element represents maximum. And set it as maximum for new group, while deleting previous groups that those elements belong to. Only thing that is left is that maximum is multiplied by length. We can handle this again by segment tree arithmetic progression update (it can be found easily on net, i am lazy to write about it now). I hope i helped.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems like there will be a problem to combine operations "add arithmetic progression to a segment" and "find minimal value on a segment".

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

why ternary search is not correct for problem C? i am getting WA on test case 2.

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

    Ternary search (to find crest) holds good for a function whose value keeps on decreasing till some point, then keeps on increasing.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my this solution for B is failing on test 8 . Solution

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

    your answer bigger than 2^32 so you should puts OVERFLOW!!!

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    seems that u need to judge if no>0 when adding to ans

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

      But when no > 0 sum will be ~1e15 so I think there is no need to do it .

      By the way I'll see . Thanks for your time .

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

    you missed a few cases while handling your 'no' variable, just made required changes 55178901

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

What is the hacking penalty and profit for Educational round?

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

    There is no direct addition in score on hacking a problem in Educational Round but it seems quite a good debugging practice

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

Can anyone help what's wrong in this submission for Problem B. 55174319 Thank you!

»
11 days ago, # |
  Vote: I like it +50 Vote: I do not like it
»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

What is hacking test case for B)?

»
11 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Why there are so many hacks in B? Weak Test Cases?

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

    code which loop through vector/stack every time they add the number can cause TLE.

    the test case looks like this.

    100000
    for 1    x 10000
    add      x 80000
    end      x 10000
    

    mine got hacked too :)

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

I saw some of the solutions for F rely on the fact that the answer will not be too large. Does anyone want to give a proof/intuition on that?

  • »
    »
    11 days ago, # ^ |
    Rev. 3   Vote: I like it +54 Vote: I do not like it

    Let a valid subarray be $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$.

    Observation 1: Pick up all the elements of value $$$1$$$. For every two adjacent elements $$$1$$$, denoted by $$$a_{x}$$$ and $$$a_{y}$$$, if $$$l \leq x$$$, then it must be held that $$$x \leq r < y$$$.

    More generally, for every three adjacent elements $$$1$$$, denoted by $$$a_{x}$$$, $$$a_{y}$$$ and $$$a_{z}$$$, $$$x < l \leq y$$$ must lead to $$$y \leq r < z$$$.

    Observation 2: Let's fix the position of value $$$1$$$ as $$$a_{k}$$$ ($$$l \leq k \leq r$$$). Without loss of generality, we assume the position of value $$$(r - l + 1)$$$ is on the right of $$$a_{k}$$$, and then we can conclude the only one possible $$$l$$$ by enumerating $$$r$$$, as we know $$$l = r + 1 - \max(a_{k}, a_{k + 1}, \ldots, a_{r})$$$.

    Consequently, there are at most $$$2 n$$$ possible subarrays that we need to check if the elements in each subarray are distinct.

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

Why this solution of D is wrong? Take the cut $$$[ k, n ]$$$ and find maximum suffix of it, $$$[ l, n ]$$$. Increase answer by the sum on $$$[ l, n ] * k$$$. Then find the maximum suffix of $$$[ k-1, l-1 ]$$$ and so on. In the end, if there some elements in the beggining of the array, which weren't counted in any suffix, also add them to answer. We can do all this with the segment tree in $$$O ( ( n + k ) \log n )$$$.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

please anyone explain for problem C if t=1 n=3 k=2 a[]={ 1 , 2 ,5 } how answer is 3 thanks in advance

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The points are 1,2,5 Let us pick our point as 1, so the distance from 1 to all the given points in sorted order is 0,1,4 For 2 it is 0,1,3 For 3 it is 1,2,2 For 4 it is 1,2,3 For 5 it is 0,3,4

    So we can see that, for 3 we have the minimum (k+1)th distance.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks i was trying to print Kth mimimum distance instead of for what value of x Kth value will be minimum.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

55182007 (Problem B) Why do I get a runtime error? It works just fine on my system.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, I guess when the first add operation is executed, the size of your vector v is 0.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me why it gives WA in test 9? https://codeforces.com/contest/1175/submission/55166598

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Was I the only person who felt B was trouble-some and spent more time on it compared to C and D?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell me why I will get WA in T5? Thansk. 55187500

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually lld has max capacity of 10^18 and that would pass when 100 would be multiplied greater then 9 times, and thus surely in test case 5, the case is that only, I did the same mistake

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem is in this part:

    if(tmp*x>=LIMIT){ cnt++; }

    what if there is no add inside the loops, but you still increase cnt and print overflow.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But I solve this case like: else if(str=="end"){ if(cnt>0) cnt--;

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think I am so stupid that I will ignore the x of input,if cnt>0 :(

»
10 days ago, # |
  Vote: I like it +4 Vote: I do not like it

At first, there was a legend related to the name of the problem, but now it's just a formal statement.

Does someone know about that legend?

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

editorial?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B it was specified "x is an integer variable and can be assigned values from 0 to 2^32−1" so doesn't it means the range of x is [0,2^32-1] and the number 2^32-1 should be included or my English is just bad?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My Submission got accepted during the contest 55132811 but after the contest ended the status changed to Compilation error. I checked the same code on custom invocation and it compiled without any errors. What the heck is going on!! Can somebody explain?

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Ok, feels lucky for being expert again :^)

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone! Answer me please. Why is my solution for C getting TL? What's wrong? https://codeforces.com/contest/1175/submission/55161342 Please, help)

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Looks like slow output, check for fast java input output methods.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Help!! Could someone please explain how to solve C what does ar[i+k]-ar[i] even mean;

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In my opinion, it's because the first k value will be generated in a[i] ~ a[i + k] intervals.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To answer on task's question you should find the smallest interval which include exactly k points.

    My submission: 55152560

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint for F?

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

    (l,r) is a subpermutation iff r = max(l,r) + (l-1) and all values in(l,r) are unique. so we try to find out how many valid l are there for a fixed r, and this can be done by a segment tree with lazy propagation

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

      Can it be solved via BFS? Start bfs at each 1 with state (i,i+1), from (l,r) next state is (l-1,r) if a[l-1] == r-l+1 and (l,r+1) if a[r+1] == r-l+1. Increase answer by 1 for each state reached. Bound is number of permutations, which should be much less than N^2.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think, it can be solved by BFS .

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You're right, I missed the statement by a mile.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain how to find number of valid l for a fixed r using segment tree with lazy propagation

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

        If all values are unique in range (l,r) then r <= (l-1) + max(l,r). Its equal only when (l,r) is a subpermutation. So for a fixed index r, in each l such that l<=r we need to have (l-1)+ max(l,r), and in each node of segment tree we need to store the minimum in that and a count denoting in how many indices that minimum occurs. As you go right and your r changes, the max (l,r) for some l is changing. You can maintain the maximum with the stack technique. And in segment tree you need to handle that with lazy propagation. You can have a look at my code for a better understanding. 55194670

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me find the problem with my code for problem B ?

Submission: https://codeforces.com/contest/1175/submission/55197218

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The value val should be (1<<32) — 1 instead of just (1<<32) . Read problem statement to sure

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for reply. But, I used '>=' to check for overflow considering that.

»
10 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can anyone explain why it is giving wrong answer on test case 8 in problem B? My submission-55198130

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read a bit above . Mb it will help you

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have applied the overflow condition whenever I am adding but still I cannot understand why I am getting wrong answer on test case 8

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if(checker>(int)pow(2,32)-1) . Here is your problem.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        sarthakoherwal, your code will fail for this test : 4 for 2^32-1 add end add

        You have to apply additional overflow check in the else if loop after the line 'x+=checker'

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

    are you checking for if( x > (int) pow(2,32) - 1 ) then cout<<"OVERFLOW" ?

»
10 days ago, # |
  Vote: I like it +7 Vote: I do not like it

where is editorial ??

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Why isn't the editorial out yet?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When will tutorials come ?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the problems of these latest contests are not tagged their difficulty pointers?( e.g. *1500, *1200 etc) Does anybody know the reason?