Halo, **Codeforces**! 🥰🥰🥰🥰

COMPFEST 14 is happy to invite you to participate in Codeforces Round 831 (Div. 1 + Div. 2) on Oct/29/2022 12:10 (Moscow time). **Note the unusual time of the round**. The round will be **rated for everyone**. You will be given **2 hours and 45 minutes** to solve **9 problems**.

The problems are written by NeoZap, Nyse, Pyqe, and steven.novaryo.

Scoring distribution: **500 — 1000 — 1500 — 1750 — 2000 — 2500 — 2750 — 3000 — 3500**

We would like to thank:

- KAN for helping to host the round;
- errorgorn for the based coordination and help with the problem preparation;
- nyab for helping with the problem preparation;
- MikeMirzayanov, geranazavr555 and KAN for writing the Russian translations;
- Aaeria, AMnu, dorijanlendvaj, eggag32, feecIe6418, fishy15, flamestorm, Gary2005, gisp_zjz, gyh20, MagentaCobra, mejiamejia, oleh1421, powergee101, ppavic, prabowo, fantasy, tibinyte, tzc_wk, Wailydest for testing the contest and providing us very useful feedback;
- Universitas Indonesia, all the local committees, administrators, and managers of the whole COMPFEST event;
- rama_pang for drinking milk;
- MikeMirzayanov for the amazing Codeforces and Polygon platform!

COMPFEST itself is an annual event hosted by Universitas Indonesia. It is the largest student-run IT event in Indonesia and competitive programming contest is one of the competitions hosted.

We hope you will enjoy and have fun in the contest. Semoga beruntung dan selamat bersenang-senang!! 💪💪🔥🔥

**Edit:** round was delayed by 5 mins due to delays of onsite contest.

**UPD**: contest is over!

Congratulations to our winners!

We will try to post the editorials as soon as possible. Please stay tuned!

**UPD 2** : Editorial

We are very sorry for the late editorial. We did not anticipate the workload of maintaining an onsite contest, especially since this is the first onsite contest held by our university in three years. We will use this experience to learn and improve our preparation next time.

Finally, we are delighted that the contest ran very well and that many of the contestants are enjoying the contest.

See you next year! 🥰🥰

minum susu gaming

minum susu gaming

minum susu gaming

What was the milk like?

minum susu gaming

minum susu gaming

minum susu gaming

minum susu gaming

minum susu gaming

minum susu gaming

Тян бы

minum susu gaming

for drinking milk

minum susu gaming

minum susu gaming

minum susu gaming

minum susu gaming

minum susu gaming

minum susu gaming

minum susu gaming

minum susu gaming

What is minum susu gaming?

do you understand minum susu gaming when you don't live in the world of minum susu gaming

(yes me neither)

Just asking what is that?

drinking milk game

Thanks I was not aware of that.

https://www.youtube.com/channel/UCr9KnB-CRPYR0x9FjarTRaA

what

minum susu gaming

Is it first time

2 hours and 45 minuteslong contest?No, of course.

Definitely no

Very excited to participate

agree

very excited to wake up at 5 AM for this wonderful contest!

Note unusual timing

Yea.. Two times in a row now

As a tester, this is the first div1 of errorgorn as the coordinator.orzorzorz.

Seems that the contest coincides with CSP (an important contest in China in which almost all high-school students doing OI have to participate). Many Chinese participants aren't able to participate in this contest ... /sad

Is a rescheduling possible?

I know about it already. But this contest is based on COMPFEST 14, the only possible way to avoid the conflict is to reschedule it after ABC (clashing with ABC would have more complaints), but by then the contestants of the onsite contest would have gone home and would have access to internet which is obviously not ideal.

Therefore, it is impossible to reschedule due to these constraints.

I would rather let it clash with ABC.

Unusual time.

What does

`rama_pang for drinking milk;`

mean?I think your answer should be in contest problems.

i think it means rama_pang drank milk (cmiiw)

As a tester, problems are good and I recommend participating

However, the contest time conflicts with csp-2022 senior. Please change another time!

Note unusual timingEvery Codeforces user can relate with thisNote the unusual time of the round.

I hope that problem statements should be short as there are 9 problems, so one can go through it easily

Hoping your wish comes true.

As it will be my first contest,I hope i can solve 1 or 2 questions.

Good luck!

Yay! I can't wait to participate in this mirror contest! I didn't manage to get into the finals of the official COMPFEST 14, but I'm glad I can join this rated mirror contest!

hoping to solve at least two problems.

As a tester, I think the problems are very interesting, and I hope you enjoy them too!

As a tester, I hope you all enjoy the problems and get positive deltas!

And also,

Note the unusual time again.It will be2 hours and 45 minutesto solve them!excited to participate:)

It's a pity that I can't participate in this contest because I participated in CSP-S, but I will definitely come to look the problems after the contest.

And I am looking forward to the problems of this contest, hoping to surprise me.

minum susu gaming

nice emojii ..!

WoW! A lengthy contest（＾ω＾）

Keren

Hello authors , this is a unusual time for starting contest. I am a student. i have a class schedule of which is 9am to 4pm in Bangladesh. for this reason , I can not participate the contest which is started in unusual time. I requested to the Authentication of Codeforces , if every contest is start from at 8pm, it will help to improve and participate of every contest. Thank You.

Unusual time, this time.

wow 9 problems and 2 hours and 45 minute. This is first time for me

...

what is drinking milk??

Good Luck!!

Postponed by 5min

why?

Everytime this happens my adrenal glands are confused. That can't be healthy for them... :(

delays 5 min to drink milk...Is it just me or site is crashing for everyone?

Same, m2.codeforces.com is working fine

Is late registration available for this contest?

C is way more difficult than D and E

is it??

damn..i feel proud...that i solved c...and depressed that i couldnt solved d and e

Fast forces :(

Anyone know what is pretest 6 in E? This contest is so much WA-in-pretests...

I had multiple different brain-fade solutions in E, and each of them gave WA 6, so likely it's just a normal case catching many of those WAs. The correct solution is to take the max height you can, or allow your children to take the max height they can, and so on.

Example: if you have a tree

the answer is $$$7$$$, because you can assign

$$$a = [8, 5, 4, 9, 3, 2, 1, 7, 6]$$$ and remove them in the order $$$[7, 6, 5, 4, 3, 2, 9, 8, 1]$$$.

Oh my god that's literally an one-sentence answer that I've been trying to come up for almost two hours! Thank you! I've got to the part where I thought of the "depth or width" stuff, but I didn't find the general formula for it.

Thanks for the round! All problems up to G are pretty nice (haven't read further).

got back to specialist!!

Thanks for the great round! How to solve F?

How to do E ?

Since you can only remove leaf node, consider the vertices in topo-sorted order. You have two option: 1. continue the sequence from some child. 2. End the sequence here.

You can solve it with some kind of tree DP. At each vertex, you decide if you want to go further up the branch and if you want to stop at the vertex and merge the longest branches of the child nodes.

The explanation seems a bit abstract, so I upload 178381518 together.

Solution for E:

Let $$$dp[i]$$$ be the answer to subtree i.

Consider in two cases：

Case 1:node i is not in the answer.In this case,we can easily get:$$$dp[i]=\Sigma dp[j]$$$,$$$j$$$ is son of $$$i$$$.

Case 2:node i is in the answer.Through observation, the answer must be a chain.

In general,$$$dp[i]=max(\Sigma dp[j],depth[i]-max(depth[k])+1)$$$,$$$j$$$ is son of $$$i$$$,$$$k$$$ is descendant of $$$i$$$.

Can you please elaborate, maybe some proof or insights?

How does you get $$$dp[i] =\Sigma dp[j]$$$ in the first case and why the answer in the second case is the chain?

Case1:

You only need to prove the following process is the optimal:first,take all the nodes of subtree $$$son[i][1]$$$.Then,take all the nodes of subtree $$$son[i][2],son[i][3],...$$$

Hint:use proof by contradiction.

Case2:

You need to notice:

In the sequence,the position of node $$$i$$$ is always greater than its descendants.

In the sequence,the value of node $$$i$$$ is always

notgreater than its descendants.So if node $$$i$$$ is in the answer,all numbers in the subsequence must be equal,which must be a chain.

You are so sexist. How can you call it son and not a daughter?

how are we deciding the permutation array a?

Bro did you get how it's chosen ?

Why isn't answer for the first case Not

6?for each node calculate (a, b) where a is LIS endint at this node and b is LIS not ending at this node (considering this node's subtree)

transition for a is max of childrens' a +1

transition for b is sum of all childrens'(max of a or b)

Consider painting each node with black or white.

If you paint node $$$x$$$ with black, then its score will be the maximum point among its children plus $$$1$$$.

If you paint node $$$x$$$ with white, then its score will be the sum of all its children.

The answer will be

`max(black(1), white(1))`

.how to solve problem C??

i want to waiting a genius to help me to solve the C

Use this test case:

Expected output: 36

36 still , got WA :'(

You are not considering placing small in middle

Expected output: 34

Your output: 29

ahh , yes , thats it :( what is the approach actually ?

got it only considered higheset ones in middele , but shold have considered lowest ones also , so dumb I am :)

Why is my logic failing in the latest submission if you can tell?

could you give the configuration in which 36 is the ans.(the best I can think of is 39)

Video Solution for Problem C

Hint:Assuming the array is sorted, in an optimal configuration you just need to break the array into 3 contiguous segments.

Thanks!

do you do dp for E? I can't figure out the transition in time ;-;

Yeap, dp[i] = max(depth[i], sum_of_all(dp[children])

yes, transitions are pretty simple

dp(i, 1) = max(dp(u, 1) + 1), over all child u if i

dp(i, 0) += max(dp(u, 1), dp(u, 0) for all child u of i

i, 1 -> if we include i as next next element of longest subsequence

i, 0 -> if we exclude i and only take its children in longest common subsequence

base case is as following dp[leaves][0] = 0

dp[leaves][1] = 1

thanks! i had the same approach but the excluded one seems a bit counter-intuitive for me

I just thought it would be helpful to think this way but at the end dp(i, 1) just came out to be height of every node, still thinking which element I am putting on the back to increase length of longest nod-dec subsequence helped me visualize the solution better

Pak Chanek I hate this name.

How to solve B?

It's optimal to always place the block so that it's height is bigger or equal than width .

Now placing the blocks in asc/desc order will be enough.

How did you prove this? I proved it, but I doubt so many people would be able to prove it the way I did it. Maybe there is an easier way... or they just proved by AC

Proof by picture:

You want to maximise the green lines. So you place the blocks vertically. The length of the red and the blue line is the same. Not sorting the blocks will lead to blue being longer than red. A shorter length is not possible, by nature of $$$max(height_i)$$$ and $$$\sum width_i$$$.

Nice. I guess this part would probably be obvious to all. In such an arrangement, the answer = max_height * sum_of_widths.

What I found difficult to prove was why can't I rotate the longest (by height) block so that the max_height gets reduced, and hopefully the increase in total_width would by such that we end up with a better answer. Of course after rotation, the last block would conveniently be placed in between so that the blocks remain sorted by height.

Again, I proved this algebraically but I believe there should be an easier proof.

You don't need to sort the last block after laying it flat. Actually the blocks need not to be sorted. Having a highest block and the sizes to the left and the right of it non-increasing is sufficient. With this you can also proof your case of rotation simply by picture.

Bottom edge will have to touch the x axis that means in x axis by the time you insert a rectangle it will be added to the width so we will have to minimise the width so that perimeter becomes minimise.

178390392 Could someone provide test for this?

Take a look at Ticket 16381 from

CF Stressfor a counter example.Is it suggested to use these type of things in contest

It doesn't work during contests.

And yes, if you feel that you're bad at implementation, you can stress test locally during a contest by writing your own generator and brute force solution. But, it requires more time commitment and patience, so your mileage might vary

Rotate blocks in such a way that width of block be minimum. Then place them in ascending order of their hight and calculate perimeter.

what's your approach for D?

Figuring out minimum number of cells without a card needed to carry a card from cell (1,1) to cell (n,m)

Exactly, but I thought It would be (n + m — 3), After the contest, I realized only 2 were enough. Thanks for your comment. It helped me to rethink my solution!

thanks bro. this comment was much helful for me .

Huinea

In F if we define with $$$M$$$ maximum frequence of some value in array and with $$$D$$$ number of distinct elements in array.

Is it correct to claim that all multisets with at least $$$M$$$ elements, and none of them larger than $$$D$$$ are valid?

And if yes, how to code it in less than O(N^3)?

No. Consider frequency array of original one is [3,1,1,3]. M=3, D=4. But we cant make sizes of sets to be [4,3,1].

Thanks :)

Is this approach for F correct — Count all partitions such that largest size is less than or equal to number of distinct numbers and number of partitions is >= maximum occurrences of a number.

Wrong.

I liked sample test cases, they were pretty good : )

This was a nice round! A-D felt really logical and required very little to none background knowledge. Was already tired and satisfied so did not really give too much into E but seems like a cool problem as well. Will try to solve later.

Solution for E:

Let $$$dp[i]$$$ be the answer to subtree i.

Consider in two cases：

Case 1:node i is not in the answer.In this case,we can easily get:$$$dp[i]=\Sigma dp[j]$$$,$$$j$$$ is son of $$$i$$$.

Case 2:node i is in the answer.Through observation, the answer must be a chain.

In general,$$$dp[i]=max(\Sigma dp[j],depth[i]-max(depth[k])+1)$$$,$$$j$$$ is son of $$$i$$$,$$$k$$$ is descendant of $$$i$$$.

Disgusting time limit in B

Python just can't handle reading so many lines without magic with acceleration

Just don't code in python)

Probably this counts as "magic with acceleration", but after getting TLE a couple of times with Python because of slow input (in earlier contests), I found that adding

as the first two lines of the code helps a lot. You just add these two lines, no other changes required

for inputting integers. With this I passed B in Python in 233 ms. I now have these lines standard in my Python template.Note that when inputting a string, you now need to do

`input().decode()`

instead of just`input()`

.What I actually cannot understand is that I first submitted with PyPy 3 64-bit and I got TLE. Then I decided to rewrite in C++. But after contest I submitted exactly the same code with Python 3 instead of PyPy and it ran in 500ms. I always thought PyPy should be faster.

There are some blogs on Codeforces which discuss this in detail, search for "pypy vs python". Summary: for Python 3, actually Python is faster for input than PyPy. However, for some structures such as sets and dictionaries, PyPy is faster. So maybe it would work to submit on Python if you expect that the input takes the longest, and on PyPy if you expect the algorithm takes the longest.

Anybody with Problem C approach is it greedy or dp

Not dp

What's the idea for this

we can always get > max — min by taking min in 2 sets, max in 3, the rest in 1. So it is impossible for elements 1 < 2 < 3 to exist, otherwise taking these three we get less than we could. So all elements of 2 are a prefix or suffix. Then think a little about how best to distribute the remaining ones and iterate over the length of the prefix/suffix

what is the key observation of C?

Suppose you have an array a of 3 elements 1,3,5. How you should rearrange these elements so that abs(a[0] — a[1]) + abs(a[1] — a[2]) becomes maximize?

Sorry I dont quite understand. I will make 1,5,3 but how it helps?

Yes This is the intuition. Suppose array a is now 1,3,4,5. So your plan is to re arrange it like 1,5,3 as it gives the best answer but you have to put 4 also on the bag but in which bag you should put it?? Obviously on middle bag, otherwise if we arrange it like (1,4) (5) (3). Then the person will choose 4,5,3 which will not give the best answer so we will arrange like (1),(5,4) (3) so best answer is (1-4) + (4-3).

Now we will always look for a maximum element and two minimum elements or one minimum and two maximum elements. Why is that? Suppose a minimum element is min and a maximum element is max abs(max-min) will give better answer than (max-(min+1)).

consider array: 1 2 10 12

if you put 1 in bag 2 alone, the best answer is |1-2|+|1-12|. you see you can always subtract the number you want (in this case is 1) from the biggest number in the array (in this case it's 12) but the problem is nuber 2 because you can't get rid of it if you have chosen 1.

but if you put 1 and 2 in bag 2, now you have the value |2-10|+|2-12| which is much better. so the answer is max(|a[i+1]-a[i]|+|a[n]-a[i]|) for all i.

and you need to consider the case when the pivot is the biggest so max(|a[i]-a[i-1]|+|a[i]-a[1]|

I hope you got it now.

Why do we always take a consecutive segment from the largest/smallest element for bag2 ?

so, it's important! first we make estimation of what value we can achieve. It's this: $$$>=$$$ than mx_el_of_a $$$-$$$ mn_el_of_a. Now, You Don't Give bags with stones to MINImizer-guy such that there exists w_from_bag1 $$$<=$$$ w_from_bag2 $$$<=$$$ w_from_bag2. I repeat DO NOT GIVE bags with such configuration of stones. There is no point in giving bags with such configuration of stones: you (maximizer-guy) can do not worse, already. Therefore bag2 is a prefix or a suffix. // this explanation was read by me from hacker:great_fortune, but he hasn't got your upvote, so I concluded to unravel a bit more. Was not able to come up with a solution for hours and hours. but. next time maxmin-problem will be percieved easier by me, alternative is not an option

Amazing problemset, big thanks to authors! G just blew my mind. F is also very nice, and H is one of the coolest data structure problems I have seen in a long time.

I found COMPFEST problems to be nice every time , there was a compfest round (unrated) few months ago, that had great problems too

Really good problemset, I especially liked problem D, however I think problem E was easy for its position.

Thanks to the round!

All problems were really good, but WA on pretest 2 for C was quite annoying.

me(planning how can I quickly do problems so I could finally reach expert) Problem C: I am going to ruin this man's whole career

pretty nice set! (just E to F gap was really high)

H is standard dp on hld problem, refer to joi 2018 catdog

How to solve F?

There used to be this scale, back in the days when I was smol. Something finally coming useful from childhood.

Helps in solving DNostalgic! (◦'⌣'◦)/

I also thought of this same scale when solving problem D lol.

Really liked

`Problem D`

. Nice one.In problem D How does Case like gives no answer ?

2 2 4

3 4 2 1

my sequence of moves is just

move 3 to cell (1 , 2)

move 4 to cell (2 , 1)

move 4 to cell (2 , 2)

move 3 to cell (2 , 2)

move 2 to (1 , 2) and then to (2 , 2) and doing the same for 1 isn't that valid ?

The statement says $$$3\le n,m$$$, so this kind of case doesn't exist.

ok but why in most of the solutions they keep 4 cells empty and the just consider moving the card onto n * m — 4 cells

why 4 , in my solution (Wrong one) i thought i can move cards onto any free cell if it exists or to some other cell that has its top card greater than the current card by 1

Because if we keep $$$4$$$ cells empty we can move a new card to anywhere we want, so it's only nessesary to verify whether there's enough empty cells or not.

And we can't put two cards on one cells at the same time. I guess this is the mistake of your approach.

If you want to move a card from (1,1) then it is necessary to have 2 empty cells except (1,1) and (n,m). and if you want to move your card which is not on (1,1) it is necessary to have 1 empty cell except (1,1) and (n,m).

TLX teams always provide amazing problems!

Personally, My favorite point is that the samples have less information than usual.

I like F the best, even $$$O(n^3)$$$ (or slower) is cool and the speedup is also interesting!

By the way, when I read problem E, I went to reading the sample explanation (because I accidentally confused myself thinking that we remax instead of remin), and then I just coded the solution without proving it (well, I kinda convinced myself that it is intuitively obvious, but point stands)

what is the speedup from N^3?

Hi, I'd like to share my code, maybe you'll find it helpful :D

178435674 $$$O(n^2 \log n)$$$

As I know there also exists $$$O(n^{5/2})$$$ solution, could someone share it?

Thanks! that cleared it up for me

Can you explain your solution, please?

I submitted a solution for problem E in python using dfs and was getting runtime error on test 3, after some investigation got to know that it was giving recursion limit error in a normal dfs of 10^5 nodes. Below is my code to it, if anyone can explain me how to solve this using recursion then it would be great.

Thanks

Problem : 1740E - Hanging Hearts

Solution : 178403205

I'm lazy to provide an actual code but one possible solution is using threads. You can set an increased default stack size when you make a new thread.

Why result is 63 in testcase2 of propblem C ???

`Bag 1`

-> 8`Bag 2`

-> 45`Bag 3`

-> 17, 19Max Possible score = |45-8| + |45-19| = 63

thanks, it seems my brain is overloaded during that time

w2 as 45 and w1 8 and w2 19

Impressive gap between E and F.

https://codeforces.com/blog/_twink123121

Guys can someone pls explain problem E (hanging hearts) to me pls? I have read many of the solutions but have understood none of them. Also I am very salty because I only solved problem D after the contest after I realised that I added an extra "+1" for no reason that gave me WA.

Can someone provide a testcase for this? 178391526

1

3 3 6

1 2 3 4 5 6

this case must give "YA".

I think this is the worst case in the problem.

Can you elaborate on how is this possible?

At start there are $$$7$$$ vacant cells $$$(3 \times 3 - 2 = 7)$$$

When $$$1,2,3,4,5$$$ are removed from the stack then there are $$$ 7 - 5 = 2$$$ vacant cells. But the minimum free cells required to move from $$$(1,1) \rightarrow (n,m)$$$ is equal to $$$3$$$ $$$[(n+m)-(1+1)-1 = n+m-3]$$$.

So how is this testcase giving YES?

UPD: Just realized I need only $$$2$$$ vacant cells to move one card from $$$(1,1) \rightarrow (n,m)$$$. Updated it in the program and got AC. Thanks!

I was just glancing at problem I because I was late but still wanted to read the problems. The problem seemed interesting, and the (seemingly obvious?) properties I observed is that the answer is $$$-1$$$ when we cannot construct $$$S \bmod m$$$ (The initial sum of all elements modulo $$$m$$$) with the format of $$$kt \bmod m$$$ ($$$t$$$ being any arbitrary integer), and otherwise the answer is never $$$-1$$$ (I may be wrong on the latter point). Then I thought there may be some invariant property conserved when we follow the optimal method. My expectation of the time complexity is $$$O(nm \log n)$$$ or a bit slower. For anyone who got their hands on problem I — what was your approach so far?

1

3 3 6

1 2 3 4 5 6

this case must give "YA".

I think this is the worst case in the problem.

I meant problem I (the last problem of the set), not problem D.

sorry!

it was for the comment above your comment.

I didn't have time to think about the problem, but there is a stronger condition that is maintained: let $$$g = \mathrm{gcd}(n, k)$$$. Let $$$S_i$$$ be the sum of all elements with indices equal to $$$i$$$ modulo $$$g$$$. Then all $$$S_i$$$ are increased or decreased by $$$k/g$$$ after every move, and hence these sums must have the same remainder modulo $$$m$$$, and this remainder must be divisible by $$$\mathrm{gcd}(m, k/g)$$$. I have a feeling that this is probably sufficient

Well this is sufficient because we can first make all these sums equal to 0 by doing random increases, then we can transfer $$$1$$$ by $$$k$$$ positions in either direction using and increase and a decrease, therefore we can transfer $$$1$$$ by $$$g$$$ positions, hence we can transfer all nonzeros into one cell for each index remainder modulo $$$g$$$. Don't know anything about the optimality, though

Can someone give me a small testcase for which my

submissionwould fail? I'm not able to understand where I'm going wrong.Take a look at Ticket 16382 from

CF Stressfor a counter example.For problem C:

4

17 8 19 45

What I did was put the maximum in the first bag and the min in the second bag. Or put the min in the first and the max in the second. And take the maximum of them.

Bag 1={45}, Bag 2={8}, Bag 3={17,19} => Ans: 46

Bag 1={8}, Bag 2={45}, Bag 3={17,19} => Ans: 63

So the answer is 63. Can someone tell me where am I wrong?

you are right.

who said you are wrong?!!!

https://codeforces.com/contest/1740/submission/178348292

Wrong answer on pretest 2.

The answer is 15 (splitting it like [1] [9 10] [2]), your code outputs 10.

Can anyone tell what is the correct approach for #C? I can't figure out!

consider array: 1 2 10 12

if you put 1 in bag 2 alone, the best answer is |1-2|+|1-12|. you see you can always subtract the number you want (in this case is 1) from the biggest number in the array (in this case it's 12) but the problem is nuber 2 because you can't get rid of it if you have chosen 1.

but if you put 1 and 2 in bag 2, now you have the value |2-10|+|2-12| which is much better. so the answer is max(|a[i+1]-a[i]|+|a[n]-a[i]|) for all i.

and you need to consider the case when the pivot is the biggest so max(|a[i]-a[i-1]|+|a[i]-a[1]|

I hope you got it now.

thanks, now i got it accepted

Consider the sorted array. Since we have to distribute to 3 bags. We can always find 3 consecutive segments like below: ...(elements in w1)(elements in w3)( elements in w2)...

So, the second person, to minimize the result. No matter what values he choose, he has to choose them in consecutive segments. Otherwise, the result will increase.

We now greedy choose first segment [0]. And therefore, the second person will has only 1 choice is to choose last element in w3 and first element in w2.

Just draw it on paper, you will get my point.

Now, we also have another option is greedy choose last segment [n-1]. consider segment like ...(w2)(w3)(w1) (just reverse above) Also draw it on paper, you will see he has only 1 option : last element in w2 and first element in w3.

w2 has to be in rightmost or left most to maximize the result

thanks man!

Seems that there's a big gap between E and F

sry i thought F, G would be about 300 lower than they are

Could you please explain problem D ❤️

If the number of non-blank cell is lower than or equal to $$$n * m - 4$$$ (if don't have the rule 2(You cannot move a card onto cell $$$(1, 1)$$$) and 3(You cannot move a card from cell $$$(n, m)$$$), it will be $$$n * m - 2$$$), it can be proved that we can move any card on any cell to any cell without passing $$$(1, 1)$$$ and $$$(n, m)$$$.

If we don't follow rule 2 and 3 then number of non blank cells are n*m-2, but how we can reach the (n,m) from (1,1) by just 2 blank cells? They said we can move to adjacent cell(sharing same side). does that mean we can go to (n,1) from (1,1) as they share same side which is left boundary. and from (n,1) to (n,m) as they share same side which horizontal boundary?

It is because on a n * m grid where all cells filled except one, you can move any card from any where to any place you need by shifting or rotating the cards position to the empty space. So to move a card from (1, 1) to (n, m) you need two spaces before removing the card from (1, 1) and placing to the available spaces, then after that you will be left with one free cell and by rotating and shifting you can move the card to (n, m).

Hey, I tried solving problem E without using dp and it managed to pass all the tests but I'm not sure if it is the correct solution or not. If someone could hack it that would be great. If it is indeed right can someone prove why it works?. This what I came up with, instead of randomly going to a subtree of a node I visited the subtree with the deepest nodes first and assign values to a node when we have visited all nodes in its subtree. Then I just stored the subtree min in the same order and calculated the LNDS.

Thanks in advance.

178446226

E

You shouldn't have done that to your friend. Shame on you Hopefully MikeMirzayanov sees this and does the right thing.

Yes I know that's why I am apologizing and admitting my errors.

It's just your alt account isn't it? You can't fool anyone with this lame excuse

Why would I make a wrong submission from my main account and not from my alt. That's because there is no alt account thing going on here. I understand your scepticism but situation is exactly as I described

lol kid do you think we are fools out here?This is not your home or kindergarten school where you make fool of your parents and friends.The friend that you are talking about is actually your main account and things occurred like this according to my analysis skill:

1.You submitted D and got WA in your main account

2.Then you thought that ,"Let me just keep submitting in alt as long as I don't get AC and save point deduction from main account."

3.In the end you submitted the AC solution again but this time in your main account

I would ask MikeMirzayanov to skip solutions from both of your accounts

Like I said that's what it looks like but is really not. I think best would be to leave the decision to mike's judgement.

In the C problem, why was I getting it wrong can someone explain? I was talking about the lowest in one bag(including repeats), and the biggest in another bag(including repetitions).and the rest others in one bag, and then I was iterating with all the elements with the equation from that bag to get the min by thinking both a[0] and an [n-1] in the W1 bag and W2 bag. at last, I choose the max one from both of them. My submission

Take a look at Ticket 16387 from

CF Stressfor a counter example.Good website brother. Cant we see this without premium features?

The testcase that I shared should be visible without premium. But yes, to use the website for yourself, you will need to purchase a plan.

Consider the test case

1

4

1 12 88 100

Your code's output is 111.

You are considering this configuration as optimal:{1}, {100}, {12,88} =|100-1|+|100-88|=99+12=111.

But consider this configuration: {88},{1,12},{100}

Here

option1=|1-88|+|1-100| =87+99=186.

option2=|12-88|+|12-100|=76+88=164.

Therefore, the answer should be 164.

Thanks man.Much appreciated

Editorials please :)

Can any one explain to me why my solution to D fails? Here is my code

Contest is very good, Editorial please :-)

In Problem C, if we consider array [1,2,3,4,5,6] and put balls with weights 1 and 2 in bag2, balls with weights 3 and 4 in bag1 and balls with weights 5 and 6 in bag3 answer should be 12 but the correct answer is 6. Anyone please explain. Thanks.

Because in this case that person (the person who want to make you loose in problem D ) will chose 2 from bag 2, 3 from bag 1 and 5 from bag 3, so the result is 4.

one of the ways to the best answer is to put 1 in bag 2, 2 3 4 5 in bag 1 and 6 in bag 3.

Thanks. Didn't read question correctly.We have to take exactly one brick from each bag but I am taking as many as possible bricks from three bags.

SecondThread when is the screencast coming?

Probably tonight or tomorrow morning

26 more rank points to get back to IGM!

Can't wait!

Anyone can explain me problem 3 in detail please, I'm having a hard time understanding it

Can anyone explain me why I am getting Denial of Judgement verdict on problem D. submission https://codeforces.com/contest/1740/submission/178637268

Maybe the issue comes from Codeforces itself, not you.

Waiting for Editorial.

Can someone explain the thinking behind problem B? Would be of great help[problem:B]

The contest was really helpful to me, I really made a good knowledge of it.

Codeforces Language Picker -- chrome extension to fix codeforces language picker.

I received an announcement for this past contest 9 minutes ago. Anyone else?

Yep i did as well, it is probably because an update was made to the post (editorial is published)

The problems are good quality.It suprised me very much.I am looking forward to more contests!

You are given an array A of size N. For every element of the array, you can either increment it by 1 or keep it unchanged. For every element, you can do this operation at most once. For instance, if the element at ith index is c, you can either change it to e+ 1 or keep it c.

Determine the length of the longest subarray in which all the elements are equal by doing any such operations.

anyone pls help