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

Hello Codeforces!

On Jan/18/2024 17:35 (Moscow time) Educational Codeforces Round 161 (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 Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Big thanks to the testers shnirelman and Minder for their valuable advice and suggestions!

Good luck to all the participants!

UPD: Editorial is out

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

Comments Comments (204)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

Hopefully I reached Expert :)

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

I wish everyone a good contest!

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

My 3rd rated contest. Wonder if I could reach True Rating 1700(displayed 1400)

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

Good Luck and Have Fun everyone!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -46 Vote: I do not like it

Hope this round aint Mathforces af. Usually, Edu rounds = Mathforces

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

What's the difference between an educational round and normal div 2 round?

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

Such a short and clear announcement I hope problems statements be like this too!!!

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

Hopefully I can get Pupil(not Newbie) :/

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

BledDest Round

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

Hope I can get Expert badge.

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

Hopefully I reached Specialist :)

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

How many problems I need to solve to become a Pupil in this contest?

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

Educational round is overrated

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

Educational round means you have to study gcd well :)

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

As I screwed up in the last div3, I hope to solve 3-4 problems in this round :|

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

bad explanation of first question

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

[deleted]

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

Didn't realize E was easier ,should've tried that first.

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

B was a good problem for such a simple concept but i made 2 wrong submissions.

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

    Yes! Problem statements were clear and precise. But I must be blind... :(

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

Was C that easy ? is it based on some standard algorithm/ some standard problem ? i was thinking in direction of Floyd Warshall algorithm. but could not come up with solution. I'm seeing around 7000 successful submissions. or it was based on something else like Dijkstra/DFS/BFS ??

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

    i pre-calculate cost of go forward and backward

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

    This problem maybe doesn't require the shortest path algorithm

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

    C was a modified version of prefix sums

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

    It can be shown that in order to go from point x to a point y, going back is never a good choice.

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

Damn, the first question reduced my life by a few years. :')

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

I have skill issue

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

I think E was way easier than it ought to be. Good contest nevertheless.

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

Wasted too much time in problem A :/

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

can someone please explain problem A? Thanks in advance.

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

    this took me 90 minuts to figure out

    loop from 1 to n if(a[i]==b[i]&&c[i]!=a[i]) then yes and break if(c[i]!=a[i] && c[i]!=b[i]) yes and break

    print no if loop finished without any yes

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

awoo Loved the D and people think LinkedList is overrated.

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

I got drown in caseworking C. Any ideas on avoiding, like, a dozen of caseworks?

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

    you can create a Generic function that decrease the number of those caseworking.

    242254308

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

      Wow! That was neat!

      I tried to partition the array into several groups, and each group contains two "center" cities where everyone leads to, and then hop between the groups before caseworking the best answer out when they are in the same group.

      That was painful. Those with a daring soul may see it here --> 242305848

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

my first E yaaaaaaaaaaay

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

Anyone feel like the wording on A was weird?

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

    Took me 20 minutes and out of the contest to understand the concept of "uppercase is lowercase this time".

    I do not understand how problemsetters cannot see that such a wording is bad.

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

what is the approach for B?

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

    Note that the sides of the triangles are powers of two. So, at least two of the sides have to be equal. This observation makes it a lot easier.

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

      how to count the valid triplets?

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

        Use combinatorics, create a map to keep track of frequency, for each frequency in map, you can choose 3 sides of same length NC3 (N = frequency of element and you can choose 2 same sides and 1 from smaller sides, NC2 * CF (cumulative frequency before the current element). Intuition is 2^k + 2^(k + 1) is less than 2^(k + 2) using GP formula you can prove, therefore 3 sides cannot be unique, isosceles and equilateral triangles can be formed

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

E was basically APIO 2022 P3 with nerfed limits?

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

How to solve F?

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

Good contest

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

I submitted B 14 times ;-;

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

Did the authors intend to cut off solutions to D that uses two std::sets? I got TLE on my first attempt before finally switching to segment trees.

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

    No, I used two std::sets as well and it passed in 700ms

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

      same, my passed in 389ms

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

      Same. It was meant for Set. At any point if you remove X elements, you will iterate for 2*X elements and out of which if you remove Y elements, next time you will iterate for 2Y elements. So overall 3*N operations will be carried out.

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

      I see. I guess it was my implementation that was inefficient, then.

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

    How did you solve it by segment trees? Like what was each Node storing, can you please share.

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

      The segment tree was only used to get the global minimum of the remaining health points of each monster (i.e. $$$d_i$$$ minus the total attacks dealt to it). Each node stored the minimum of that value among all indices in its range, as well as the index that caused that minimum value. This allows us to simulate each round and find out which monster died during the round.

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

    I used linked list — 265 ms.

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

    I used 2 vectors and a static linked list. It's supposed to be O(n)...

    → Reply
»
3 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

C was intuitively not too hard.. just too painful to implement.

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

How to guess the solution of problem E?

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

    Notice that this problem appeared in APIO and copy paste

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

    10^18 says it should be done in O(logn).

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

      I'm pretty sure it can be done in O(n), using the fact that increasing array of length n contains exactly 2^n increasing subsequences. Oh, I meant n being the length of resulting array.

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

    I think considering case of $$$1, 2, 3, 4, 5, 6 ...$$$ is very natural.

    Then understanding $$$1, 2, 3, ... , n$$$ gives $$$2^n$$$, should be enough to be able to construct solution

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

      I tried this idea. I noticed, that if I have blocks, which look like: $$$|10 \; 11 \; 12|7 \; 8 \; 9|3 \; 4 \; 5 \; 6|1 \; 2|$$$, and their lengths are $$$a_1, a_2, \dots, a_k$$$, then number of subsequences is $$$(2^{a_1} - 1) + \dots + (2^{a_k} - 1) + 1$$$. Then I can factorize $$$x$$$ in sum of degrees of $$$2$$$. For example, $$$37 = 2^0 + 2^2 + 2^5 = (2^5 - 1) + (2^2 - 1) + 3$$$, so I use $$$a = {5, 2}$$$ and append two decreasing numbers at the end.

      This is $$$O(log^2{X})$$$ solution, which is incorrect.

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

        Nice idea. I think after that you should have realized, that building solution using independent blocks would result in very lengthy sequence. And after that realization should have abandoned this approach and returned one step back to $$$1, 2, 3, 4, ...$$$

        If we add $$$3$$$ to the end of $$$1, 2, 3, 4$$$ we would get additionally as much sequences as there were sequences in $$$1, 2, 3$$$

        So in general adding $$$m$$$ to the $$$1, 2, 3, ..., n$$$ would increase number of sequences by $$$2^m$$$. That is I believe — final idea of solution.

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

          I figured this out but was unable to implement within time :(

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

I didn't like the round (yes, I am going back to expert again)

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

is it div3?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

Horrible statement for D!

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

Am I the only one who was struggling with problem B ;-;

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

    Not sure why but I found A relatively harder than B. B was pretty much straightforward as triangle is only possible if sum of two sides is greater than third. Note that 2^0 + 2^1 + .... + 2^n < 2 ^ (n + 1). So you always have to take two same numbers. Reminder can be any number which is less or equal to this.

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

E looks like easyer than D because you can find the solution on the Internet :)

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

OMG! Stuck on B for more than 30 minutes, not until the contest is finished did I notice that the length is $$$2^{a_i}$$$ not $$$a_i$$$ .

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

Problem E coincides with APIO2022 Problem C completely.

In APIO2022 Problem C — Permutation, It requires an array of length less than 90. In today's contest, it just has a limit that the array of length at most 200. Besides, In APIO, it also requires that elements should be distinct. It has been weakened.

I think that E<D.

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

Can someone tell me why my code for D get runtime error? Thank you in advance

My Code

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

Wasted 10 minutes in Problem B before I noticed the power of 2.

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

Me thinking that D was about decreasing health instead of just checking if damage is enough. :[

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

I submitted B 5 times and got WA.Because I thinked pow(2,0)=0.:)

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

Can some high rated coder tell me how to become an expert asap?

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

    You just need to work on yourself. Try solving previous contests in virtual mode or just try solving problems in archive. There you can choose the types of tasks in which you are bad. If you can't solve something, don't look at the solution right away, try to solve by yourself. But if you really can't, check solution and always write your code by yourself. Also there are some useful courses in edu, you can solve them too

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

Div 2. where E solved by more than 1800 people,

bye-bye my rating 😂

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

it's okay ill try again next round. btw can i participate div1 round?

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

    yeah but div1 is harder. Div2 and div1 happens at the same time you can participate in div2 if that is better for your level.

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

I don't understand why my hack didn't work on problem B Test: 1 4 0 0 0 3 This is withing the constraints of the input given but it shows unsuccessful hacking attempt because expected answer is 1. Shouldn't expected answer be 0 since no triangles can be formed obviously.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -21 Vote: I do not like it

Decent contest. A and B is okay. C is somewhat fun but probably should only be limited to a<b (failed rhe caseworking like an idiot, but even then turning from the left-right variation to the other way around doesn't require much effort) Who tf allowed E to exist? Even I, a literal green, knows that it's APIO22's perm at first glance. Stealing problems from chinese OJs or some random unpopular place, while a scummy thing to do, would still only allow a small set of participant to get a major advantage. But stealing from fricking APIO??? What kind of coordinator even allowed that to exist lmao. What's next? Stealing literal IOI problems? Come on man what the hell

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

    ......and the fact that anyone who takes CP seriously should know about the existence of oj.uz, which...allows for free copy pasting, is, uhhhh, funny. Stealing from a judge that allows you to see submissions post-AC is already bad, stealing from somewhere that you could ctrl+c ctrl+v for free..... Should've copied instead of debugging C smh

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

    then why you didn't solve E?

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

Anyone plz tell me how can you solved the Problem C or D, I was solved only A,B. Thankyou

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

    Problem C was only the cost of going to X -> X+1 -> X+2 -> ... -> Y if $$$X \lt Y$$$, or X -> X-1 -> X-2 -> ... -> Y if $$$X \gt Y$$$. The reason is that if you go back to a closest city you have to retreat anyway, so we only need to calculate the cost of going to the left, or to the right. To do this efficiently we use prefix and suffix sums.

    Problem D for me was only implementation, I simulated the steps, but instead of iterating all the monster and removing them for $$$N$$$ steps I only save the monsters that are affected by removing the dead monsters. I think this is $$$O(n \log n)$$$?, because in each iteration the monsters affected are reduced. I really don't know and possibly get hacked. For removing monsters I use Linked List.

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

      D is $$$O(n)$$$ if implemented properly because each monster is removed once = n in total, and each removed monster affects two in the next round = 2n. +n rounds = still $$$O(n)$$$.

      Something like this. My initial implementation was $$$O(N log N)$$$ improved by reading other solutions.

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

242304887

what is wrong with my solution!! this problem suck!!

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

Going back to newbie :(

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

Could someone explain why and tell me the number of increasing subsequences?

UPD: I found out why, thanks

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

I actually liked E, It took me an hour to come up with a pattern, the pattern was related to bitmask of X. It could have been better if length of array was atmost 120.

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

Can anyone tell me why my submission on D gets WA?

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

    The problem is the first occurrence of this line:

    if (i==0||been[i]) continue;

    If the monster on the left is missing/dead, you still need to check the monster on the right. You should combine that if-statement with the next one, instead of skipping the rest of the loop body.

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

What does this mean "The penalty for each incorrect submission until the submission with a full solution is 10 minutes"

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

    When you commit the correct solution, you get points like you would have commited it 10 minutes * wrong times later.

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

    assume that you sent problem B after 10min and get wrong answer on test bigger than 1

    this 10min will be added to your penalty

    your handle A: +(0:03) B: -1(0:10)

    your penalty will be 3+10

    sorry for being complicated

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

    even if you send 100 wrong submissions, it doesnt count to your penalty until you submit a correct one. Each wrong submission costs 10 penalty points. A submission is not wrong if it is accepted or compilation error or your code fails in the very first test.

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

    On the scoreboard, people are ranked by number of problems solved first (higher is better), and by time second (lower is better).

    The time is the submission time of all the solutions added together. For example, if you solve problem A, B and C exactly 10, 20 and 30 minutes after the start of the contest, your total time is 60 minutes. For every incorrect submission, 10 additional minutes are added to your time.

    However, and I think this is where the confusion comes from, the penalty time for incorrect submissions only applies to problems that you have solved. If you do not solve the problem, that problem adds 0 minutes to your time, no matter how many failed attempts you made.

    This prevents situations like where Contestant 1 solves problem A in 15 minutes. Contestant 2 solves problem A in 10 minutes, and then makes a wrong attempt to solve problem B. Giving contestant 2 a 10 minute penalty would make him rank lower than 1, which seems unfair, since both participants solved the same set of problems (only A) and participant 2 was strictly faster.

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

Can Anyone please explain the logic behind Problem D ...

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

    Consider the monsters before first day. Each monster gets some damage, foreach monster you can tell how many days it lives.

    Output answers until the first day monsters die, then remove all monsters that die that day. Repeat.

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

    If you use the linked list approach, then the intuition is this: you can easily compute whether a monster dies in the current round, by adding the attack scores of its neighbors and comparing it to the monster's defense score. If the monster survives this round, it will also survive subsequent rounds, as long as its neighbors don't change.

    So the only monsters that you need to check on round X are the neighbors of the monsters that died on round (X — 1). (Round 1 is a special case: here you have to check all monsters.) If you store the monsters in a double-linked list, then you can efficiently remove dead monsters and calculate a list of their neighbors, which you use in the next round, etc.

    This way, you do at most O(N) work across all N rounds.

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

Anyone knows why my submission for problem D gets wrong answer verdict? I am trying to maintain the previous and next monsters in prv[i] and nxt[i], code here: https://codeforces.me/contest/1922/submission/242332530

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

How to solve F? Does it use some specific optimisation?

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

    Naive O(N^3K) dp was just fine.

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

      Can't you just bruteforce every possible x in $$$O(N x)$$$?

      Oh, I see now. That different x's are optimal, in 3rd test case replace first all 2s with 3 and then entire array to 2.

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

Can someone explain B?

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

    we have to pick three powers a,b,c lets assume a<=b<=c. if a=b means 2^a+2^b=2^(a+1) => 100 + 100 ==> 1000 (2^3 addition in binary) the sum has to be less than longest side to have a valid triangle. which means a+1>c but c>=a so we have to take c such that it is equal to a

    if a!=b a=0100 b=1000 sum=1100 this sum is less than 10000 i.e we need c to be b<=c<b+1

    so we need to take all the pairs in which either 3 or 2 numbers are equal

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

Can anyone explain how to approach problem D

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

    You can simulate it pretty much. Think of it like this, if a monster is about to be defeated, then after it's defeated, its adjacent monsters will begin attacking each other, and you don't have to think about it again. You then check if the adjacent monsters will be defeated in the next round. Following this you're able to simulate.

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

can anyone tell me where i'm wrong in my solution for problem D? thank you.

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

Can anyone help me point out what is wrong in my 242347538 for problem D?

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

still trying to solve A

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

E was surely much easier than D.

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

This submission seems suspicious, the participant has included code from some other problem to avoid plag checks. His exact same code was available in a youtube video during the contest. MikeMirzayanov please look into this.

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

Problem E, Possible Issue with Judge,

Verdict: Wrong answer on test 2, test case 29

Test case 29,

30

My output for test case 29,

7

1 100000003 2 100000002 3 100000001 4

Judge: Wrong answer The number of increasing subsequences in the printed array doesn't equal to x (test case 29)

I have myself counted 30 increasing subsequences in my output. Please look into this.

242373040

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

    Ok this is really weird actually, I ran your code locally and on an online compiler for X = 30 and got the output of:

    8 100000004 1 100000003 2 100000002 3 100000001 4

    But when I ran your code on Custom Invocation on CF, I got the output that you described. Really strange.

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

      Actually follow up on this, it prints out: 8 100000004 1 100000003 2 100000002 3 100000001 4

      When compiled with G++17 but it outputs:

      7 1 100000003 2 100000002 3 100000001 4

      When compiled with G++20

      This might be your problem...

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

    The judge is correct. However, your code seems to be printing

    8
100000004 1 100000003 2 100000002 3 100000001 4

    instead of the output you mentioned for the 30 case when I run it on C++17. Here the answer is clearly > 30. But the output you mentioned in your comment will have 30 favourable subsequences.

    Curiously, I got the output you mentioned when I ran it in C++20, so you may have some kind of compiler specific error in your code.

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

    You access outside the limits of your pos array (I think you meant to put j < pos.size() in the if?).

    → Reply
»
3 years ago, hide # |
← Rev. 4  
Vote: I like it +7 Vote: I do not like it
A hack for C
How it works
→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

I think A problem is bad,because its topic is vague

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

I feel like this contest has tested the contestant's ability to judge time complexity 感觉这场就考验了选手对时间复杂度的判断能力

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

Wow, 3 years since I last did competitive programming and I still choke under pressure of a CF contest XD

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

Problem C.

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

Why am I getting TLEs in problem D? Please help.

Submission using set only, TLE in TC 15

Submission using idea of doubly linked list and set to handle the remaining elements, TLE in TC 7

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

When does the system testing start?

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

Video solutions for A-C, D-E

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

Really wondering if this solution for F is hackable (in both idea and execution time)? I know it had to be DP but the presented idea seems pretty messy and duct-taped, would actually be open to some revelations, and the complexity seems to be a pretty high-constant-factor $$$O \left( n^3 x \right)$$$.

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

Finally Expert !!!

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

Strange, I got TLE for my submission for B despite it being O(nlogn) in worst case.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 
void solve() {
    ll n;
    cin>>n;
    vector<ll> arr(n+1);
    for(ll i=1;i<=n;i++){
        cin>>arr[i];
    }
    vector<ll> close(n+1);
    close[1]=2;
    close[n]=n-1;
    for(ll i=2; i<n; i++){
        if(abs(arr[i]-arr[i-1])<abs(arr[i]-arr[i+1])){
            close[i]=i-1;
        }
        else{
            close[i]=i+1;
        }
    }

    vector<ll> dist;
    for(ll i=1;i<n;i++){
        if(close[i]==i+1){
            dist.pb(1);
        }
        else{
            dist.pb(abs(arr[i]-arr[i+1]));
        }
    }

    vector<ll> backDist;
    for(ll i=n;i>1;i--){
        if(close[i]==i-1){
            backDist.pb(1);
        }
        else{
            backDist.pb(abs(arr[i]-arr[i-1]));
        }
    }

    reverse(backDist.begin(),backDist.end());

    vector<ll> prefixSum(dist.size()+1);
    vector<ll> suffixSum(dist.size()+1);

    prefixSum[0]=0;
    prefixSum[1]=dist[0];

    suffixSum[dist.size()]=0;
    suffixSum[dist.size()-1]=backDist[dist.size()-1];




    for(ll i=2;i<=dist.size();i++){
        prefixSum[i]=prefixSum[i-1]+dist[i-1];
    }

    for(ll i=dist.size()-2;i>=0;i--){
        suffixSum[i]=suffixSum[i+1]+backDist[i];
    }

    ll q;
    cin>>q;
    vector<ll> res;
    while(q--){
        ll x,y;
        cin>>x>>y;
        if(x<y){
            ll ans = prefixSum[y-1]-prefixSum[x-1];
            res.pb(ans);
        }
        else{
            ll ans = suffixSum[y-1]-suffixSum[x-1];
            res.pb(ans);
        }
    }
    for(ll i=0;i<res.size();i++){
        cout<<res[i]<<endl;
    }

}

Can anyone help me find why this code is giving runtime error in testcase-2

Problem-C

PLease help !!!

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

Easy video explanantion for problem E

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

downvote, if you liked editorial

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

Why do you only takes 3 problems to the problem list?

→ Reply