By pikmike, history, 3 months 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 Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 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 xwd456 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 Sealionheart 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

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

0

»
3 months ago, # |
  Vote: I like it -64 Vote: I do not like it

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

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

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

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

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

best of luck

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

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

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

      Rudra24 can you explain/elaborate this please?

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

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

    smh people changing comment content to avoid getting more downvotes

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

Finally...

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

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

I'm looking forward to this competition. I wish I could increase rating.

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

Hoping to remain expert this time :)

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

Hope that queue does not occurs.

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

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

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

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

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

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

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

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

Hoping for a positive delta :)

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

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

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

    Persistence my man! Full year of persistence paid off! Congrats. :)

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

Kudos to Team vovuh BledDest pikmike for organising awesome contests.

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

wish me good luck

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

This kind of ordering?? You just destroyed me.

»
3 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Unbalanced problemset?

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

Problem B makes me rethink my whole life.

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

    B sucks

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

    Luckly I jumped straight to C and got it early. Still didn't solve B tho...

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

    I thought it is a dp problem, but dp always act as a mirage. Wherever i am unable to think of logic, i always thought the problem to be of dp(XD), but after contest i got to know about greedy approach.

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

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

    Yes, E is exact copy of:

    448 Problem C

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

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

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

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

    What exactly is misleading in B and C statement?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      Many are confused in C for -1 condition !

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

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

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

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

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

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

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

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

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

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

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

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

                10 years? Your account history says otherwise..

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

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

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

                I bet I'm better than your 10 years

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    I thought Russians are the dumbest but it seems like Chinese like you are worse. Ur more dumb than your handle bro

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

WrongProblemOrderForces !!

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

How to solve E?

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

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

      that's why UpSolving is important... xD

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

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

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

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

goodbye ratings.

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

How to solve Problem D?

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

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

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

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

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

How to solve B?

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

      Tried with that but WA

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

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

          Ohh no. Another silly mistake

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

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

      I tried first taking as many swords as possible and then removing each sword and getting axes in place(only if I can) for both f and p and combine results of both. What's wrong in this approach?

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

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

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

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

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

B should be placed after C :(((

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

    After D

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

    Why? It is just a basic brute force.

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

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

        That doesn't increase a problem's difficulty.

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

Copy pasted E from here

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

    :(

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

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

      Practice...

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

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

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

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

»
3 months ago, # |
  Vote: I like it -30 Vote: I do not like it

Fucked-up-order-forces

»
3 months 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)

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

How to solve G?

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

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

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

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

Can someone just give a hint for B?

»
3 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Is Linear Diophantine Equation used for Question 2?

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

    No,It can be done without this theorem.

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

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

Wrong Answer on test 2

Story of this contest

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

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

    plz help

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

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

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

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

isn't E divide & conquer dp?

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

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

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

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

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

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

I found B very interesting..

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

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

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

Can someone give any hints for F?

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

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

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

        We will try to explain this technique in editorial

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

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

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

    check this test case: 11110 1

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

Solution for C: Initialize a string str of 1's of same size. In C just put 0 on both side of string str at x distance, if you get 0 at a position in input string. For -1 condition : Check if you can form input string from the string str according to given rules. If you can't form input string print -1.

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

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

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

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

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

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

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

      I did the same thing and got accepted 90966489

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

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

Problem D looked like a standard interview problem.

»
3 months ago, # |
  Vote: I like it -32 Vote: I do not like it

It was LOVEDAY contest for me

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

I overcomplicated B .Didnt look for cntB<=200000

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

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

How to solve Problem B ?

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

import random random.shuffle(problemset)

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

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

    Educational round is very unpredictive. Specially be extra cautious when they say round is for standard 5-6 students.

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

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

    Can confirm, just submitted.

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

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

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

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

    i guess that you access string w out of bound?

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

»
3 months 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 pikmike or MikeMirzayanov look into it.

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

swap(B,C);

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

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

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

      Got it. Thanks, man. I don't know what I was thinking when I first saw the problem. Feeling so stupid now.

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

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

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

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

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

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

    Are you using long integers?

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

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

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

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

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

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

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

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

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

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

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

Can someone tell me where do I go out of range I got so tilted during the contest.On problem C:90979571

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

    you should initialise your string s = ""; and in for loop s +='a'; even though your code is giving wrong ans but you will not get RE

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

      Wow thx a lot. Do you know why my code gives runtime error?

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

        I think it happens because the string is empty so you cannot use its indexes , as the space at that index is not created.

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

          A bit weird it passed on test case 1 without RE but thanks a lot for the help.

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

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

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

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

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

please help

upd: i got my silly mistake

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

Dear coders,I have a question.Suppose I submit wrong solution in this contest two times.Before two minutes ending the contest,if I submit correct solution,Is it counted accepted?And is it show in my contest list that I have solved this problem during contest time?

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

    Yep , if you solved the problem during contest.

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

Swap B and C :)

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

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

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

Someone please explain how to solve problem D.

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

    this is brute: for(int i=1;i<=n;++i) for(int k=i+1;k<=n;++k) if(a[i]==a[k]) for(int j=i+1;j<k;++j) for(int l=k+1;l<=n;++l) s+=(a[j]==a[l]); I'm going to use a two-dimensional prefix and optimize this to

    Unable to parse markup [type=CF_MATHJAX]

    $. for(int j=i+1;j<k;++j) for(int l=k+1;l<=n;++l) s+=(a[j]==a[l]); So the total complexity is going to be

    Unable to parse markup [type=CF_MATHJAX]

    $,Can be achieved by.

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

      code != explanation

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

      Your optimation is not clearly parsed. Can you mention it again?

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

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

      Nice explanation :)

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

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

        No its not dp. The optimization is done via Prefix sum arrays

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

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

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

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

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

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

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

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

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

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

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

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

      • »
        »
        »
        »
        3 months 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').

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

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

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

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

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

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

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

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

»
3 months 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?pikmike

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

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

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

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

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

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

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

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

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

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

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

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

    • »
      »
      »
      3 months 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])$$$
»
3 months 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?

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

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

Recently seeing this trend of placing a more complex problem (grammatically or otherwise) at B than the problem at C, and its not helping. Now on, will keep a watch if problem C is getting solved by more people than B, and then decide which to attempt first. ;O

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

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

E is not a original question Same as https://codeforces.com/problemset/problem/448/C

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

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

      I hope it's Unrated. It's a bad experience?

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

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

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

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

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

deleted :(

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

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

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

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

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

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

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

Why doesn't the system test start?

»
3 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Is it rated?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Spoiler
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think he asked coz the problem E was not original and few people passed it by just submitting code for the problem which was copied.

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

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

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

how to solve problem B using binary search?

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

    Same question. I was trying with binary search but got wa on tc 2. Can anyone tell me whats wrong in my code. I think my logic is 100% correct.

    Code Link: https://ideone.com/nbM3Uu

    Thanks in advance.

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

C was easier than B.

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