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

Hopefully I reached Expert :)

great

I wish everyone a good contest!

Good luck to every Contestant!My 3rd rated contest. Wonder if I could reach True Rating 1700(displayed 1400)

Good Luck and Have Fun everyone!

Good luck to everyone

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

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

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

New: Educational Rounds on Codeforces!

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

Hopefully I can get

Pupil(not Newbie) :/You didn't even give the contest

BledDest Round

SpoilerYou Know its Graph Time

No please god no!

you're right

Hope I can get Expert badge.

Often, how much harder are Educational Rounds compared to normal rounds? I want to know whether to compete or not. This is because my last educational round gave me some serious trauma: Educational Codeforces Round 153 (Rated for Div. 2)

Slightly more difficult than normal div 2 round. Sometimes edu rounds needs good observations skills also.

Alr thanks! I'll participate.

Hopefully I reached Specialist :)

Hope for a positive delta.

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

for pupil i think 2 is enough.

Educational round is overratedEducational round means you have to study gcd well :)

l have nothing big,Pupil hop to be reached!

we share the same rating, I hope we share the promotion too.

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

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

Upd: Solved 3. Did C Overcomplicated :(

anxiety

bad explanation of first question

true !!

[deleted]

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

How did you know he is using an alt ?

i guess someone snitched his alt which made his accusation hypocritical

What happened to "romanian diversion strat"?

This First question made me skip contest man :(

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

thats apio2022 perm

Okay I start to implement it

I got 98.8 pts and stuck on it :(

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

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

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

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

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 ??

i pre-calculate cost of go forward and backward

yeah that's the resolution i think

This problem maybe doesn't require the shortest path algorithm

C was a modified version of prefix sums

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

proofLet's assume wlog that

`x < y`

, you have to reach for sure point x+1 to get closer to y If`x`

is closer to`x-1`

than`y`

, you can go to x-1 at cost 1 and than come back to x at cost at least 1. So, at the end, you will stay in point`x`

with -2 coins. Then the path from`x-1`

to`y`

is mandatory, so the final cost will be increased by two. This is the best condition.Damn, the first question reduced my life by a few years. :')

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

I have skill issue

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

I think E was way harder :(

Wasted too much time in problem A :/

can someone please explain problem A? Thanks in advance.

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

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

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

only condition 2 is enough

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.

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."get it now, thank you.

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

awoo Loved the D and people think LinkedList is overrated.

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):

bro u fell of

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

That's upto how we implement it. https://mirror.codeforces.com/contest/1922/submission/242308688

i know that lol i am bad at coding, point is that linked list is overrated

I think have a better code using a linked list and its usage is underrated in CP submission

Bro just use set

I hate segment trees

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

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

242254308

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

You can check my solution

Hope it helps

Well actually you can just simply use prefix sum for that:

You can see my code here: 242282293

Stucked in Question B till last not able to optimise.

my first E yaaaaaaaaaaay

Anyone feel like the wording on A was weird?

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.

what is the approach for B?

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.

how to count the valid triplets?

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

E was basically APIO 2022 P3 with nerfed limits?

How to solve F?

Good contest

I submitted B 14 times ;-;

I can feel your pain :(

Did the authors intend to cut off solutions to D that uses two

`std::set`

s? I got TLE on my first attempt before finally switching to segment trees.No, I used two

`std::set`

s as well and it passed in 700mssame, my passed in 389ms

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.

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

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

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.

I used linked list — 265 ms.

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

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

How to guess the solution of problem E?

Notice that this problem appeared in APIO and copy paste

orz

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

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

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.

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

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.

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.

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

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

When will I be expert like you?

is it div3?

A div

fourF had comparably equal ACs to today's D and lower ACs than E.maybe because majority of high rated users don't write div4?

You're comparing an outlier with another outlier

Horrible statement for D!

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

no bro

Struggled with both A and B :)

Us bro.

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.

Yes agree B was trivial once u realise that fact

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

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

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

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

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

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

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$$$ .

OH NO!

Just noticed it by reading your comment :/

Its 2^ai

Sorry, typo, fixed.

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.`

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

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.

noo it was the first E i did :(

You copied from the internet, cheater

no it was easy

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.

I totally agree with you

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.

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

It's hard, you can find discussions here

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

My Code

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

Us

I noticed it too late into the contest.

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

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

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

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

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

Okay Thanks I will try this

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

bye-bye my rating 😂

nvm

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

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.

thanks

Can someone tell me does KasymK cheating in this round?

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.

can be formed from 0 0 0

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?)

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

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

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

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

......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

then why you didn't solve E?

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

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

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.

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.

Thanks for sharing your idea.

242304887

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

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

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

Going back to newbie :(

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

UPD: I found out why, thanks

In third testcase you have 12 subsequenses. In forth testcase you have 36 subsequenses.

There are 12 increasing subsequence.

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.

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

The problem is the first occurrence of this line:

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.

didn't expect that.. Thanks

Take a look at Ticket 17262 from

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

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

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

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.

i missed up this

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.

Can Anyone please explain the logic behind Problem D ...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.

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.

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

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://mirror.codeforces.com/contest/1922/submission/242332530

Take a look at Ticket 17261 from

CF Stressfor a counter example.How to solve F? Does it use some specific optimisation?

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

Spoilerdp[l][r][k].

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.

Can someone explain B?

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

Got it , Thanks!

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

Can anyone explain how to approach problem D

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

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.

Thanks !!!

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

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

Take a look at Ticket 17263 from

CF Stressfor a counter example.thank you, I know where my solution failed and I have solved it.

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

Take a look at Ticket 17264 from

CF Stressfor a counter example.Thanks! Finally solved it.

still trying to solve A

Ask Ruchi she will help

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

Try long long type instead of int.

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

respectfully, write better statements please.

E was surely much easier than D.

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.

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

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.

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...

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

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.

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

A hack for CI don't know why there's an empty line in the beginning :(

How it worksMany people compare $$$a_i-a_{i-1}$$$ and $$$a_{i+1}-a_i$$$ in their codes, and some of them assign $$$a_0=-inf$$$ and $$$a_{n+1}=inf$$$ to make coding easier. However, if $$$a_0\ge-1e9$$$ or $$$a_{n+1}\le 2e9$$$, then $$$a_1-a_0$$$ or $$$a_{n+1}-a_n$$$ isn't big enough so they output $$$1000000000-0=1000000000$$$.

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.

The generatorAnd, 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.

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

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

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

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

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

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.

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

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:

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.

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

submission id: 242394158 link: https://mirror.codeforces.com/contest/1922/submission/242394158

In your main function, you should use

`ll n`

instead of`int n`

to read the input data correctly.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.

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.

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

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.Thanks for the reply. i found one more problem which was the reason for different output was in the first if block

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??--

I think the following will be better:

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`

.Thnaks a lot. :-)

Problem

C.Solution`0 8 12 15 20`

-->`8 4 3 5`

.`8 4 3 5`

and`8 4 3 5`

.`>`

for one array, and with`<`

for another. Change values of array of differences to`1`

when comparison result is`true`

:`8>4>3>5`

and`8<4<3<5`

`1 1 0`

and`0 0 1`

Prepend and append

`1`

to the arrays (as edge elements had only one neighbor):`1 1 1 0`

and`0 0 1 1`

That becomes:

`1 1 1 5`

and`8 4 1 1`

.`0`

to the arrays and make cumulative sums:`0 1 1 1 5`

and`0 8 4 1 1`

becomes`0 1 2 3 8`

and`0 8 12 13 14`

.`i`

<=>`j`

.(Code:242346587)(Perl).

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

Because it is O(n^2)

Think what happens if no one ever dies

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.

SpoilerActually, your second version of code which uses linked list is not improved at all. You still do not to avoid useless calculation.

When does the system testing start?

It has already ended. It ended around 19:00.

Video solutions for A-C, D-E

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)$$$.

Finally Expert !!!

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

You use the

`Counter`

in Python. Its worst case is`O(n^2)`

when you convert a list to a counter because of hash collision. Someone construct this worst case.Exactly. I made some small modifications to your code to counter the issue of hash collisions, and then your code passes: https://mirror.codeforces.com/contest/1922/submission/242430708

I see. Thank you both.

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

You should write

`n-=(1LL<<(ll)(cnt-1))`

instead of`n-=(1<<(ll)(cnt-1))`

. It's around the sixth line in the function`solve`

.Updated code: https://mirror.codeforces.com/contest/1922/submission/242436814

Thank you very much

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://mirror.codeforces.com/contest/1922/submission/242434985

my code:

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..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:

and add the following:

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)Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Can anyone help me find why this code is giving runtime error in testcase-2

Problem-C

PLease help !!!

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.when n=2

that is

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

My mistake. Actually it's here:

`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.

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

For problem C, I can't understand I just can get AC in contest even though I finish

nqueries in each test case rather thanmqueries :(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.

Problem A Statement Was Too Confusing

Easy video explanantion for problem E

downvote, if you liked editorial

Good luck to everyone!

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

W