##### Hi, Codeforces!

Alexdat2000, Igorfardoc, and I are pleased to invite you to our Codeforces Round 890 (Div. 2) supported by Constructor Institute, which will be held on Aug/05/2023 17:35 (Moscow time). **This round will be rated for participants with a rating lower than 2100.**

We would like to thank:

- errorgorn for coordinating the round.
- Umi, maomao90, thenymphsofdelphi, Dominater069, Mike4235, valeriu, irkstepanov, zengminghao, Gheal, DeMen100ns, FEDIKUS, thanhchauns2, MinaRagy06, Java, xudian, madlogic, squishybanana04, stefanbalaz2, kobebryan9, Murinh0, IlyinAD, zamong_juice, Pemguimn, the_hyp0cr1t3, STommydx, peshkoff, AndZhi, revelcoS, Valenz, and tibinyte for testing the round and providing useful feedback.
- MikeMirzayanov for Codeforces and Polygon.

You will be given **5 problems**, one of which is divided into two subtasks, and you will have **2 hours** to solve them.

One of the problems will be interactive, so please read the guide for interactive problems if you are not familiar with it.

**The score distribution is 500 — 750 — 1250 — 2000 — (1500 — 1500)**

**UPD: Tutorial**

**UPD2**: Congratulations to the winners!

**Div. 2:**

**Div. 1:**

We are thrilled to share some exciting news with you! We are teaming up with our partner, **Constructor Institute in Schaffhausen, Switzerland**, to bring you an amazing opportunity: a round supported and organized in collaboration with Constructor Institute, where you can explore Master's programs in Switzerland. Now we pass the floor to our partner.

*Hello, Codeforces community!*

**Constructor Institute in Schaffhausen (Switzerland)** is pleased and proud to have the opportunity to support the round on Codeforces. We invite you to participate in it!

*If you are passionate about studying in Switzerland and pursuing a Master’s degree, we encourage you to fill out the form to initiate the application process and scholarship interview. Our Institute representatives will be in touch with you to guide you through the next steps.*

**We offer two Master programs, both taught in English, with flexible duration of 1.5 or 2 years full-time:**

*MSc in Computer Science, Software Engineering, and Leadership**MSc in Quantum Software Engineering, and Computer Science*

*Our Master's programs open doors to a world of opportunities. Many of our students have secured high-profile roles in multinational companies in Switzerland and across the globe. Additionally, our programs also serve as an excellent preparation for Ph.D. research in fields such as software engineering, cybersecurity, artificial intelligence, and other advanced topics.*

*We understand that financing your education can be a concern, and to support your journey, we are offering the following scholarships:*

*Tuition waiver scholarships — 20,000 CHF per year, covering the cost of tuition fees.**Full scholarships — 20,000 CHF per year, covering the cost of tuition fees, along with a monthly stipend of 2,000 CHF to assist with living expenses in Schaffhausen.*

*Both scholarships are non-repayable, providing you with financial peace of mind.*

*To learn more about Constructor Institute and its programs, visit our webpage.*

**Eligibility for the programs and its available scholarships:**

*You have obtained or you will obtain a Bachelor’s degree in Computer Science, Software Engineering, Physics, or a related field before the program starts.*

*To express your interest in this opportunity, please complete the form:*

*Complete the Form*

*We wish you good luck in the competition and enjoy solving the problems.*

Omg Igorfardoc round!

Omg sponsored div2 round!

It will be interesting if Mike and the team can share how they prepare a contest.

So we can understand your efforts and hard work to conduct a contest.

Yes, I agree as I believe it would greatly deepen all participants' understanding of the contest if the authors can share with us the problem statements beforehand.

Problem statements won't help me. They should provide editorials for the questions before-hand

Editorials won't help me, They should provide Author's solution before hand.

Author's solution won't help me, They should hand me my -100 rating before hand

I think he meant after the contest.

Getting Problem statements before the round will be very useful to prepare for round.

Go to catalog section. There you'll get most of your answers.

can i expect constructive algo problem? as it was sponsored by constructor institution

Oh hell no

As a tester, I thought the problems were nice, and I recommend participating in this round!

As a tester, I hope my enjoyment when testing the round would be indicative of your enjoyments when participating in it.

orz tibinyte testing round !!!

Hope to become cyan!

Hoping to reach specialist this time.

All the Best shrey_17sept

ughhhhh!!! again was vv close... waiting for the rating rollback...

Hope to become specialist before arrival of Joyboy

manga readers...

garp is in danger

Hope to be constructive(as this round)

As a tester, I really enjoyed this round! Everyone should participate!

My favourite pokemon !

I say a full constructive and a happy specialist for me. gl everyone!

As a participant i recommend all of you to participate.

As a tester, good luck! (And give me contribution)

I'll solve at least 4 problems,good luck to me.

Based on the score distribution, I think this round would be speedforces.

Hiha, this round is going to be fun! >_<

hoping to become pupil again

As a tester, problems is excellent and cute :>

This Constructor Institute, it's the former "Schaffhausen Institute of Technology", right? Is it going to obtain (or maybe already has) accreditation any time soon? I also wonder what's the connection with Constructor University Bremen... They seem to share the logotype.

As a tester, ris noitubirtnoc em evig esaelp

Is this a hint to one of the problem :>

Use reverse(str.begin(), str.end()); :p

good try

Round Clashing with Leetcode Round

Codeforces > Leetcode

I know that Codeforces >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Leetcode

But for interview prepration as told by striver_79 u should have to give Leetcode Contest

hope i can ac C problem ：）

did you?

No,I always wa test 2 :(

Thanks,Constructor Institute.

Hope I can be a master.

5 problems? I think it will be hard.

actually 6 problems,because one of the 5 problems is divided into two subtasks

Hoping to become pupil this contest

preparing for permutation problems :) DYK? A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Wish you all lots of love, good luck and non-negative deltaAs usual quietpan did well. Wish solvemproblr had given :(

A literally A very Very Very Very Very bad contest : ( ( ( ( ( ( (

It's good to see that cf is finally improving on their problem statements.

For me, this was the coolest contest I've been to in the last couple months. Namely in the fact that the tasks mostly do not require knowledge of complex algorithms, all the solutions are quite short. Thank you! And a question. in E2 n = 1e6 to prevent bitset O(n^2/64) solutions?

I'm fed up with these constructor algo problems.

A: If a[i]<=a[i+1], then 0 <= max(0, a[i+1]-1) and a[i]-1 <= a[i+1]-1 <= max(0, a[i+1]-1), therefore max(0, a[i]-1) <= max(0, a[i+1]-1), then a[i]<=a[i+1] holds after any times of operation. If a[i]>a[i+1], we need to perform a[i] operations to make a[i]=a[i+1]=0. So the answer is max(a[i]) where a[i]>a[i+1].

B: If n==1 there's no solution, let's assume n>=2. Let t be the number of occurences of 1 in a[i]. If t==0, then we can let a[1]+=n-1 and a[i]-=1 (2<=i<=n). Let's assume t>=1. Then sum(i: a[i]==1)(b[i] — a[i]) >= t because b[i] is positive integer and b[i]!=1, so b[i]>=2. Therefore, sum(i: a[i]!=1)(b[i]-a[i]) <= -t --> sum(i: a[i]!=1)(a[i]-b[i]) >= t --> sum(i: a[i]!=1)(a[i]-1) >= t. So if sum(i: a[i]!=1)(a[i]-1) < t, there's no solution. Otherwise, we can construct a solution: First turn 1 into 2, then we reduce the maximum element in a by 1 for t times. If there's some a[i] remain unchanged, then a[i]>1, then we can reduce them by 1 and add them to any occurence of 2.

C: For any 1<=i<=n-1, let's find the maximum value it can become by binary search. Assume the value we are checking is T. Then we need T-a[i] operations on i-th element. If a[i+1]>=T-1 then we are done. Otherwise, we need T-1-a[i+1] additional operations on (i+1)-th element, Then check if a[i+2]>=T-2. We repeat this process until we find some j such that a[i+j]>=T-j, or we have used more than k operations. Then we can solve the problem in O(n^2*log(k)).

D: We can solve the problem by D&C (Divide and Conquer). Assume we need to find the index of maximum element on [L, R]. If L==R then the answer is L. If L+1==R, we can do query(L, R) and the answer of query is 1 if p[L] is the maximum (0 otherwise). In general cases, we choose M close to (L+R)/2 and solve (L, M) and (M+1, R) recursively, assume their answer be x, y. Then we only need to find if p[x]<p[y]. Let's do query(x, y) and query(x, y-1), the difference of answer of the queries means "there are how many i such that x<=i<=y-1 and p[i]>p[y]". If p[x]<p[y], then we have p[i]<=p[x]<p[y] for x<=i<=M and p[i]<p[y] for M+1<=i<=y, so the difference will be 0. Otherwise we have p[x]>p[y], so the difference will be at least 1. Then we can solve the problem. The cost of queries will be not greater than 2*n^2 for the top layer, 4*(n/2)^2 = n^2 for the second top layer, 8*(n/4)^2 = n^2/2 for the third top layer and so on. So the total cost is not greater than n^2*(2+1+(1/2)+(1/4)+...)=4*n^2.

For C, how does O(n^2*log(k)) pass so seamlessly if n=1000 and n^2*log(k) = about 2e9?

Edit: Soz idk why I thought n^2 = 1e8 imma kms

$$$n^2 \log_2 k = 1000 \cdot 1000 \cdot \log_2 10^8 \approx 10^6 \cdot 26 = 2.6 \cdot 10^7$$$, not $$$2 \cdot 10^9$$$

1000*1000*20 = 2e7...

your maths is blowing my mind

`log_2(1e8)`

~= 26,`n^2`

= 1e6`n^2lgk`

~= 2.6e7$$$O(n^2)$$$ has very little constant, and if you count $$$n*n*log(1e9)$$$, it's actually $$$30'000'000$$$

We can optimise the min max range to

.

In B why can't we just jumble up the elements of the array such that a[i]!=b[i] and all elements will remain same so the sum of array a will be equal to array b ?

because you can have an arr=[2,2,2] and still come up with answer [1,1,4] while if you try to jumble you will still end up with having the same array.

Thanks.

How to approach C problem anyone??

binary search on answer.

binary search to find the maximum possible $$$a_i$$$ we can make for every $$$i$$$

YocyCraft's solution is good — in order to find it, you probably have to make the observation, that it has to be optimal to increase only one segment of numbers. After that, you can try starting that segment at every number.

Note that we can binary search the answer, as the following gives rise to a monotonic function -

We ask the simpler question: "Is the value

`X`

attainable after at most`k`

operations?"Since the constraints on n are small enough, an

`O(n^2)`

solution suffices.Loop through the array, checking if we can make this current element equal to

`X`

. We can calculate the cost required to make this element equal to`X`

, by simulating the process, making sure that the next element is adjusted appropriately using recursion. If we can afford the cost, then we say that we can attain`X`

. Otherwise, we are unable to achieve`X`

.Careful implementation must be done, but this is the general overview of the logic.

Ough, probably I need to learn binary search, as I didn't try to use it and wrote $$$O(n^2)$$$ solution, which I thought is very difficult for $$$C$$$ problem.

Could anyone please tell me how my E1 question didn't pass the test 7?

correct output is 4

My first subbmission can pass this test case

Thank you so much.

It seems like you should update your dp values from n to 1 instead of from 1 to n, otherwise you could have updated some larger values before you visit it.

Oh my God, this mistake is so classic. I can't believe I made it again.

I made exactly the same mistake during the contest orz.

E2，seems to be bad. why 1e6.

so any hint?

why 1e6We wanted to force $$$O(\frac{n\sqrt n}{32})$$$ complexity. Although $$$O(n \log^2 n)$$$ FFT methods can also pass. I think it is suitable for div 2 round to make the last problem more "educational".

Is this the reason why E1 is so basic?

Many people using 2log FFT didn't pass. The bitset solution is not educational, just very intentional and unnatural. Your goal is to educate, not to show off.

what is 2log FFT btw?

Guess: it is divide and conquer and performing FFT on each array $$$O(n*log(n))$$$

hence $$$n*log^2(n)$$$

divide and conquer + FFT

thanks

Do you know how it feels like to only come up with a $$$\mathcal O(n\log^2 n)$$$ solution when $$$n = 10^6$$$?????? I thought about the 2log FFT for almost an hour and struggled on how to optimize it, but you finally tell me it actually is intended solution?????????

$$$\mathcal O(\dfrac{n^{1.5}}{w})$$$ is a totally brute, I agree with you. But that doesn't mean you have to limit it ———— It can still pass, it's not a big number. From a progressive perspective, this is a worse solution, indeed. but within the scope of programming competitions, some things just simply cannot be hacked. Come on, Codeforces don't have Quantum machines; I don't think it is allowed for you to enlarge the data range at will.

I think it's so bad, really. It's not a joke. Nor E2 problem itself is educational.

I'm not saying it is an intended solution, it's

not. I am saying that it is possible to get AC with it with some optimizations. The intended solution is the $$$O(\frac{n \sqrt n}{32})$$$. It is just that we are not concerned whether or not the alternative $$$O(n \log^2 n)$$$ will TLE or AC.I'm personally not sure how my comment got intepreted as $$$O(n \log^2 n)$$$ is the intended solution...

Oops, it seems that we have some different understandings on your word "force"......

So since you are not concerned about the alternative solution, why don't you just reduce the data range to $$$5\times 10^5$$$ or less? You say that you are not concerned. And in that case, all $$$\mathcal O(\frac{n^{1.5}}{w})$$$ solutions will definitely pass without caring about constants.

The word "force" is used here to mean that we wished to separate $$$O(n^{1.5})$$$ and $$$O(\frac{n^{1.5}}{w})$$$. In fact, a tester (Umi) submitted $$$O(n^{1.5})$$$ that we are still unable to hack.

To suggest to contestants to contests that we do not want to accept $$$O(n^{1.5})$$$, we made constraints much bigger than normal $$$O(n^{1.5})$$$ problems.

Edit: Umi's solution is described in their comment at https://codeforces.com/blog/entry/119058?#comment-1055388

You think the impression is more important than the actual? You want people to think nsqrtn as unpassable, but some people still could pass? You are just like the ostrich who sticks its head in the sand.

But seems that many $$$O(\frac{n \sqrt n}{32})$$$ solutions didn't passed?

Well, we are sorry about that then.

I thought that our solution (which ran in ~1200ms) already had rather large constant. We use stl bitset with the variable bitset trick from https://codeforces.com/blog/entry/100910?#comment-896029. I'll have to see what bitset implementations people are using for future contests.

It seems that some solutions used dfs to walk the tree and got RE,and if we change it to loop from $$$n$$$ to $$$1$$$,it could AC.

i also use O(n*sqrt(n)/32) and it is just 749ms as you can see it here : https://codeforces.com/contest/1856/submission/217710498

I heard some of my friends used FFT and got TLE,and some got PP;And I also found some implemented-nice bitset solutions passed,and some bad $$$O(\frac{n \sqrt n}{32})$$$ solutions got TLE.Is this really suitable for a CF contest?

How to solve it with FFT in $$$\log^2 n$$$? I can only understand how to do it in $$$\log^3 n$$$

hint for E2?

I haven't solved it, but it looks like $$$O(n^{1.5})$$$ knapsack

I boiled to problem to:

solve the following problem for each $$$i$$$ from 1~n:

denote a = $$$[sz_v]$$$, where $$$v$$$ is all the direct sons of $$$i$$$ and $$$sz_i$$$ denotes the subtree size of $$$i$$$. find a subset of $$$a$$$ $$$v$$$ such that $$$\sum v$$$ multiplied by $$$\sum a-\sum v$$$ is maximum.

but i don't know how to solve this:( seems that top performers used some sort of crazy stuff lol

Intended complexity is $$$\mathcal{O}(\frac{n\sqrt{n}}{32})$$$. The key idea is that the total sum of values for the knapsack isn't too large. So the number of distinct elements is small. See https://codeforces.com/blog/entry/49812 for details.

I did exactly this but didn't AC

The $$$\frac{1}{32}$$$ factor is actually significant! In your solutions, I see that you either

`vector<int>`

(which doesn't help)`vector<bool>`

which is a bitset, but you do not use bitwise operations on it (shift + or, instead of manual loop).I didn't know we could do bitwise operations on vector of bool. Either ways, that's a stupid thing to trap a solution on, I think bounds should have been looser

Wow, thanks

Anyone who had wa7 on e1, how did you deal with it?

thanks you people_plus_plus for great testcase, now I know that I don't know how to use knapsack properly

i wish all cf problem statements are like this contest. even though I did badly in it.

Any idea for E1? I thought of a dfs approach, in which I visited every node and counted the total number of nodes in it's subtree. Then according to the number of immediate children to the node, I tried dividing the total number of nodes in the subtree into two groups such that both the groups have roughly the same number of nodes.

I kept getting wrong answer on test case 7 for some reason I don't understand. Can anyone provide some insight to it please?

Your idea is very good, the only part that is missing is how exactly you are dividing the subtrees into two groups. In order to do that, you have to use a kind of knapsack-DP in order to calculate all sizes of the two groups

Can you please elaborate a bit, my idea was also similar but I didn't know how to approach further with it.

Can you please tell me what are the dp states?

For a certain node: dp[i] = true iff there exists a subset of the subtrees of the node that have together exactly i nodes. For each subtree with k nodes, you update the dp-array by setting dp[j] to true iff dp[j-k] is true. For a node which has m subtrees with n nodes together, this runs in O(nm).

Can we do it for E2

That method does not work for E2. Consider the case of the root having the other 10e6-1 nodes as children: Then, the dp-array has the size of 10e6-1 and we iterate through it 10e6-1 times. It is possible to improve that by small constant factors, but for E2 you have to make bigger changes

It is interesting, that transition from E1 to E2 looks like a super standard problem that everyone should know how to solve, yet so much struggle to do so. (Note, personally idk how to solve E2).

Just wanna know how many people got WA on problem D because of making query with l = r LOL.

WA on 6th pretest in C anyone?

Submission: 217341446

long

Thank you for your invaluable feedback, but I did use long long for my calculations in C (also the answer can't exceed a 32-bit integer)

Improve your binary search correctness. You need a standard.

I did not use binary search, I tried to do a greedy $$$O(n^2)$$$ solution, you can observe that the maximum value can be obtained if you build a pyramid that is tilted to the left.

Your situation is same as mine. During contest, I also got WA 217328079 on 6th pretest in C. Our approaches are similar. Both the outer loop and inner loop are counting backwards.

Once I changed the inner loop to count forward, I can get AC. See my 217375396. Not sure why yet.

I have just found the mistake in my implementation — I wasn't updating the height of the first element in the sequence after lifting the entire sequence, the correct submission: 217377033 (the only difference is that I have added the

`current`

variable)Take a look at Ticket 17042 from

CF Stressfor a counter example.Thanks so much!

Who decided E1 was a good problem on 5th position?

I mean, according to the problem points (1500 for E1, 2000 for D), it was expected that E1 would be easier than D.

just asking to confirm if it is just with me or happening with u also? Did the first question took more than 5 minutes to load for u all?

No. You might want to try mirrors of codeforces like m1.codeforces.com, as they work much faster

Most balanced contest ever!

Cool problems, thanks. :)

wasted 30 minutes on C because I did not read the constraints carefully

Had high hopes from this contest, but got stuck at A:(

Please help me what went with my logic/code ; It keeps failing on pre-test 2. I am not able to find a test case, where this fails. If you could provide me with one, I can word out the error myself. Thanks!

What's your logic?

If the array is already sorted, we need 0 operations, so print 0.

Else find the index of maximum element If the maximum element is not at the last index, we need to make the max element = 0 for sorting the array, in this case the number of operations is equal to the value of the maximum element.

else if the maximum element is at the last index, find the first index from last after which the array is sorted or find the first index i from last where v[i]<v[i-1] ; once you get the index ; array from i to n-1 is already sorted & you need to make the maximum element in range[0,i] equal to 0 for making the remaining array sorted, thus max element in range[0,i] is the answer.

you are making it too complicated, try to observe the basic pattern

knot_scared you are right ; the simple idea just didn't click for me today & I went for overcomplicated ideas ; but I just want to know where my idea is lagging. I am not able to find a test case, where this fails. If you could provide me with one, I can work out the error myself. Thanks!

I will give you a test case where your solution fails but keep in mind that you should in general go for the simplest solution. Try to solve the problem again and find the simplest way to solve if you want to improve.

1

4

7 4 10 10

your codes answer: 10 correct answer: 7 after 7 operations the array becomes 0 0 3 3

OmarAboutaleb77 thanks for your help man! The max_element() points to the first such value if multiple max values are there. Would surely go for simple logic only. Thank you.

Hints for B?

Spoilerif n = 1 the answer is no if the array doesn't contain ones the answer is yes think in this case : x y z 1 1 1 1 1 1 what can u do? another hint : u can do two things either place x, y, z on the position of ones or take ones from x, y, z and add to the ones or both

Rough Idea: Just watch out for number of 1s in a. If there are none, then a_i := a_i — 1 for all i in {1,2,...,n-1} and a_n := a_n + n-1 Otherwise, let y be number of 1s and x is sum of non-one numbers... increase each of these y 1s to 2 and so, if x — y >= y, then YES else NO. [This works because you can reduce these non-one numbers to cover up the y increment and if something is still unchanged, reduce it by 1 [not equal to zero as this value is at least 2] and increase one of the 1s (original) by another 1]

Distribute money from rich to poor

How is that?

Take the money from the richest guy and make the change in the lives of the poorest guys.

[Richest] [Mediocre] [Mediocre] [Poor] [Poor] [Poor] [Poor] [Poor]

The richest guy wants to affect the lives of as much people as possible. The richest guy knows that Mediocre guy will not appreciate 1 cent donation as much as the poor guys would. That's why the richest guy always targets the poorest to make the most impact on the population.

please help in C

use binary search on each index.

Binary search on the answer + bruteforcing every position where the maximum value will be

C was a good problem E1 also. I solved it with DFS+SUBSET SUM Dp

can you explain your E1 solution?

Is it possible to solve C without binary search? My idea is to check each subarray and find the maximum value achievable, but was not able to implement it in $$$O(n ^ 2)$$$.

I'm waiting for the sys testing to be over, so I can see what I did wrong in my $$$O(n^2)$$$ approach (intuitively I think it's totally possible)

Yes its possible, you need to maintain the maximum allowed value of ai for subarray [i,j] based on values in [i,j] and j+1. Rest is just sum of AP and prefix sums

Solution : https://codeforces.com/contest/1856/submission/217318594

well，E1 is easier than D and it can easily AC,but E2's score is lower than D,it makes A+B+C+D+E1 > A+B+C+E1+E2 . you know , AC E2 is more and more and more harder than AC D.

Is it good?

Could anyone tell me why my E1 code returns the wrong answer on test #13?

my E2 solution without bitsets fits in half of TL, can anyone hack? 217346719

My solution without bitsets works in 452 ms, while with bitset — in 421 ms. Without pragmas and bitsets — in 900 ms.

Knapsack part of Problem E might match for many contestants if they used same website to get the code

A question to anybody who solved C: this problem is about BS on the answer. How do you understand a problem requires being approached in this way? Is there a particular signature or something which makes you think in this direction? Is it the constraints? The fact that the operation was mentioned to be performed no more than k times? Does it ut just comes with experience and/or by solving similar problems(if yes please suggest some)? Any good insight is appreciated.

If problem is such that answer at some point is possible then it must be possible for all either less or greater values then we can try to think of binary search. A better and formal name for this behaviour is montonic function. A monotonic function is a function which is either entirely nonincreasing or nondecreasing

in this case the function is like if we can get a value x then for sure we can get another value <= x?

Yes, so that's why we only then need to search for values > x

ok. Which is if I found that for some x is possible. I know the best ans so far is x and I look in the interval [x+1, hi]. Makes sense. So once this is clear the problem becomes how to check if it is possible to get some value. Right?

YES

when the problem is about minimum or maximum, it is pretty common to use binary search.

Yup also dp and greedy can be option too

It's a feeling, a hunch. At first you digest the problem and then you start bruteforcing different techniques in you head.

This is basically what's going on inside of my head

you make it clear xD. Going by exclusion also brings you there

I thought about bruteforce and dp but didn't able to think in a bs way.

can someone tell me why i got FST on E1? 217343471

my approach: I calculated the subtree size for each node. then for every node, stored the subtree sizes of its child nodes in an array. then did a dp to partition the array in 2 sets such that the difference of their sum is minimized. and then added their product with answer.

upd: got ac after making the graph directed :')

Does 11k+ submission of B justified ??

What do you mean?

I think it was pretty good idea and I don't think that much number of submission is justified

I am gonna get downvoted, but I also find it suspicious that everybody was able to find the idea. I have seen way easier Bs with less subs.

You can't just say that

"I have seen way easier Bs with less subs.". You aren't measuring objective difficulty here. You're measuring how you felt about the problems. You have seen Div2B's whych were easier for you but harder for most people. This time the problem was easier for most people (many probably guessed the amswer), but harder for you.This is actually a thing that happens to everyone. I remember two recent contests and their Div2E's (both were 2400 rated problems): I was able to solve one in about 15 minutes, while I couldn't get the other one even after 90 minutes.

Please help me, i'm unable to understand what's wrong with my code. When i'm running it on my laptop's Visual studio code it's working fine and giving the expected results as in the output but when submitted as answer then it says

wrong answer on pretest 1.Here is my code for Problem A of Contest 890 (Div 2):

Got it! I just saw that i have put

`ios::sync_with_stdio(false); cin.tie(nullptr);`

in the while loop by mistake which is not its right place.You can compare your solution with that of mine.

After getting FST on problem D, I dropped from rank 3 to rank ~200. I am not surprised because in each recursion I ask three queries (r-l)*(r-l). If my code did not pass the pretests, I would come up with the solution.

And I think the score division in problem E is not suitable.

Sorry for my bad English!

Could anyone help me out with C Submission

Take a look at Ticket 17030 from

CF Stressfor a counter example.Thanks figured it out, i had to update the whole array

j

I hope rating changes will update before i get to sleep.IKR

My FSTed solution for E2 involves heuristics to solve the simplified problem "partitioning the given set of positive integers $$${a_1,a_2,\cdots,a_k}$$$ into two, so that the difference between the smaller sum and $$$\frac{\sum a_i}{2}$$$ is minimized." Specifically:

I am curious about how to construct strong tests for such heuristics. Any ideas on constructing them?

If you have subtree of size $$$1$$$, gcd always be $$$1$$$, so you claim that you can always make exactly $$$\frac{\sum{a_i}}{2}$$$. Just make any test with large $$$k$$$, where it can't be achieved.

Actually, my intention is to ask for the ideas behind the construction, not just the test makes my solution fail.

But I have also come up with one idea: For example, if the set of numbers are $$$1,3$$$ and $$$g$$$ repeated $$$2k'$$$ times ($$$g$$$ and $$$k'$$$ are ome sufficiently large integers), then the $$$\gcd$$$ of them is $$$1$$$, but it is impossible to select a subset with sum $$$\frac{\sum a_i}{2}$$$.

I have never realized that the construction can be that easy :(, thanks for your reply.

nice round, specially the statements are. short and clear

Really that many people found B2 solution that easily???!! I guess I need to improve my intuition.

Well it's kinda constructive problem, you should approach them a little bit differently from others

SpoilerI'd like to report probably a system issue.Vladithur MikeMirzayanov. During the contest i submitted my solution to e2 and it got rte on test 17. I had 20 minutes to debug it but i didn't manage to do it in time. Surprisingly after contest it appeared that the reason for rte was probably stack overflow because of dfs recursion. (i changed in ac submission after contest only recursion to iteration and it easily got ac). Therefore here are 2 questions:

Here is my 1st submission to e2 which got rte: https://codeforces.com/contest/1856/submission/217343160 Here is my submission to e2 after contest which got ac https://codeforces.com/contest/1856/submission/217365641

According to this blog about compiler options, stack for C++ is limited to 256 mb.

I see. However that blog was 13 years ago so there could be some updates. Moreover, my complaint is also that the verdict imo should be mle not rte in this case.

Command lines have not undergone significant changes. For example, for gcc11-64-winlibs-g++20, the command line looks like this:

`g++.exe -Wall -Wextra -Wconversion -static -DONLINE_JUDGE -Wl,--stack=268435456 -O2 -std=c++20 -o %name%.exe *.cpp`

.I think the verdict of RE is more appropriate. The process in the operating system terminated with an error, and that's what RE is. It's a different situation from trying to allocate more memory and reaching the ML.

Rating update when?

Why not set stack size to be equal to max memory limit for any problem?

Video Editorial for problems A,B,C,D and E1;

https://youtu.be/jxLu6DMDV7o

Hope to become cyan!congrat you're cyan

Is this ratings without cheaters or what? MikeMirzayanov

Let's go I'm master now!

congrats

Best Div2 A is easy to read and B is easy to read too

I really want to say that bitset is a way to optimize your code, and it really can be used in races for answers.

https://codeforces.com/contest/1856/submission/217389353 can anyone tell me why i am wrong in this submission ? thank you !

Take a look at Ticket 17029 from

CF Stressfor a counter example.Thank you so much !!! Hope you get the best luck in your life :3

One of the tag in problem C is Dp. has anyone solved problem C using DP ? if yes then please share the approach of DP.

I enjoyed this game, its concise problem description made me feel comfortable.

Thanks for the round, pE2 was really interesting!

https://codeforces.com/contest/1856/submission/217324302

10

8 1 11 1 2 1 1 1 1 1

total sum of this array is28

so we can make another array like this

2 2 2 2 10 2 2 2 2 2

so why this case ans is no?

Your Answer is wrong for Test 2.. 3rd one.. which is

Thanks for contest!A little late,but contest was great!

https://codeforces.com/contest/1856/submission/217873662 Could someone tell me what I am doing wrong?

Take a look at Ticket 17043 from

CF Stressfor a counter example.hey i got a warning mail from codeforces that "Your solution 217270813 for the problem 1856A significantly coincides with someone else...." as it was a basic implementation based question and i used the variable names as common so it might be a coincidence and i used ideone compiler so i dont know if due to that this happed. please look into it.

hey i got a warning mail from codeforces that "Your solution 217337076 for the problem 1856C significantly coincides with someone else...." as it was a basic implementation based question and i used the variable names as common so it might be a coincidence and i used ideone compiler so i dont know if due to that this happed. I did not share my code to anyone. This is second time i got a warning without any copying or cheating. I belive in fair play. Please look into it.