Educational Codeforces Round 94 [Rated for Div. 2]
By awoo, history, 4 years ago, translation, In English

Hello Codeforces!

On Aug/25/2020 17:35 (Moscow time) Educational Codeforces Round 94 (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 Neon 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 neal 7 179
2 tmwilliamlin168 7 210
3 jiangly 7 235
4 kmjp 7 236
5 LayCurse 7 245

Congratulations to the best hackers:

Rank Competitor Hack Count
1 orz 54:-1
2 anuragsingh804 31
3 Loveforever 20:-3
4 dapingguo8 16
5 celestialcoder 15

401 successful hacks and 778 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A neal 0:01
B jiangly 0:05
C gleb.astashkin 0:07
D balakrishnan 0:06
E lebowski998 0:04
F rainboy 0:43
G rainboy 0:19

UPD: Editorial is out

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

Comments Comments (268)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -76 Vote: I do not like it

0

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

Gladly waiting for div4 && div3 Contest..........

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

"You sleep while we work: due to technical reasons Codeforces may be unavailable on August 24 on time interval 21:00-23:30 (UTC)."

Ha ha, I am in UTC-7 timezone, so for me at this hour I am wide awake!

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

    West coast be like: Aww I have to wake up early for CF contests

    East coast: sleeps in until 10:25 and doesn't miss the contest

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

    You sleep while we work It's not a statement, it's an order.

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

    mike mirzayanov is from russia) so russians sleep at this time)

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

Codeforces is the best way to spend time in this pandemic

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

    https://bfy.tw/Ormx

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

    In normal Div 2 ,weightage is different for all question, but in Educational contest weightage is same for all questions,and Ranking is based on penalty and no. of questions.

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

      Anushk-24 can you explain/elaborate this please?

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

        In the classic div 2 rounds you get a different amount of points for solving different questions. For example you get for A 500 points, for B-750,C-1000, and so on, but in the educational rounds this doesn't exist and you get one point for each question you solve. Also, in the classical Div 2 rounds you get less and less points for problems as time goes but in Educational round you get penalties.

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

    smh people changing comment content to avoid getting more downvotes

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

Finally...

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

In the recent Educational Round, I unable to have some positive rating. Expecting positive this time. Give me your wishes. Cross fingers.

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

Hoping to remain expert this time :)

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

Hope that queue does not occurs.

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

Can anyone please tell me what is the speciality of Educational rounds?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    • Every question has equal weight-age
    • 12 hour open hacking phase
    • Some problems are standard/classical
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what it the meaning of "equal weight-age" ?

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

        If you solve A and if you solve F, you get the same result.

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

      Some more -

      • No "Failed System Tests" Disappointment
      • Takes a long time for ratings to change
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Actually there's a systest phase after the hacking phase(contains all successful hacks), and your solution might fail during that phase.

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

          That's true but people usually don't wait till that long and directly see the rating changes. That feel of "Running on Test Case X" is unmatchable.

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

Greetings to the Harbour Space university :D I think problem solver students in there are lucky to have this great community:D Always forward :)

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

Hoping for a positive delta :)

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

became pupil first time in last contest. Hope will maintain this status :)

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

Kudos to Team vovuh BledDest awoo for organising awesome contests.

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

wish me good luck

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

This kind of ordering?? You just destroyed me.

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

Problem B makes me rethink my whole life.

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

Felt B was even harder than D. Still, I am not sure about my solution. And I think I've seen E before on CF

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

    Yes, E is exact copy of:

    448 Problem C

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

      Not exactly. In E you can not perform an operation if any element being affected is already 0. In that problem you provided a link to it says that it can be appliead as many times as you wish

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

The most disgusting codeforces round I have ever participate. B has misleading statement. C gives a useless and misleading range of x. E is an so old problem. The most bad experience.

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

    I have idea just now. I could have done this. That irritating B costed me. Disgusting round. Don't order problems in terms of difficulty

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

    What exactly is misleading in B and C statement?

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

      Many are confused in C for -1 condition !

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

        -1 is when there is no answer, and it is clearly stated in the output format. Figuring out when there is no answer is a part of the problem.

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

          why do u give an range of x by [1,|s|-1]. It is absolutely useless. If you want to make both w[i-x] and w[i+x] unexist, plz just make x in any range or a not such a range make some participants think it have some meaning.

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

            $$$x \in [1, |s| - 1]$$$ is exactly the range where the value of $$$x$$$ does have some meaning.

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

      For B

      You don't care what to take, since each of them will melt into one steel ingot.

      But the question is to maximize the no of weapons, so it does matter what he chooses. The one with the lesser cost will give us more no of weapons.

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

        Bruh how can u get confused by this. If it stated how you maximize weapons it is giving u the answer.

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

          I didn't get confused as such. It's just contradictory in my opinion.

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

      And so many participants think B as the most volume,just because you state that melt them. Why give such misleading statement?

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

        Well, there are two places where it is clearly written that we have to maximize the number of weapons (the output format and the last sentence of the statement), and exactly zero places where it is written that we have to maximize the weight.

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

          I think that such misleading statement dost not exists in most codeforces round I have ever participate. It is an online contest with tight time bound, we do not want to practice like an reading contest.

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

            I think you have lost your mind and cool:).... Take a break.... Because you need it... The problem setters got nothing to do with it if you read the problems in a wrong way... So just don't lose your cool buddy..

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

            I didn't find the statements misleading in any sense. And FYI, BledDest has written more contests than you have participated on Codeforces.

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

              sry,I participate codeforces contest for about 10 years. I complained because many participant got confused as me. U can have different view, but such attack is too naive.

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

                10 years? Your account history says otherwise..

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

                  First, I do not think this is the key point.But I can reply that I create new account after retired from ICPC. I think everyone have the right to comment a codeforces round. I played really bad in some past round, but I do not complain about it. I complained because this is the first round that I have ever seen that so much participants(maybe just in china around me) got confused with the statement. So I think I should let the round maker known what happened.

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

                  Yes, you're right. You do have the right to disagree with the setting of the statements, just as much as we do in telling you that you're slightly over reacting about the said problem statements.

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

                I bet I'm better than your 10 years

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

                  Plz do something to prove that yourself instead of bragging here. Maybe after ten years you won`t even be able to participant WF :)

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

How to solve E?

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

    448C - Painting Fence

    This is an exact replica of that problem. How lucky (and hardworking) I am to have solved it!

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

      that's why UpSolving is important... xD

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

      Is it? In tbat problem it says that you can paint a fence that has already been painted. And in E you cannot perform an operation if its range contains an element which is already zero.

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

        Yeah, but solving E is equivalent to solving Painting Fence because in the optimal sequence of Painting Fence, we never perform an operation on an already painted part of the fence. (Proof by contradiction)

        But the two problems are slightly different in the ranges of $$$a_i$$$. This makes Painting Fence a subtask of Problem E, but they are almost the same. (I used the same code for both problems because when I solved Painting Fence two months ago, my solution was a bit different from the editorial which incorporated $$$a_i==0$$$ part).

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

    dp[pos][k] where pos is the prefix we are at and k is the number of active 2nd type queries and gives minimum answer to make all elements till pos equal to 0

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

goodbye ratings.

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

How to solve Problem D?

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

    Iterate for $$$j$$$ and $$$k$$$, Now you need a index i such that $$$a_i = a_k$$$ and $$$i < j$$$, similarly, you need index $$$l$$$ such that $$$a_j = a_l$$$ and $$$k < l$$$, this suggests us to store two things.
    $$$1$$$. $$$pref[i][j]$$$ be the number of times $$$j$$$ appeared from $$$1$$$ to $$$i$$$
    $$$2$$$. $$$suff[i][j]$$$ be the number of times $$$j$$$ appeared from $$$i$$$ to $$$n$$$
    Now, rest is quite easy.

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

    There are only at max $$$n$$$ distinct numbers, so lets consider the case where each of them are used as $$$j$$$ and $$$l$$$, lets call this number the $$$divider$$$. So for each $$$divider$$$, we iterate left to right across the array, lets say the current number is $$$cur$$$. There are two cases:

    1. $$$cur$$$ $$$\ne$$$ $$$divider$$$ — Then we want to add the number of pairs for which this position is $$$k$$$ and some previous position of $$$cur$$$ is $$$i$$$, lets say it is $$$cnt_{cur}$$$. We'll add this to the answer and also store $$$cur$$$ in a vector with contains all non-$$$divider$$$ numbers visited (if its visited multiple times its stored multiple times). I'll explain how to calculate $$$cnt_{cur}$$$ in the other case.

    2. $$$cur$$$ $$$=$$$ $$$divider$$$ — Then we want to add all possible values which act as $$$i$$$ to their respective counts. Clearly each number in the vector we stored can act as $$$i$$$ if this position acts as $$$j$$$, so we just add 1 to $$$cnt_{x}$$$ for each $$$x$$$ in the vector.

    Also, we have to consider the case where all 4 numbers are the $$$divider$$$, but this is simply $$$cnt_{divider} \choose 4 $$$.

    Now since we're iterating over $$$n$$$ distinct numbers and iterating over the whole array in $$$O(n)$$$ each time, and operation 2 is clearly $$$O(n)$$$, it may appear as if the total complexity is $$$O(n^ 3)$$$. However we can observe that $$$cur$$$ $$$=$$$ $$$divider$$$ can only occur $$$n$$$ times over all iterations as each position has only 1 value. So operation 1 which takes $$$O(1)$$$ time is run $$$O(n ^ 2)$$$ times and operation 2 which has complexity $$$O(n)$$$ is run $$$O(n)$$$ times, so overall $$$O(n ^ 2)$$$ which easily passes.

    My submission — 90967360

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

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

    I iterated for i and k and maintain some arrays which mean:

    lft[x]: how many x appears in the range [i+1,k-1]

    rht[x]: how many x appears in the range [k+1,n]

    cnt[x]: how many pairs of (x,x) with the first x in [i+1,k-1] and the second x in [k+1,n]

    Apparently, (cnt[x] = lft[x] * rht[x] ) always hold but we can't iterate for x (which cause TLE). But note that with the same i, we move k from k to k+1 will cause only the change of cnt[a[k]] and cnt [a[k+1]], so cnt[] can be maintained with O(1) and the solution is O(n^2)

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

How to solve B?

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

      Tried with that but WA

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

        Go from 0 to number of swords.

        In each iteration. You try to take i swords and if you can't all swords then give remaining to your follower.

        Now, take as much as axes you and your follower can with remaining weight capacities.

        Find maximum answer from all of them,

        Not so nice Implementation

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

          Ohh no. Another silly mistake

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

            If u started ur loop with 1 instead of 0 .. we are in the same boat buddy .... this mistake cost me the whole problem

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

      What kind of hint is it ? :)... It is also given in the statement(number of swords < 2*10^5)...

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

        Some people like me ignored it. After reading the problem second time I noticed that it is less than 2*10^5

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

          Okay Fine... But to be honest I laughed so hard on your hint.. and I am still while writing this comment... Great Hint:).. Don't take it personal man...

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

    The solution is greedy. First, if s>w swap them and the number of sords with the number of axes. Make a for from 0 to x axes that you take where x is the maximum available given, check if it's possible to take that many, then add as much sords as possible, then add as much axes as possible to your friend bag then add as much sords as possible to your friends bag. That's it!

    Link to my code: 90946553

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

B should be placed after C :(((

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

    After D

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

    Why? It is just a basic brute force.

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

      Though it is a basic brute force but many might have been stuck if they took the path to solve it via Linear Programming

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

        That doesn't increase a problem's difficulty.

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

Copy pasted E from here

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

    :(

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

    The problem may seem standard but I am curious about how you found that EXACT problem that E was copied from

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

      Practice...

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

      I remembered solving this problem somewhere. And I remembered that it involved painting the walls. Then I googled and got the problem.

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

    I had also found this, but wasn't sure if they are same. Checkout the last condition in the link you shared. "Note that you are allowed to paint the same area of the fence multiple times."

    Is it the same, as I think we can't the operation in today's problem if not sufficient Ai for which we intend to do operation?

    Maybe I'm missing some observation. Please clarify toxic_hack

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

      Even if you are allowed to paint the same area of the fence multiple times, that would not reduce the number of operations needed.

      You will not need to paint it horizontally twice, because you would have combined the horizontal operation.

      Neither do you need to paint vertically twice for the same reason.

      After painting horizontally in the optimal fashion, there are no unpainted block under a painted block. There is no need for a vertical paint to go over a block painted horizontally.

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

    I Accepted 448C

    but I don't know E is the same as 448C,I'm fool ,lol.

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

Fucked-up-order-forces

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

Still waiting for the day I'll turn expert. (The grind is still on)

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

How to solve G?

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

    Inclusion-exclusion, answer is C(cnt[i], i) if m = 0 where cnt[i] is number of people j with l[j] <= i <= r[j]. If m > 0 then for each mask you need to calculate intersection of segments, and subtract\add C(cnt[i] — badCnt, i — badCnt) for L <= i <= R (badCnt is number of unique people in mask, [L, R] is intersection of segments). Since badCnt <= 40, you can precalculate it with prefix sums.

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

    Inclusion-exclusion on the subset of taken pairs of mercenaries that hate each other.

    Suppose that we fix a subset of pairs we take, this subset denotes the subset of mercenaries we have to take (up to $$$40$$$ of them). For these mercenaries, intersect the segments $$$[l_i, r_i]$$$ to get the range where the size of the subset will be (let it be $$$[L, R]$$$).

    Suppose there are $$$k$$$ mercenaries we have to take. Then we have to compute $$$\sum_{i=L}^{R} C(c_i - k, i - k)$$$, where $$$C(x, y)$$$ is the binomial coefficient, and $$$c_i$$$ is the number of mercenaries that are allowed in a subset of size $$$i$$$ ($$$i \in [l_x, r_x]$$$ for those mercenaries). The key observation is that $$$0 \le k \le 40$$$, so we can build $$$41$$$ arrays of those binomial coefficients and use prefix sums to quickly get the sum on range.

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

    I believe the crux was that max complete combos never exceeded 2^20

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

Can someone just give a hint for B?

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

Is Linear Diophantine Equation used for Question 2?

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

    No,It can be done without this theorem.

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

    You can draw a coordinate system in the form of linear programming. According to the slope, the answer must be one of the two endpoints.

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

Wrong Answer on test 2

Story of this contest

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

what is wrong with my code for C, plz help, i'm desperate and i can't find the mistake. 90982135

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

    plz help

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

    I couldn't understand that long code but here is how i upsolved it: First we only know that we will get a 0 only if there is no '1' on i+x and i-x indices. (Update both indices to '0') then, for each '1' in s, we check if at least one char either i+x or i-x is 1. if both are '0', print -1. else print 1's in all un-updated indices and updated will be '0' from the first step.

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

      tks, but i think i understand my mistake, i should have initialize the answer with all ones.

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

        Seems like that wasn't the only mistake. I'm no expert but i think that shorter code like this is easier to debug.

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

isn't E divide & conquer dp?

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

    Yes and it's actually pretty easy.... Almost solved in during contest and feeling regretful now...

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

Thanks for the best B ever. Must say it was a bit humiliating when i started solving it first but it turned out to be the best decision of my life when i decided to move on to C rather :) .

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

    Great decision. I wasted an hour on B. Couldn't even read D which I was able to solve in 10 min after the contest.

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

      Can you help as how to see rank after the contest? I'm unable to find myself.

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

    I failed just because of starting the loop from 1 instead of 0 ... feel me lol

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

I found B very interesting..

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

    shouldn't have wasted that much time on B, C was waaayyy easiear and doable than B.

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

      Yup,I also wasted a lot of time in B ,since I thought that problems are in SORTED order...

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

Can someone give any hints for F?

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

    The total length of $$$x$$$-prime strings is not too big (somewhere around $$$5000$$$), so we have to generate them, build an Aho-Corasick automaton and implement the following dynamic programming: $$$dp[x][y]$$$ is the minimum number of characters from the first $$$x$$$ we have to remove, so the resulting state in the automaton is $$$y$$$ (make sure to mark the bad states of the automaton, that is, the states where some prime string ends).

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

      Haven't really heard some of the terms you used. Guess this problem wasn't intended for me to solve. Appreciate the reply BTW :)

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

        We will try to explain this technique in editorial

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

Hi all, can u help me? Sorry, I bad at English.... https://codeforces.net/contest/1400/submission/90954904

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

    cases of for having '1' is ambigous, but have a '0' is obvious. why are you considering '1's first?

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

    check this test case: 11110 1

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

4 Times "WRONG ANSWERE ON TEST 2"...

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

This contest has been weird-order-forces, greedyforces, and WA on Pretest 2-forces.

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

Can anyone tell me what's wrong in my approach for C. I created the original required array(say arr) by using the conditions in a reverse way, then I created another array using those conditions in a given way array(say s2) By using arr. Then I checked if the input string (say s1) is not equal to s2, the answer is -1 . Else print the array (arr). my WA

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

    no there could be multiple answers. so finding one possible and then checking if it matches input is obviously wrong.

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

      I think you misunderstood. His logic is right but maybe some implementation mistake.

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

      I did the same thing and got accepted 90966489

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

      You are correct. My mistake was, suppose if i=1 then both i+x and i-x (if existed) is not necessarily 1.Thanks.

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

Problem D looked like a standard interview problem.

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

What is the point of naming questions A, B, C when they don't represent the difficulty level? Just do it the CodeChef way if you can't order properly, it wastes a lot of time.

That being said, definitely a great education contest.

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

How to solve Problem B ?

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

So, now my believe that they sort problems in terms of difficulty is broken. Thanks!

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

In fact, question E is the same as the question 448C You can use the code from question 448C to pass E.

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

    Can confirm, just submitted.

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

    I had solved 448C while practicing about a year ago. Couldn't solve it today. Now this is sure that I won't forget this problem/solution ever :)

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

      me too……

      but I Accepted 448C in 8/23

      lol

      I'm fool

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

        i accepted 448C 10 months ago,

        but i spent too much time on B that I didnt even look at E!!!

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

Why is this code wrong for C?

Please help (if possible provide correct logic of C)

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int x;
        string s, w;
        cin>>s;
        cin>>x;
        for(int i=0; i<s.size(); i++){
            if(i+x<s.size() || i-x>=0){
                if(s[i+x]=='1' || s[i-x]=='1') w[i]='1';
                if(s[i+x]=='0' && s[i-x]=='0') w[i]='0';
            }
        }
        if(w.size()==s.size()) cout<<w<<"\n";
        else cout<<-1<<"\n";
    }
    return 0;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i guess that you access string w out of bound?

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

    I think you should check conditions i+x<s.size() and i-x>=0 separately.

    In your code, when i=0, i-x<0 but i+x<s.size() -> you access character at a negative (i-x) position in string s.

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

i submitted my solution when very few seconds were remaining (usually when contest is over then a small rectangle appears saying contest is over but this did not happened in my case when i clicked on submit) . But my solution did not got submitted. What could be possible reasons ? can awoo or MikeMirzayanov look into it.

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

swap(B,C);

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

When can we expect the editorials? Eagerly waiting for the explanation for B.

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

    Iterate on $$$i$$$ — the number of swords you take, then you can compute the number of axes you take using a simple formula in $$$O(1)$$$: $$$\min(cnt_w, \frac{p - is}{w})$$$. Then compute the number of weapons your buddy should take: if the swords are lighter than the axes, then the buddy should take the maximum possible amount of swords he can, and then — the maximum number of axes. Otherwise, it's vice versa.

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

      I tried first taking as many swords as possible for F and then removing each sword and getting axes in place(only if I can) and then decreased the count of respective weapons and then performed same thing for P and then combined the results.

      I saw many of test cases for this solution correct but many were close but not exact? What's wrong in this approach?

      PS:- I understood your approach. Thank you.

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

        Hey man! If you find an answer to your question. Please let me know. I did the same. Don't know why it's wrong to do that.

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

The question E was an exact copy of /problem/448/C. why?

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

Why is it giving MLE on E?

I created a 3-d vector ( n * n * 2 ) of ints

Technically, 10^8 vector of ints gives ~ 4*10^8 ~ 400 MB,

So here it is 4*(5000)*(5000)*(2) = 2*10^8, which is roughly 200 MB, and constraint is 256 MB!

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

    Are you using long integers?

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

      no I changed it to integers, after 1st attempt, still MLE

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

        Still 200 is pretty close 256. And I see you are using vectors. Vectors sometimes take a bit extra space than you assign them.

        Maybe array won't give MLE

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

          thanks, it worked with the array. still curious to know the factors affecting the MLE part. bcoz I had approximated 1MB to 10^6 bytes, but it is 1024*1024, which provides even more space than 2*10^8 bytes.

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

            Read up on how vectors work. A vector is alloted extra space than the size you declare it to. This is to support the pushback operations in constant time. When the actual capacity is reached, the size alloted is doubled I think.

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

            vector makes more cells than it actually has, because it can expand

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

Poor me couldn't solve C. Could anyone explain it a bit?

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

    First initialize s (length n) with all 1's.

    Traverse on string w. For all 0's in w set s[i-x] = 0 if i-x>=0 and s[i+x] = 0 if i+x<n, where i is the index of a zero.

    Check if the final string s is correct. If it is print it else print -1. You have to check if it is correct because you changed some cells' values from 1 to 0 in s. So you have to make sure that all the 1's in w are valid.

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

Contest is very interesting.... Thanks...

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

Damn, I didn't read problem E correctly (or I forgot the details). I thought we had individual numbers given and not the numbers of each specific number....

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

Why don't you guys announce officially that problems won't be sorted according to increasing difficulty. And I think gone are the days when the problemset used to consist of problems with varied difficulties. It's really frustrating taking part in such contests.

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

why will binary search not work in problem B.

I was trying like this if you can take 'mid' number of total swords then you can take any number of swords less than 'mid'

to check mid we will take that kind of sword which is cheaper first and then rest of the other type of sword.

Submission : https://codeforces.net/contest/1400/submission/90957831

please help

upd: i got my silly mistake

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

Swap B and C :)

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

can somebody please help what is wrong in my code in div2C ,i just changed some if's and it got accepted thanks in advance WA CODE Accepted Code

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

Alternate Solution to B:

Suppose item of type 1 costs lower than type 2 ( if both are equal choose arbitrarily). We first determine if there is an optimal solution which does not use all the type-1 objects. Consider any optimal solution S*. If S* has some type-2 objects, replace them by type-1 objects until there are (a) either no type-1 objects left, in which case we conclude that there is an optimal solution which uses all type-1 objects, or (b) We obtain an optimal solution consisting only of type-1 objects, which, further, does not use all type-1 objects. But (b) happens iff floor(p/weight_{type 1}) + floor(w/{weight _type 1}) < cnt_type 1.

If (b) happens, then the optimal value is simply floor(p/weight_{type 1}) + floor(w/{weight _type 1}).

Otherwise, all the type-1 objects are part of an optimal solution. Now we iterate over the number of type-1 objects that one of the persons takes as part of the optimal solution, we can then figure out the remaining capacities of both persons and update the answer accordingly.

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

Someone please explain how to solve problem D.

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

    deleted

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

    Let's take all possible values of j and l, so we need to find possible i and k. How do we do that ?

    Spoiler

    But it's a tle. So how to do it effectively.

    Spoiler

    I think the code should be readable now. 90963741

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

      Nice explanation :)

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

      Was D a standard approach? If it was, what is this thing called?

      Ps: I know it is an optimization to the brute force and hence can be called DP, but I wanted to know a more specific term than DP related to this problem (if any)?

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

        Well I am not sure for the standard term, I can relate it to "contribution techniques". A recent problem which uses same kind of technique can be found in Codechef August Long Challenge,( Subsequence frequency counting ).

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

anyone please help what's wrong in my code in problem C( giving wa on test#2)

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

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

    One of the bugs is,you did not consider that when i-x and i + x are both out of bounds, s[i] must be zero. But I corrected this point and still got the wrong answer, and you have to find the remaining bugs yourself. It is recommended that you can print out the test data to see what is wrong.

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

For problem C, will checking if the character is 1 instead of checking for 0 and transforming be wrong ? Hard to explain but here's the code WA Solution

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

    u should check the 0 first since its obvious, if you check the 1 first, its hard to handle as there can be 2 positions for 1

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

      Bro it can be checked.I couldn't solve it during the contest,but after the contest I upsolved it.

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

In question c, I did not consider that when i-x and i + x are both out of bounds, s[i] must be zero. It is a sad story. I think there should be many people like me.

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

I have an nlogn Solution to problem E(nlogn preprocessing and O(n) recursion) ..

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

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

can some one provide small counter case in my problem c submission

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

    Accepted

    I don't know what exactly the mistake was but it was something with reinitializing values.

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

      I am not initializing anything if you notice . Just see these two codes , the only difference is that i am declaring string outside the loop and in the other inside. wrong answer

      accepted

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

        problem is with the way you use resize() function. temp.resize(n+1,'1') will not change the value of whole string to string of '1's. Ex. if temp="001" then it will become "00111" after temp.resize(5,'1').

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

For problem F, it says in the notes for the first example that

The resulting string "1162317" contains no 8-prime substrings.

But here "62" and "17" are also 8-prime substrings, right?

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

    In the 2nd condition with the $$$[l_2, r_2]$$$, $$$x$$$ can't be divisible by $$$f(l_2, r_2)$$$. For those substrings, 8 is divisible by 2 and by 1.

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

Can we solve D if the array were circular? For example, take n points around a cirlce. Each point i has a value $$$a_i$$$. Join points which have the same value by a straight string and then ask for the number of times two strings intersect.

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

    Wow. Another perspective to look at the problem.

    This perspective would be helpful in creating another problem with the same solution.

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

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it 
    if(n==1)
return 1;

    This is not quite correct. If array has length 1, but its only element is 0, then the answer is 0. After reading your code I think it's impossible for your code to pass an array with 0 to this function recursively, but you can be given such array on the input.

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

Is n^2logn allowed in D , many submissions are passing Extreme cases with 1990 ms.

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

URGENT If i submit a solution from 2 different accounts will both of them will get skipped?awoo

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

problem E felt much easier than problem D... Could it be because problem D is a well known problem? Because I looked at some solutions and they seemed very tricky. I mean, I reduced it to the number of "pure" intersecting sub-segments so maybe that's well known? I don't know...

If it is a well known problem, I can say that even though they consistently screw my ratings, these EDU rounds are so important to get familiar with non-ad-hoc problems and their solutions.

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

Even though C has a very simple understandable solution. Did anyone thought of using Two Sat to solve the problem during contest ? It is a very direct application of Two Sat.

Spoiler

You can check my submission here 91000892

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

Can someone hack my solution for D, the time complexity of my solution is $$$O(n^3)$$$.

Link: https://codeforces.net/contest/1400/submission/90999462

Edit: It's $$$O(n^3)$$$

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

    Your solution actually can take up to $$$O(n^3)$$$ on a test like

    1
3000
1 2 3 ... 1000 1001 1001 ... 1001 (total 2000 occurrences of 1001)

    Due to how unordered_map works, occurrences of 2001 will be stored in g[0],

    so

    int c1 = fre[y][g[x][j]] - fre[y][g[x][i]];
int c2 = fre[y][n] - fre[y][g[x][j]];
int c3 = fre[y][g[x][i]];
ans += (c1 * (c2+c3));

    this piece of code will be executed for all $$$y$$$ in $$$[1,1000]$$$, for all $$$0\leq i<j<2000$$$, which is total of 1999000000 times.

    Fortunately for you your solution has a very low constant factor and runs on this test in 1699ms so I don't think it is possible to hack it.

    At first I thought compiler somehow realised this loop is somewhat redundant and optimised it into just adding the same thing x times, but no, when I run it on similar test with $$$n = 6000$$$ it did take approximately $$$8$$$ times longer

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

      I most-probably hacked 30 submissions using maps , unordered maps and custom hashes. and I hope if my test case is added then his solution may time out. PS:- My test can't stop compiler optimisations thus I don't think the submission will timeout.

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

        No it won't. The part using hashmap does $$$O(n)$$$ operations on it, so even if you defeat it, which is impossible given that those operations operate on keys from [1, n], they'll take $$$O(n^2)$$$ which is still very fast with $$$n=3000$$$.

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

          Ya I came to know it after seeing that pragma , in his submission. And I think that pragma should not be allowed in real to use. As it is just allowing some brute approaches to pass. Anyways its my opinion.

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

I worked out E by greedily picking min_element and recursively solving the subproblems on either side of it. Can someone provide the proof of optimality for the approach?

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

    The recurrence comes down to $$$T(n) = T(n-i) + T(i) + O(n)$$$ where $$$i$$$ is the index of the min element. Worst case is $$$T(n) = T(n-1) + O(n) = O(n^2)$$$.

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

    You want to take the longest "horizontal" interval because if you take two overlapping intervals, you can always replace them with their union and intersection (for example if a = {1,2,2,1}, you can take the intervals [0,2] and [1,3], but you can replace those with [0,3] and [1,2]).

    So, you keep taking the longest one as many times as you can, which happens to be min_element times.

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

    What you guys said is right in itself, but it doesn't justify optimality, I think.

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

      The first observation is that the order of the operations doesn't matter. Consider some element $$$i$$$ frequency $$$a_i$$$. All the operations acting on $$$i$$$ need to sum up to $$$a_i$$$ (op 1 has the effect of $$$+1$$$, op 2 has the effect of $$$+x$$$). Since addition is commutative, the order doesn't matter.

      The second observation is that it's always better to do a single op 2 on any $$$i$$$. Two op 2s $$$(i, x_1)$$$ and $$$(i, x_2)$$$ can be replaced with a single $$$(i, x_1+x_2)$$$.

      The third observation is that the intervals for any two op 1s can be replaced by their union and intersection (as described by Svlad_Cjelli above). This means that if you have some set of intervals that overlap to span a range $$$[l, r]$$$, then you can replace the intervals such that you have an op 1 that spans the whole range.

      Now for the greedy strategy. By the first two observations, we can end the algorithm by perform $$$r-l+1$$$ op 2s on the remaining elements. Otherwise, we need to perform some sort of op 1. Using the third observation, we can greedily pick the largest range possible.

      Where does the min element come in? If you use the greedy strategy above, then doing $$$< a_{min}$$$ op 1s followed by the $$$r-l+1$$$ op 2s is never better than doing $$$r-l+1$$$ op 2s from the start. However, once we reach $$$a_{min}$$$ op 1s, we cannot do anymore op 1s over the full $$$[l, r]$$$. Hence, it breaks down into the left and right subproblems.

      Therefore, the final greedy algorithm $$$solve(l, r)$$$ is the minimum of:

      1. $$$r-l+1$$$
      2. $$$a_k + solve(l, k-1) + solve(k+1, r)$$$ where $$$a_k = min(a[l...r])$$$
      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C is confusing.

For a given $$$i$$$, such that $$$i-x > 0$$$ and $$$i+x <=N$$$, should $$$s[i-x]$$$ be equal to $$$s[i+x]$$$? From the problem statement it seems so. Otherwise $$$w[i]$$$ is not defined, since it should be equal to both $$$s[i-x]$$$ and $$$s[i+x]$$$.

But from looking at the solutions, it doesn't seem to be the right interpretation. What is the right interpretation of the problem statement?

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

    If w[i]==1 then s[i-x] and s[i+x] must be equal (to 1). But if w[i]==0, then one of them could be 0 and the other one could be 1.

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

I think this round is "hap"py and not "happy".:(

I can't solve E(T_T),I'm so weak!

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

.

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

    It seems that D is not a original question either.Will this contest unrated?

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

Please explain why problem E is exactly the same question as 448C - Painting Fence. And will this round be unrated because of this mistake?

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

E was used in Tencent(腾讯) coding test of campus recruiting a few days ago.

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

In E.Clear the Multiset can anyone explain me how we get the output as 3 instead of 2.Thank You! input 5 1 0 1 0 1 output 3

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

    We need to clear $$$a_1,a_3,a_5$$$ (They are all equals to $$$1$$$) separately, so we need $$$3$$$ operations. How did you get the answer $$$2$$$?

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

deleted :(

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

    i am your friend, and i want to thank you（

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

Why does a iterative solution not work for E? I try to find the minimum value in every contiguous segment with value >0, and reduce every element in the segment by the min. value, I keep doing this till all elements are not 0

91013729

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

    Reducing by the min takes min operations.

    5
3 3 3 3 3

    Your code prints 1, but the answer is 3.

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

      oh, I completely forgot that. Thanks a lot

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

Hi, please somebody help me debug this code for problem B. I have been trying to find the bug but no success. I am first iterating over all number of swords we can take ourselves, and then giving the remaining swords to follower. Axes fill the remaining space for both.

MY CODE

Thanks in advance!

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

    loop on l from 0 to p/wgts should be upto min(p/wgts, cnts) because otherwise cnts-l can be negative.

    Testcase:

    1
16 12
2 4
4 5

    expected answer : 5 your output : 6

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

Why doesn't the system test start?

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

Is it rated?

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

Why the rating for this round is not given till now?

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

C was easier than B.

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

What does +,+1,+2,+3 mean in the standings page? Can anyone explain?

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

    Number of penalties (incorrect submissions) that person received for that question.

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

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

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

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

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

Can anyone send me more problems like RPG PROTAGONIST i would like to practice more of them.

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

    If you means problem with both brute force and greedy,1389D is pretty good.

    → Reply