Educational Codeforces Round 161 [Rated for Div. 2]
By awoo, history, 10 months 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

»
10 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Hopefully I reached Expert :)

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish everyone a good contest!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to every Contestant!

→ Reply
»
10 months ago, # |
  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
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck and Have Fun everyone!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone

→ Reply
»
10 months ago, # |
  Vote: I like it -46 Vote: I do not like it

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

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it -32 Vote: I do not like it

    ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ

    → Reply
»
10 months ago, # |
  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
»
10 months ago, # |
  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
»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hopefully I can get Pupil(not Newbie) :/

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

BledDest Round

Spoiler
→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I can get Expert badge.

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

Hopefully I reached Specialist :)

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope for a positive delta.

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

    for pupil i think 2 is enough.

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

Educational round is overrated

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

Educational round means you have to study gcd well :)

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

l have nothing big,Pupil hop to be reached!

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

I hope to bring the pupil back again. Good luck for everyone!

→ Reply
»
10 months ago, # |
  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
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anxiety

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

bad explanation of first question

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

[deleted]

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +77 Vote: I do not like it

    and you are also using an alt, so shut up, do not complain of stuff you are personally doing

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

    What happened to "romanian diversion strat"?

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This First question made me skip contest man :(

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

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

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

    thats apio2022 perm

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

      Okay I start to implement it

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

        I got 98.8 pts and stuck on it :(

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

    D is a lot easier than E, E has just appeared before

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

      Yeah and I thought D<F<E... E needs constructive skills...

      → Reply
»
10 months ago, # |
← 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
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
10 months ago, # |
  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
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    i pre-calculate cost of go forward and backward

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

    This problem maybe doesn't require the shortest path algorithm

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

    C was a modified version of prefix sums

    → Reply
  • »
    »
    10 months ago, # ^ |
      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
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

    I mean yeah. Like I did too many wrong subs in A :(

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

I have skill issue

→ Reply
»
10 months ago, # |
  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
»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Wasted too much time in problem A :/

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain problem A? Thanks in advance.

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

      but the question said if there is one wrong letter then its a NO??

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

      Same lol!. Usually the first problem is too stressful than other problems

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

      only condition 2 is enough

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

      if a="ab", b="cd", c="ef" then what will be the template string t? suppose t= "EF", but it matches with string c also, right? Sorry if my question sounds dumb.

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

        In order to print "yes," it should not match the condition with the third string. So, "EF" matches with the first and second strings, because none of them is equal to "ef,",the third string should not match the condition. This is what is happening in our case because "EF" means that the string should be different from "ef," but it is "ef," so it doesn't match the required condition. Therefore, we print "yes."

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

    Count the number of positions with a!=b but( b==c or a==c) and also if all are equal then if the count is ==n it's no otherwise it's yes

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

awoo Loved the D and people think LinkedList is overrated.

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

    I actually used TreeSets/Ordered Set to track the previous and next poitners. Unfortunately was not able to solve. If someone could help me identify my mistake in the solve function (Java Code):

        static void solve(IO io) throws IOException {
        int[] params = io.readIntArray();
        int n = params[0];
        // int k = params[1];
        long[] attack = io.readLongArray();
        long[] defence = io.readLongArray();
        TreeSet<Integer> alive = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            alive.add(i);
        }
        HashSet<Integer> active = new HashSet<>();
        active.addAll(alive);
        for (int i = 0; i < n; i++) {
            HashSet<Integer> dead = new HashSet<>();
            HashMap<Integer, Long> damage = new HashMap<>();
            for (Integer j : active) {
                Integer prev = alive.lower(j);
                Integer next = alive.higher(j);
                if(prev == null && next == null)
                    continue;
                else if(prev == null){
                    damage.put(next, damage.getOrDefault(next, 0l) + attack[j]);
                } 
                else if(next == null){
                    damage.put(prev, damage.getOrDefault(prev, 0l) + attack[j]);
                }
                else{
                    if(j - prev == next - j){
                        damage.put(next, damage.getOrDefault(next, 0l) + attack[j]);
                        damage.put(prev, damage.getOrDefault(prev, 0l) + attack[j]);
                    }
                    else if(j - prev > next - j){
                        damage.put(next, damage.getOrDefault(next, 0l) + attack[j]);
                    }
                    else 
                        damage.put(prev, damage.getOrDefault(prev, 0l) + attack[j]);
                }
            }
            for (Integer j : damage.keySet()) {
                if(damage.get(j) > defence[j]){
                    dead.add(j);
                }
            }
            for(Integer j: dead){
                alive.remove(j);
            }
            active.clear();
            for (Integer j : dead) {
                if(alive.lower(j) != null){
                    active.add(alive.lower(j));
                }
                if(alive.higher(j) != null){
                    active.add(alive.higher(j));
                }
            }
            io.append(dead.size());
        }
        io.newLine();
    }
    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro u fell of

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

    Still do think its overrated after writing this piece of art which even i can't read now Submission

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

    Bro just use set

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

I hate segment trees

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

Stucked in Question B till last not able to optimise.

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

my first E yaaaaaaaaaaay

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

Anyone feel like the wording on A was weird?

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

what is the approach for B?

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

      how to count the valid triplets?

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          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
»
10 months ago, # |
  Vote: I like it +20 Vote: I do not like it

E was basically APIO 2022 P3 with nerfed limits?

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

How to solve F?

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

Good contest

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I submitted B 14 times ;-;

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

      same, my passed in 389ms

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

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

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

    I used linked list — 265 ms.

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

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

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

How to guess the solution of problem E?

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

    Notice that this problem appeared in APIO and copy paste

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    maybe 10^18 gave me a hint towards set bits....

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

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

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

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

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

    When will I be expert like you?

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

is it div3?

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +30 Vote: I do not like it

    A div four F had comparably equal ACs to today's D and lower ACs than E.

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

      maybe because majority of high rated users don't write div4?

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

      You're comparing an outlier with another outlier

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

Horrible statement for D!

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

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

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

    no bro

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

    Struggled with both A and B :)

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

      Yes agree B was trivial once u realise that fact

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

        A was relatively hard, I was confused for like 6 minutes, then I just guessed based on testcases.

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

      F missed the first line sides are 2^a[i] not a[i]

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

      Great solution bro, I have solved A and C and couldn't solve B. LOL

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

    i was struggling with B for 1 hour cause of overflow case. t-t

    → Reply
»
10 months ago, # |
  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
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Cheaters cheat what can we do :( I spent all my time on D

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

    OH NO!

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

    Just noticed it by reading your comment :/

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

    Its 2^ai

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

    the length is $$$2^{a_i}$$$. Stuck on A also because if this The string doesn't match the template if the given condition doesn't hold for at least one i.

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

    Same here, i too thought the same and trying to figure out the sliding window solution!

    → Reply
»
10 months ago, # |
← 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
  • »
    »
    10 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    noo it was the first E i did :(

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

    I feel the same , I saw some submissions to E with 9 lines of code. Even if it didn't appeared in some contest , it would still be an easy problem and clearly not E or (may be even D) level.

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

    I totally agree with you

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

    how did you find that? Had you solved this problem earlier? I searched problem E for almost 20-30 minutes but was unable to find any similar problem.

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

    how do u solve for < 90? I can understand upto 118

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

    ohh yes I was thinking that too, I realised after a while..

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

      Okay Thanks I will try this

      → Reply
»
10 months ago, # |
  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
»
10 months ago, # |
  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
  • »
    »
    10 months ago, # ^ |
      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
»
10 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Can someone tell me does KasymK cheating in this round?

→ Reply
»
10 months ago, # |
  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
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    can be formed from 0 0 0

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

      definition of degenerate triangle is given in the problem(area must be greater than 0) do you really think a combination of 3 sticks of length 0 is a triangle?)

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

        the length of each side is 2^Ai not Ai

        so in case Ai == 0 the length is 1

        its shown in first line of statement

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

          Yeah you are right I made a similar mistake during contest, my brain us melting.

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

        bro the length is 2^ai not a[i] GG

        → Reply
»
10 months ago, # |
  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
  • »
    »
    10 months ago, # ^ |
      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
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    then why you didn't solve E?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Don't want to copy code + messed up horribly (unironically know that adding a numbern that is larger than all previous corresponds to adding a 1 at the end of current bit sequence but not knowing how to deal with x2 case). What do you expect from a Green again

      → Reply
»
10 months ago, # |
  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
  • »
    »
    10 months ago, # ^ |
    ← 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 < Y$$$, or X -> X-1 -> X-2 -> ... -> Y if $$$X > 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
    • »
      »
      »
      10 months ago, # ^ |
        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
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for sharing your idea.

      → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

242304887

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

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

    In the combinations function you cast res to int, which can overflow in some testcases

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

    your ll C(ll n, ll k) actually return a int instead of a long long.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Going back to newbie :(

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

    Take a look at Ticket 17262 from CF Stress for a counter example.

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

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

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← 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
  • »
    »
    10 months ago, # ^ |
      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
  • »
    »
    10 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Video editorials for D & E here: https://www.youtube.com/@rishabhxchoudhary/videos

    → Reply
»
10 months ago, # |
  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.net/contest/1922/submission/242332530

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

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

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

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

    Spoiler
    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← 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
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain B?

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

242343507 whats up with testcase 3 in B? how can be factorial of any number be zero?

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

Can anyone explain how to approach problem D

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Video editorials for D & E here: https://www.youtube.com/@rishabhxchoudhary/videos

→ Reply
»
10 months ago, # |
  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
»
10 months ago, # |
  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
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

still trying to solve A

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why this solution 242350744 for problem C is giving runtime error on testcase 3.

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

    Try long long type instead of int.

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

      Done that already,seems like the problem was out of bound vector. My bad :(

      → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

respectfully, write better statements please.

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

E was surely much easier than D.

→ Reply
»
10 months ago, # |
  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
»
10 months ago, # |
← 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
  • »
    »
    10 months ago, # ^ |
      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
    • »
      »
      »
      10 months ago, # ^ |
        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
  • »
    »
    10 months ago, # ^ |
      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
  • »
    »
    10 months ago, # ^ |
      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
»
10 months ago, # |
← Rev. 4   Vote: I like it +7 Vote: I do not like it
A hack for C
How it works
→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 3   Vote: I like it +17 Vote: I do not like it

    Actually there's another one. A lot of contestants don't use the prefix sum to solve C. They just calculated the distance one by one. So, the following can hack them.

    1
100000
......
100000
1 100000
1 100000
......
1 100000
    The generator

    And, for problem B, there's so many people use a "cnt" array to count the appearance of a number. They just memset the cnt array in the beginning of each test case. So, just construct a test with 10000 test cases and make sure that the sum of n is 300000.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys pehle ques me toh same same but diffelent...ho gya..:)

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

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

→ Reply
»
10 months ago, # |
  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
»
10 months ago, # |
  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
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me a case where it is failing in B





int n;
    cin>>n;
    vi v(n);
    for(auto &it : v)cin>>it;
    map<int, int>mp;
    sort(al(v));
    map<int, int>smaller;
    int cnt = 0, prev = -1;
    set<int>st;
    for(auto &it : v)
    {
        st.insert(it);
        mp[it]++;
        if(prev != it)
        {
            prev = it;
            smaller[it] = cnt;
        }
        cnt++;
    }    
    debug(mp); debug(smaller);
    int ans = 0;
    for(auto &it : st)
    {
        int f = mp[it];
        int cur = 0;
        if(f >= 3) 
            {
                int NCR = ncr(f, 3);
                debug(NCR);
                cur += NCR;
            }

        if(f >= 2) cur += smaller[it];
        ans += cur;
    }
    cout<<ans<<endl;
→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    either 3 sides have to be same. (or) 2 sides have to be same and 1 side have to be lessthan other equal sides. ~~~~~ reason: In a triangle, sum of 2 sides have to be more than 3rd side. ~~~~~ As we are given in powers of 2, if 3 sides are different, then count of triangles are 0. if 2 sides are same, count = choose 2 of same size and other with size less than choosen size. if 3 sides are same, count = choose 3 from same size.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this is code, i have written for E (Increasing Subsequences)

vector<int> solve(ll n){
    vector<int> v{1}; vector<ll> dp{2};
    while(dp.back()*2<=n){
        v.push_back(v.back()+1); 
        dp.push_back(dp.back()*2);
    }
    ll cs = dp.back(); int l = v.back();
    vector<pair<int, int>> ins; int s = v.size();
    while(cs<n){
        if(cs+1==n){
            l++;
            ins.push_back({l, 0});
            cs++; break;
        }
        for(auto it = dp.rbegin();it!=dp.rend(); it++){
            if(cs+*it <= n){
                cs+=*it;l++;
                ins.push_back({l, s-(distance(dp.rbegin(), it))});
                break;
            }
        }
    }
    for(auto &i: ins){
        int val = i.first; int p = i.second;
        v.insert(v.begin()+p, val);
    }
    return v;
}

Its running perfectly fine in my local device.

when submitted, i came to see that I got wrong answer when n=pow(10, 18). i checked my solution with the code:

ll count_seq(vector<int> v){
    int n = v.size();
    vector<ll> dp(n, 1);
    for(int i = 0;i<n;i++){
        for(int j = 0;j<i;j++){
            if(v[j]>=v[i]) continue;
            dp[i]+=dp[j];
        }
    }
    return accumulate(dp.begin(), dp.end(), 1ll);
}

I sent output of solve function as input to count_seq function. I am getting pow(10, 18) implying its correct answer.

I cant figure out whats wrong. please help me.

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

    Can you tell me the submission id? So I can find why you're wrong more quickly.

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

      submission id: 242394158 link: https://codeforces.net/contest/1922/submission/242394158

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

        In your main function, you should use ll n instead of int n to read the input data correctly.

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

          Bro, this is error!!!. Thanks for correcting me. from now i will completey use ll instead of int. I have been poking my head for 3 hours. I dont know what can i do other than saying thankyou. I am just a newbie, Lets be friends. I need some guidance from pro's like you.

          → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For D when i run my code in VScode for the example testcase i am getting correct answer but when i submit or use the custom invocation i am getting wrong answer for the same testcase. Does anyone know the reason?. My Code.

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

    Your code contains an UB. In the following code block:

    for(auto itd = defence.begin(), ita = attack.begin(); itd != defence.end(); itd++, ita++){
    if(*itd < 0){
        died++;
        defence.erase(itd);
        attack.erase(ita);
        itd--;
        ita--;
    }
}

    You tried to erase 2 iterators called itd and ita, but you immediately use them after the erasing. It is now allowed and that's why there are different output of your code.

    To correct, you should create a temporary backup for prev(itd), prev(ita) and then erase itd, ita. Finally, replace itd, ita with the previous backup.

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

      Thanks for the reply. i found one more problem which was the reason for different output was in the first if block 

      for(int i = 0; i < k; i++){
    if(i == 0 && (defence[0] - attack[1] < 0))
        defence[0] -= attack[1];
                
    else if(i != k-1 && (defence[i] - (attack[i-1] + attack[i+1]) < 0))
        defence[i] -= (attack[i-1] + attack[i+1]);

      even when i = 0, the if statement is not executing because of the '&&' statement and the else if statement is running for 0 index and subtracting '-1 th' index which gives it a garbage value.

      what you suggested is another problem which i need to correct so thanks for that. so will this work??--

      for(auto itd = defence.begin(), ita = attack.begin(); itd != defence.end(); itd++, ita++){
    if(*itd < 0){
        died++;
        auto prev_itd = itd - 1;
        auto prev_ita = ita - 1;
        defence.erase(itd);
        attack.erase(ita);
        itd = prev_itd;
        ita = prev_ita;
    }
}
      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        I think the following will be better:

        for(auto itd = defence.begin(), ita = attack.begin(); itd != defence.end(); ){
    if(*itd < 0){
        died++;
        auto tmp_itd = itd;
        auto tmp_ita = ita;
        defence.erase(itd);
        attack.erase(ita);
        itd = tmp_itd;
        ita = tmp_ita;
    } else {
        itd++;
        ita++;
    }
}

        Your updated code still have some problem. If the itd points the first element of defence, you cannot to set the prev_itd to itd - 1.

        → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C.

Solution
→ Reply
»
10 months ago, # |
  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
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Because it is O(n^2)
    Think what happens if no one ever dies

    → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    The time complexities of your two codes in the worst condition (i.e. No one dies) are both $$$O(Tn^2\log n)$$$. It will get TLE obviously. To improve, you can check my submission. We should avoid useless check of whether a monster dies when its left and right neighbours don't die.

    Spoiler
    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When does the system testing start?

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Video solutions for A-C, D-E

→ Reply
»
10 months ago, # |
  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
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally Expert !!!

→ Reply
»
10 months ago, # |
  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
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

242432261 Can anyone explain why this code is giving WA on testcase 5

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anuone help me. I have written the code for problem D with linkedlist and its working properly for test1. But, I am getting runtime error: "-1073741819 exit code" for test2 . what should i do.

The test case details are in https://codeforces.net/contest/1922/submission/242434985

my code:


// object of linked list
class obj{
public:
    int a, d; // attack and defend values
    obj* next{nullptr}; obj* prev{nullptr}; //next and previous monsters
    obj(int at, int de, obj* p, obj* n=nullptr){
        a=at, d=de; prev=p;next=nullptr;
    }
};
bool check(obj* curr){ // checks if current monster will be deleted
    if(curr->prev==nullptr && curr->next==nullptr) return false;
    else if(curr->prev==nullptr){
        if(curr->d<curr->next->a) return true; else return true;}
    else if(curr->next==nullptr){
        if(curr->d < curr->prev->a) return true; else return false;
    }else{
        if(curr->d < curr->prev->a + curr->next->a) return true; return false;
    }
}
int main(int argc, char const *argv[])
{
    int T; cin>>T;
    while(T--){
        int n;cin>>n; vector<int> A(n, 0), D(n, 0); // A for attack and D for defend
        for(int i = 0;i<n;i++) cin>>A[i];
        for(int i = 0;i<n;i++) cin>>D[i];
        obj* head = new obj(A[0], D[0], nullptr);
        obj* l = head;
        for(int i = 1;i<n;i++){
            l->next=new obj(A[i], D[i], l);
            l=l->next;
        }
        deque<obj*> next_del;// contains all monsters that are going to be deleted in next round
        for(auto t = head; t!=nullptr; t=t->next){
            if(t->prev==nullptr && t->next==nullptr){
                
            }else if(t->prev==nullptr){
                if(t->d < t->next->a) next_del.push_back(t);
            }else if(t->next==nullptr){
                if(t->d < t->prev->a) next_del.push_back(t);
            }else{
                if(t->d < t->prev->a + t->next->a) next_del.push_back(t);
            }
        }
        vector<int> ans;
        while(next_del.size()){
            ans.push_back(next_del.size());
            set<obj*> altered; // contains all monsters that needs to be checked.
            while(next_del.size()){
                obj* front = next_del.front(); next_del.pop_front();
                obj* prev = front->prev; obj* next = front->next;
                while(next_del.size() && next_del.front()==next){
                    next_del.pop_front(); next=next->next;
                }
                for(obj* ob = front;ob && ob!= next;){
                    obj* ppp = ob;
                    if(ob)ob=ob->next; if(ppp) delete ppp; 
                }
                if(prev) altered.insert(prev);
                if(next) altered.insert(next);
                if(prev) prev->next=next;
                if(next) next->prev=prev;
            }
            next_del.clear();
            for(auto &i: altered){
                if(check(i)) next_del.push_back(i);
            }
        }
        while(ans.size()<n) ans.push_back(0);
        for(auto &i: ans) cout<<i<<" "; cout<<"\n";
    }
}
→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Try not to use pointers. In CP, using arrays prev and next will be better than using pointers. You can check my submission to see how to use arrays instead of pointers..

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

    I found where's wrong in your code now. Here's the updated version.

    There are two modifies. The first is to remove the block:

    while(next_del.size() && next_del.front()==next){
    next_del.pop_front(); next=next->next;
}
for(obj* ob = front;ob && ob!= next;){
    obj* ppp = ob;
    if(ob)ob=ob->next; if(ppp) delete ppp; 
}

    and add the following:

    front->prev=nullptr;
front->next=nullptr;

    The second is correcting the check function. If curr->prev==nullptr satisfies, we should execute if(curr->d<curr->next->a) return true; else return false; but not if(curr->d<curr->next->a) return true; else return true;. (Pay attention to the last word)

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    When $$$n=2$$$, dist only contains 1 element. Then, prefixSum[1]=dist[0]; and suffixSum[dist.size()-1]=backDist[dist.size()-1]; will cause an RE.

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

      when n=2 

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

      that is

      suffixSum[0]=backDist[0]

      i dont get how it will cause RE can you explain a little

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

        My mistake. Actually it's here:

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

        dist.size() will return a size_t (a.k.a unsigned long long or unsigned long, depend on your machine and compiler) type. Then, minus it with $$$2$$$, we'll get a very large number ($$$18446744073709551615$$$ or $$$4294967295$$$). Then let i be that and try visit suffixSum[i]. It will cause the RE here.

        To correct, just change dist.size()-2 to (int)dist.size()-2. This convert the unsigned long long to int.

        I've modified your solution and it's AC now.

        BTW it's very weird that you've submitted an AC solution but then submitted an RE one! And that two codes are so similar.

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

          Thanks ohhh i was trying to figure out why my code is giving RE that's why i was trying to submit different codes

          just got a little pissed as i wasn't able to submit in the contest

          → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, I can't understand I just can get AC in contest even though I finish n queries in each test case rather than m queries :(

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

    That's because the pretests are too weak. In fact, in this round, C's pretests are the weakest one as there's more than 100 hacks about problem C.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A Statement Was Too Confusing

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Easy video explanantion for problem E

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

downvote, if you liked editorial

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

W

→ Reply