Educational Codeforces Round 168 [Rated for Div. 2]

6 weeks ago, # ^ |

I don't have much experience, but I can say that only practice helps. It can be useful to review the problems and solutions of past competitions (but at the level you feel you can understand at the moment). My mistake was that I analyzed the solutions of the more difficult problems, although I could not solve the easier ones on my own. So I recommend solving gradually, it is better to solve an easier problem yourself than to understand or remember the solution of a harder one

→ Reply

6 weeks ago, # ^ |

Also at your level I recommend to pay more attention to past div 3 and div 4 contests, usually problems there easier than div 2

→ Reply

abinand0911

6 weeks ago, # ^ |

thanks for the insight I have been working on it and most of the times I do make the mistake of analysing past problems but some times I can get the most optimal intuition but unable to convert the logic to code

→ Reply

HERMES017

6 weeks ago, # |

Hope to reach grey.

→ Reply

dipanshu_115

6 weeks ago, # ^ |

I have faith in you :)

→ Reply

6 weeks ago, # |

Hope to reach cyan today

→ Reply

bkchodi

6 weeks ago, # ^ |

Spoiler

→ Reply

6 weeks ago, # ^ |

I prefer hard way :)

→ Reply

bkchodi

5 weeks ago, # ^ |

Congrations you are cyan now.

→ Reply

5 weeks ago, # ^ |

Thanks)

→ Reply

HERMES017

6 weeks ago, # ^ |

also D

→ Reply

6 weeks ago, # ^ |

Yeah, that was a good contest for me, I managed to do ABCD. Hope it won't get hacked

→ Reply

Forever1507

6 weeks ago, # |

Guys the waiting queue is really long(my last submission has already waited for 30 mins),will it be all right before the contest?

→ Reply

xinyu123_AKIOI

6 weeks ago, # |

Let me go back to Expert,CodeForces!

→ Reply

Vivek_Dubey

6 weeks ago, # |

Hope to reach....... Realising NO HOPE LEFT

→ Reply

JigSaW__

6 weeks ago, # |

Only 20 points :)

→ Reply

devansh_devu_gupta

6 weeks ago, # |

manifesting to reach blue today fingers crossed

→ Reply

hxano

6 weeks ago, # |

My first unrated Div. 2

→ Reply

shviv1

6 weeks ago, # ^ |

+12

You are lucky to get it unrated.

→ Reply

adi004

6 weeks ago, # |

Really hoping to learn more. Always been told I couldnt do cp

→ Reply

6 weeks ago, # |

← Rev. 3 →

the worst round ever. 4 update messages in 20 minutes.

→ Reply

LM0

6 weeks ago, # ^ |

+12

You updated your comment 3 times.

→ Reply

6 weeks ago, # ^ |

I haven't changed anything. only when the fourth came

→ Reply

6 weeks ago, # |

-46

What I'll miss is that in the first 20-30 minutes there were four updates to problem B's condition, but problem D is a nightmare. The problem writer has 0 creativity. It’s like I’m reading a study problem>. Worst round

→ Reply

alpha_6124

6 weeks ago, # ^ |

problem B seems much harder before updates

→ Reply

6 weeks ago, # ^ |

i mean, there should be no updates. the testers should fix this before the round

→ Reply

6 weeks ago, # ^ |

I agree that it is pretty classical but this is an Educational round.

→ Reply

ziad-abdou1

6 weeks ago, # ^ |

If problem D has 0 creativity , why you donot solve it

→ Reply

6 weeks ago, # ^ |

there is no connection here. the problem may not be creative, even if I haven’t solved it

→ Reply

6 weeks ago, # ^ |

I agree, I solved it and it is not creative at all.

→ Reply

devanshu16

6 weeks ago, # |

speedforces :'(

→ Reply

aviralarpan3301

6 weeks ago, # ^ |

← Rev. 2 →

+11

because of people like you, who copy paste ABCD as soon as they get them from telegram.

→ Reply

Dinh_Van_Tung

6 weeks ago, # ^ |

Y are a cheatforces

→ Reply

myaltaccountsthis

6 weeks ago, # |

ok so my code that used a Node class and new() TLEs but it runs in 50ms with n=200k on my system.

when i get rid of the Node class and use ints it runs slightly faster on my end but AC

whats the big deal with new() taking forever???

→ Reply

6 weeks ago, # ^ |

Use global variables, they are faster. Preallocate memory, rather than allocating runtime memory for better performance.

There are disadvantages also, you need to make sure, you are not allocating more than required, or you will get MLE.

→ Reply

donpaul2718

6 weeks ago, # |

12k did C? lol. cheatforces. These idiots are digging their own grave.

→ Reply

Cyclonestopper9000

6 weeks ago, # ^ |

← Rev. 2 →

so true lmao

more people solved C than B, despite B having a way easier algorithm

→ Reply

6 weeks ago, # ^ |

← Rev. 3 →

-12

Guess what, aryanc403 bhai has tried C-problem 4 times. He is quite experienced and knows most of the things in CP. If it takes him 4 tries then the problem must be little challenging. and yet 12k people solved it.

Definitely C is leaked. xD .

→ Reply

saikumarailwar9

6 weeks ago, # ^ |

Even D is leaked. In last 10 min D submissions increased from 3k to 5k. Looking weird:(

→ Reply

alpha_6124

6 weeks ago, # ^ |

C was quite easy as per aryanc403 he may have bad day

→ Reply

aryanc403

6 weeks ago, # ^ |

I have seen the intended solution.
I'm sure I will miss it, irrespective of what day it is and what time it is.
Not the kind of problem I'm good at.

→ Reply

HERMES017

6 weeks ago, # ^ |

C was easy compared with other Div 2s.

→ Reply

Roll_no_68

6 weeks ago, # ^ |

← Rev. 2 →

Exactly i was unable to solve B but did C in less than 10 minute, also got idea to solve D but was not able to write code :(

→ Reply

i_would_win

6 weeks ago, # ^ |

tbh if you figured out only condition where one region becomes 3 it was easiest to implement check out my submission for more details

→ Reply

Roll_no_68

6 weeks ago, # ^ |

Actually the problem was I didn't read the constraint properly which was stating, initially there will be at most 1 region.

→ Reply

i_would_win

6 weeks ago, # ^ |

ohh I was getting notifications again n again so I carefully read the problem

→ Reply

6 weeks ago, # ^ |

-6

c was literally valid parenthesis from leetcode. It is one of the foundational problems for stacks. I think 12k submission is not justified. But it should be higher than usual div2 c. I solved it using rust as I am learning it.

→ Reply

ibrahimwq

6 weeks ago, # ^ |

C is not just valid parenthesis lol

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

I just built a valid parenthesis and summed it up and got accepted. What is so hard about it ? And the cheaters gonna get skipped anyway. So I don't think it doesn't matter.

→ Reply

ibrahimwq

6 weeks ago, # ^ |

+13

well, u just answered to urself. You didn't prove why it will be minimum cost, and just guessed.

→ Reply

nsudhir

6 weeks ago, # ^ |

I think we have to close the open bracket as soon as possible then only we can get minimum cost.

→ Reply

Krishna.1

6 weeks ago, # ^ |

Bro can you prove why there exists only one solution.

→ Reply

dream7

6 weeks ago, # ^ |

← Rev. 2 →

It wasn't valid parenthesis problem, this problem's solution had some objective (greedy) and constraints, which is totally diff.

→ Reply

swastiksethi03

6 weeks ago, # ^ |

-6

Yes it was, you just need to observer when the cost is minimum and fill the blanks accordingly.

→ Reply

nguyenkhangninh99

6 weeks ago, # ^ |

agree, such cheater ruined codeforces

→ Reply

6 weeks ago, # |

is this rated for GMs , LGMs, IMs??

→ Reply

Cyclonestopper9000

6 weeks ago, # ^ |

no, only for people with rating less than 2100

→ Reply

6 weeks ago, # ^ |

then why are they in official standings ?

→ Reply

6 weeks ago, # ^ |

They are, but after system testing you will be able to see the standings for Div. 1 and Div. 2 separately.

→ Reply

6 weeks ago, # ^ |

ohh cool :)

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

no bro, only till 2099

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

Ok thx

→ Reply

Astroflexx

6 weeks ago, # |

-17

WTF ????????????? HOW NEWBIES AND PUPILS WITH < 150 PROBLEMS SOLVED ARE SOLVING D ????

5000 ACCEPTED ON D IN A DIV2 ROUND IS JUST INSANE.

→ Reply

6 weeks ago, # ^ |

Because it is very easy and classical, however I won't deny the presence of cheaters.

→ Reply

6 weeks ago, # ^ |

its standard problem, cheaters are there tho

→ Reply

tak_eshi

6 weeks ago, # ^ |

can you tell me about that standard problem

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

i mean say we are on node v with value a[v] and the smallest element from every subtree of v is mn, and then a bit of case handling, if (mn<= a[v]) we go on with mn as the minimum value for the subtree that includes v , else we return (a[v]) + (mn — a[v])/2 that is simply getting both the values to their centre point .

The idea is that dfs is returning the minimum element in the subtree of the node.

You can see this soln 273567246 and its standard cuz its the simplest of DFS

→ Reply

CM_This_Year

6 weeks ago, # ^ |

Why do we take values to their center? And how does taking to centre ensure that these values of subtree nodes will always be >=0 in the future.

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

so look i need to set the entire tree up in such a way that the minimum value in the subtree of 1 is maximized , excluding the value of node 1. Why? cuz if the minimum value is increased that means i can perform the operation on node 1, more times before the minimum value in subtree reaches 0.

For the "if" case, say i have a node with val 5, and it has 3 children with values 3,7,9 now i will simply return 3, why? cuz if i perform any operation on node with val 5, the val 3 will decrease thus decreasing the minimum.

For the "else" case, say i have a node with val 2 and it has 2 children with values say 7 and 9, so the min value of the subtree currently is 2, but we can make it better , as the minimum value of the child is 7, if i perform the operation twice the values will become 4, 5,7 . so i took them to their centre value. And more operations are clearly of no use as the minimum value that is currently 4 will start decreasing.

So the idea is MAXIMIZING the MINIMUM in every subtree, beginning from leaf nodes to root.

→ Reply

CM_This_Year

6 weeks ago, # ^ |

For the second case you can maximize the root to 11. And the tree after the operations becomes 11,0,2 Can you explain this else case again?

→ Reply

6 weeks ago, # ^ |

alright so in the second case, lets say x has value 2, and it has 2 children y and z with values with 7 and 9, and x is connected to node 1.

so the tree is like 1->x->(y,z)

so the DFS begins, for y it will return 7 and for z it will return 9. now for x the minimum value amongst it's subtrees,i.e. y and z, will be 7. But its own value is 2 which is lower than 7.

For better understanding , lets suppose we dont do any operations and simply return the minimum then we return 2. and now we are at node 1 , and the minimum element in all its children's subtrees is 2, so that means i can just increase the value of node 1 twice before one of the elements in the tree gets 0.

Now, suppose we did some operations on x, so minmum amongst it's child subtrees was 7 and it's value was 2, how many operations should i do, such that the minimum of the entire subtree is MAXIMIZED and not only the value of node x? i should do (7-2)/2 = 2 operations so value of x would become 4, value of y and z gets 5 and 7, so the minimum of the subtree gets 4 and i return it , this is the maximized minimum of the subtree. And now i can perform 4 operations on node 1 :).

Let's say what if i did more oerations on x ? say 2 more operations , x's value becomes 6, y and z become 3 and 5, now the minimum of the ENTIRE subtree is 3 , so that means i can only do 3 operations on node 1, which is not the best possibility , Thats why i take values to the center

→ Reply

shubhamjee

3 weeks ago, # ^ |

Great explanation! i did it in the same way

→ Reply

KindaGoodGames

6 weeks ago, # ^ |

IT is a pretty straight forward Tree DP Question. And not everybody learns mostly off codeforces, I just do codeforces for the contests, but rarely for Practice Purposes (except if they appear on USACO Guide)

But yeah, 5k on D is still quite a lot.

→ Reply

potatopop

6 weeks ago, # ^ |

if you don't mind what other resource are you using?

→ Reply

KindaGoodGames

6 weeks ago, # ^ |

I personally just do mostly USACO Guide. Doing Bronze to Silver and knowing some techniques from Gold should be enough in my opinion. Also it is very important to do the actual codeforces contests, since it does also help with general problem solving instead of just solving problems tied to specific topics

→ Reply

Roll_no_68

6 weeks ago, # ^ |

Tbh as a newbie i found D easier than other div2 rounds but sadly i was not able to write code

→ Reply

6 weeks ago, # |

+10

Does anyone else keep getting WA on test case 19 for problem D? Solving E and losing rating is tough :((

→ Reply

Astroflexx

6 weeks ago, # ^ |

Yes

→ Reply

dd_07

6 weeks ago, # ^ |

What is the exact tc?? I also faced the same :/

→ Reply

SXZZ5

6 weeks ago, # ^ |

← Rev. 2 →

YESSSSSS :( 273588603

→ Reply

LittleMoon

6 weeks ago, # ^ |

+22

In your code, val can grow exponentially. Keep a check, if it is greater that 1e9 return false.

→ Reply

6 weeks ago, # ^ |

You're right, thanks!

→ Reply

donovilia2007

6 weeks ago, # ^ |

If you passed the number Y to dfs, which must be subtracted from all the numbers in the subset, then Y may have become greater than 2^64

→ Reply

kesshb

6 weeks ago, # ^ |

Me too, no f... idea what's wrong in that case 19...

→ Reply

kesshb

6 weeks ago, # ^ |

Okay, got it now though, happy days, jeeez...

→ Reply

CCamelo19

6 weeks ago, # |

I tried problem E, Got the correct solution. Exceeded the time limit :(

→ Reply

6 weeks ago, # |

+10

Imagine looking for an overflow for 30+ mins while telling yourself the following code snippet "definitely isn't the cause, its bounded by $$$n \cdot max(a)$$$".

Code snippet

dfs(int x, int cost) {
    for(auto v : adj[x]) {
        if(!dfs(v, base_req + max(base_req - a[x], 0ll))) {

→ Reply

6 weeks ago, # ^ |

Wait this causes an overflow? :0 Can you explain why?

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

Consider a line graph with the following values of $$$a_i$$$

$$$1 \rightarrow 0 \rightarrow 0 \rightarrow 0 \rightarrow 0 \cdots$$$

Then if our starting "cost" (i.e., how much we want to add to the root) is $$$1$$$, then the corresponding values of cost for each node becomes:

$$$1 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \cdots$$$

So the value simply overflows for any such line graph of more than $$$32$$$ / $$$64$$$ nodes depending on whether you're using 32 or 64 bit ints.

→ Reply

6 weeks ago, # ^ |

Got it, thanks! So we just need a special check once the the value is greater than $$$10^9$$$

→ Reply

6 weeks ago, # |

The contest was really easy, the first 4 problems felt like Div. 3, and problem D was very classical.

→ Reply

devcode24

6 weeks ago, # |

-9

The B question is something! How are they able to make such tough problems! I bet even gpt cannot solve these problems

→ Reply

6 weeks ago, # ^ |

It was not that hard. You just have to find the free cell that serves as the only bridge to 3 free cells. You can look at my post contest submission to figure it out. I misread the problem statement and I thought there could be more than 1 sets. I solved it in that way in contest.

→ Reply

devcode24

6 weeks ago, # ^ |

← Rev. 4 →

Thank you! But after writing the comment I wrote, I was able to understand the problem.

→ Reply

tickbird

6 weeks ago, # |

couldn't solve D

I'm so retarded,

doing cf for year and still nowhere near blue

→ Reply

6 weeks ago, # ^ |

+21

It's ok it took me more than a year for expert

→ Reply

6 weeks ago, # ^ |

You are specialist so you are definitely not retarded. I looked at your profile and 70% of your solved problems are below 1400, so maybe practice harder problems.

→ Reply

attractors

5 weeks ago, # ^ |

his real account is madboly(I think I spelled it right)

→ Reply

ExpectoPatronum

6 weeks ago, # |

how to solve F, I tried many dp approaches but it didn't work.

→ Reply

toniskrijelj

6 weeks ago, # ^ |

+42

Note that tokens behave like fibonacci sequence, you have $$$f_1$$$ $$$f_2$$$ and can create some $$$f_i$$$ for $$$i>=3$$$ using $$$f_{i-1}$$$ and $$$f_{i-2}$$$ or to change $$$f_i$$$ for $$$f_{i-1}$$$ and $$$f_{i-2}$$$. You can also freely change $$$f_1$$$ to $$$f_2$$$ and vice versa. So $$$f_i$$$ means token on position $$$i$$$.

First convert all tokens to $$$f_1$$$ and $$$f_2$$$, let the number of them be $$$s$$$. Note that, because you can change $$$f_1$$$ to $$$f_2$$$ and vice versa, all that matter is their sum ($$$s$$$). You want to use minimum number of tokens to represent $$$s$$$. One token means some $$$f_i$$$. If you have $$$1000$$$ $$$f_{10}$$$ tokens maximum $$$s$$$ you can get is $$$55000$$$.

Now you do greedy, for every sum $$$s <= 55000$$$, you go through $$$f_{30}$$$ to $$$f_1$$$ and try to fit sum $$$s$$$ in minimum number of tokens (there is proof for fibonacci numbers that greedy is optimal).

Now for some sum $$$s$$$ you have $$$min[s]$$$ which represent minimum number of tokens to represent it. We want such $$$s$$$ that $$$min[s] = m$$$.

Lastly we need to calculate in how many ways can we get sum $$$s$$$ using $$$n$$$ tokens on first $$$x$$$ $$$f$$$s. Define $$$dp[i][sm][p]$$$ as in first $$$i$$$ $$$f$$$s you placed $$$p$$$ tokens and their sum is $$$sm$$$, this dp has at most $$$10*55000*1000$$$ states, transitions are in $$$O(1)$$$.

Now you just sum $$$dp[x][sm][n]$$$ such that $$$min[sm] = m$$$

273592555

→ Reply

n0sk1ll

6 weeks ago, # ^ |

This might also help.

→ Reply

6 weeks ago, # ^ |

i had about the same idea but the 10*55000*1000 dp sounds really scary to me

→ Reply

cmk666

6 weeks ago, # ^ |

+21

in fact, if you limit $$$sm$$$ to $$$n\cdot fib_i$$$ (instead of $$$n\cdot fib_x$$$), the total number of states is only $$$n^2\sum_{i=1}^x fib_i=1.43\times10^8$$$, so it runs really fast :D

→ Reply

6 weeks ago, # |

Man A screwed me

→ Reply

adarshrai24

6 weeks ago, # ^ |

really I thought A was really easy I just thought that chose the substring with longest repeating chars and just insert the different char than the present one in between of that substring

→ Reply

adarshrai24

6 weeks ago, # ^ |

← Rev. 2 →

now I realised that we don't need to find even longest substring though just find 2 repeating chars and insert the different char in between them. I am such a noob :(

→ Reply

6 weeks ago, # ^ |

It's ok I first understood that it requires minimum time and implemented a brute force solution and got wa1 and then sent another solution still wa1 and then realized it wanted maximum

→ Reply

6 weeks ago, # ^ |

lmao, xD thats tough

→ Reply

misaki646

6 weeks ago, # ^ |

I also WA in test1 2 times and chuckles. I know today im gonna screw up by not having enough time again

→ Reply

6 weeks ago, # ^ |

I was thinking why the time limit was 2 seconds. I literally did not make any sense.

→ Reply

6 weeks ago, # ^ |

it's just standard time limit in educational contests

→ Reply

aviralarpan3301

6 weeks ago, # |

someone please tell how to solve E

→ Reply

NekoYellow

6 weeks ago, # ^ |

+11

do it in different ways when $$$x \le \sqrt n$$$ and when $$$x \gt \sqrt n$$$. The former can be pre-calculated, while the latter can be solved by binary searching on prefix-sum

→ Reply

6 weeks ago, # ^ |

Wow I didn't think of that

→ Reply

123gjweq2

6 weeks ago, # ^ |

but what is the prefix sum?

→ Reply

NekoYellow

6 weeks ago, # ^ |

← Rev. 2 →

One observation is that, when $$$x \gt \sqrt n$$$, the level would never exceed $$$\sqrt n$$$. Then we can calculate prefix sum on the number of monsters having level $$$ \ge k$$$, for all $$$k$$$ s from 1 to $$$\sqrt n$$$ —- the monsters to encounter having level k

UPD: Sorry, got hack on this. The complexity is actually $$$O(q\sqrt n \log n)$$$, approximately 10x slower than $$$O(n \log^2 n)$$$ for $$$n = q = 2e5$$$, maybe not fast enough even for a time limit of 4s. One mending might be brute-force to $$$h = 2000$$$ instead of $$$\sqrt n$$$ (Than the overall complexity would be $$$O(hn + \frac{n}{h}q\log n)$$$ which is $$$\lt O(q\sqrt n \log n)$$$)

→ Reply

the_last_smilodon

6 weeks ago, # ^ |

I did exactly that and got TLE on testcase 63

→ Reply

6 weeks ago, # ^ |

You can precalculate an array of indices for each $$$k$$$, where the indices show where the last update of level happened. I did it with merge sort tree in $$$O(n \cdot log^3_2{n} + q \cdot log_2{n})$$$.

→ Reply

6 weeks ago, # ^ |

← Rev. 3 →

I did the same, but got TLE :(. The way I wrote seems like having large constant factor.

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

Spoiler

→ Reply

aviralarpan3301

6 weeks ago, # ^ |

NekoYellow .-__-. Abito thanks

→ Reply

alpha1215

6 weeks ago, # ^ |

i have an idea that we can group the queries by k
then for each can simulate the game by using segment tree in $$$O((n / k) log(n))$$$
so we can do this in $$$O(n * log^2(n))$$$
someone please correct me if i'm wrong.

→ Reply

6 weeks ago, # ^ |

← Rev. 5 →

+21

Notice that the level you can reach by the $$$i$$$-th monster is non-increasing as $$$k$$$ increases.

Let $$$need_i$$$ represent the minimum $$$k$$$ for which our level will be $$$\leq a_i$$$ when we reach the $$$i$$$-th monster.

We can binary search on the value of $$$need_i$$$. To check if $$$need_i \leq k$$$, we want to know if the number of monsters we would have fought till $$$i - 1$$$ is $$$\lt k \cdot a_i$$$, or formally $$$\text{cnt}(need_j \leq k$$$ where $$$j \lt i) \lt k \cdot a_i$$$.

To check this $$$cnt$$$ quickly iterate in increasing order of $$$i$$$ and store the values of $$$need_i$$$ in a fenwick tree, then $$$\text{cnt}(need_j \leq k$$$ where $$$j \lt i)$$$ is just $$$sum(k)$$$.

Code — 273568637

→ Reply

md_nihal

6 weeks ago, # ^ |

can you elaborate on how to find for each k i.e we want to know if the number of monsters we would have fought till i−1 is <k⋅ai, or formally cnt(needj≤k where j<i)<k⋅ai. can you explain this

→ Reply

Ankit_singh_sisodya

6 weeks ago, # ^ |

won't it be non-increasing??

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

Oops, yeah I accidentally reversed the meaning in my mind while writing this. Fixed it now.

→ Reply

toniskrijelj

6 weeks ago, # ^ |

Check my comment.

→ Reply

donovilia2007

6 weeks ago, # |

Bad round, seriously

→ Reply

6 weeks ago, # ^ |

for what reason? like the problems were easier than div 2?

→ Reply

donovilia2007

6 weeks ago, # ^ |

I think, problems were easier than hard div3

→ Reply

6 weeks ago, # ^ |

yeah maybe

→ Reply

AK_15

6 weeks ago, # ^ |

Go and solve E, F, if problems are easier than hard div 3 :)

→ Reply

mjj_

6 weeks ago, # ^ |

Questions A to D are easier than usual,but E and F are still challenging

→ Reply

https://codeforces.net/blog/entry/11080?#comment-946680

6 weeks ago, # ^ |

this is like the 2nd or 3rd contest where i spend an entire hour on D and swept E in 20 mins from start to end

→ Reply

kai-zen

6 weeks ago, # |

How do I approach problem D?

→ Reply

alpha1215

6 weeks ago, # ^ |

for each node u it is optimal to have $$$A[u] <= min(A[each \ node \ in \ subtree \ of \ u])$$$
then answer is just $$$A[1] + min(A[each \ node \ in \ subtree \ of \ 1])$$$

→ Reply

anupam_713

6 weeks ago, # ^ |

https://codeforces.net/blog/entry/132049?#comment-1177386 see my approach explained in this comment

→ Reply

red_one_fine_day

6 weeks ago, # |

What is the idea for E?

→ Reply

aqua4

6 weeks ago, # ^ |

← Rev. 2 →

→ Reply

red_one_fine_day

6 weeks ago, # ^ |

can you please explain

→ Reply

SpyrosAliv

6 weeks ago, # ^ |

← Rev. 4 →

+17

If a $$$k$$$ doesn't scare monster $$$i$$$, then all $$$k+1, k+2, ...$$$ won't scare it. Therefore you can binary search on $$$k$$$ and find how many monsters are also not scared with a segment tree (or Tree Order Statistics), thus finding the level you're going to be at at this index with a specified value $$$k$$$.

273560444

→ Reply

Hassouna_

6 weeks ago, # ^ |

I don't understand why we used a sum segment tree for this problem. If I want to determine whether a specific value $$$K$$$ can scare the fourth monster in the array $$${x, y, z, M}$$$, how does knowing the sum of $$$x$$$, $$$y$$$, and $$$z$$$ help me decide that? I think the ordering of the three numbers might differ. Sorry if I misunderstood the code.

→ Reply

SpyrosAliv

6 weeks ago, # ^ |

← Rev. 3 →

-8

We are not summing the values themselves, but we are rather calculating the amount of monsters at indices $$$1...i-1$$$ that would not be scared with a value $$$k$$$.

That can be calculated by storing the minimum $$$k$$$ we found for indices $$$1...i-1$$$ in another array $$$freq$$$, where $$$freq_j$$$ denotes how many monsters stay when $$$k = j$$$ but leave when $$$k < j$$$. We will then query for $$$\sum_{l=1}^{k} freq_l$$$.

→ Reply

aditya0610

6 weeks ago, # |

why my code failed for D ? link my solution

→ Reply

xiaoqie

6 weeks ago, # ^ |

← Rev. 2 →

May be return earlier when its impossible, long long int may not enough.

→ Reply

aditya0610

6 weeks ago, # ^ |

yes just added val = min(val,inf); it got ac link AC solution I wish I could have thought this in contest :(

→ Reply

aqua4

6 weeks ago, # |

← Rev. 2 →

Data structure to solve E: https://codeforces.net/blog/entry/11080?#comment-946680

→ Reply

Um_nik

6 weeks ago, # |

+26

Screencast with commentary

→ Reply

gabriel88766

6 weeks ago, # |

← Rev. 2 →

$$$O(NX + N^2/X\ log(N))$$$ should be enough to E? I chose $$$X = 1000$$$, and I saw in the worst case it would do like $$$9\times 10^8$$$ operations, and the code executed fast enough, 640ms.

First brute force up to 1000 (ordering queries), then the next I solved doing binary searches in prefix sum to each level up to 200, to find the point of each upgrade.

→ Reply

RecursiveCo

6 weeks ago, # ^ |

I think in E you can actually optimize the large $$$k$$$ case using harmonic sums so it becomes $$$O(n\sqrt{n}+nlog^2(n))$$$. i.e. for each level only iterate $$$k$$$ up to $$$\frac{n}{l}$$$ (or so).

→ Reply

toniskrijelj

6 weeks ago, # ^ |

+20

You can solve E in $$$O(nlog^2n)$$$, for each $$$i$$$ you can define $$$f(i,x)$$$ as 0 if $$$i$$$ runs for value $$$k=x$$$ or 1 if $$$i$$$ doesn't run for value $$$k=x$$$. See that $$$f$$$ is monotonic so you can binary search it. ($$$f(i,0)=0$$$ for all $$$i$$$ for implementation sake)

Go through all elements and binary search $$$x$$$ such that $$$f(i,x)=0$$$ and $$$f(i,x+1)=1$$$, in order for element $$$i$$$ to run for some $$$x$$$ there should be $$$a[i]*x$$$ elements that don't run on prefix. You can use ordered set, for calculating how many elements stay/run on prefix. Answering queries is straight forward just compare $$$ans[i]$$$ with $$$x$$$. 273562301

→ Reply

lookcook

6 weeks ago, # ^ |

I solved in your complexity. I TLEd under X=1000 and ACd with X=2000.

→ Reply

Hasan0540

6 weeks ago, # ^ |

It can be solved in $$$O((n+q)\sqrt n)$$$ without Binary Search if you maintain both prefix sums and lists of indices that need fight for each $$$k \leq \sqrt n$$$: 273605589.

I had to use $$$2\sqrt n$$$ for the brute force part to get the memory under 512MB :/

→ Reply

Erering

6 weeks ago, # |

Everyone is doing binary search for D while I did entry and exit times with lazy minimum segment tree lol

→ Reply

6 weeks ago, # ^ |

Hahahha what, I solved it with basic DFS

→ Reply

Erering

6 weeks ago, # ^ |

Yea I overcomplicated it so much I basically just took the minimum in the whole tree and if its a leaf then break otherwise i take the minimum in the minimums subtree (not including the minimum) and lets call that mn2 i increase minimum by (mn2-mn+1)/2 and decrease everything in its subtree by that. I keep repeating until the minimum is the leaf then i just increase root by the minimum in the whole tree other than the root.

→ Reply

6 weeks ago, # ^ |

I solved same way

→ Reply

wazz

6 weeks ago, # ^ |

Same but the segment tree not lazy ahaha

→ Reply

6 weeks ago, # ^ |

i ditched binary search because i kept getting WA with it lol

→ Reply

https://codeforces.net/contest/1997/submission/273568701

6 weeks ago, # ^ |

← Rev. 2 →

I got 4 times TLE with binary search. I seriously don't know, why

Log(2e9) * 2 * 10^5 gets TLE.

→ Reply

__NO__NAME__

6 weeks ago, # |

man...penalty sucks

→ Reply

JasamritRahala

6 weeks ago, # |

+10

As a pupil, I'm hoping to reach legendary grand master after this contest. Wish me luck!

→ Reply

synthborne

6 weeks ago, # |

Worst contest ever taken...

→ Reply

VISH9756

6 weeks ago, # |

B question was very poorly written i thought if i am not able to do b then how can i do C and further question , it took my whole contest time . Only because it wasnt mentioned clearly that in the starting only at most 1 region is given.

→ Reply

Submission 1 TLE Submission 2 MLE

6 weeks ago, # ^ |

It was mentioned under the second picture.

→ Reply

dryeab

6 weeks ago, # ^ |

I also didn't check the announcement and wasted a lot of time on B.

→ Reply

Erering

6 weeks ago, # ^ |

Same took 40 minutes solving B because of it

→ Reply

21Cash

6 weeks ago, # |

+22

who else got WA test 19 on D for binary searching ??

→ Reply

__tomato__

6 weeks ago, # |

one of the worst rounds I have ever done, especially B, I couldn't do it while I solved C in 5mins.

→ Reply

codesniper99

6 weeks ago, # |

← Rev. 5 →

Ignore

→ Reply

aayush249

6 weeks ago, # |

Lol I got cooked in a for starting the matching character check from 1 to n and not 0 to n.

→ Reply

mengxinzcl

6 weeks ago, # |

Why do I always RE on the D question?（Python）

→ Reply

Divyanshu52Singhal

6 weeks ago, # ^ |

u need to extend the recursion limit for that

→ Reply

mengxinzcl

6 weeks ago, # ^ |

I've used sys.setrecursionLimit(1000000)

→ Reply

_Kee

6 weeks ago, # ^ |

Unlike C++, the stack size of Python runtime is fairly small (I think it's 1MB that's Windows' default), and this doesn't change even if you call sys.setrecursionlimit(), so heavily recursed solutions will get RE anyway.

→ Reply

Divyanshu52Singhal

6 weeks ago, # |

Can someone please check my 2 solution for D and tell me where i could optimize i'm feel defeated at it please anyone spare few minutes on my solution if u want i can explain what i did in my code

→ Reply

A.L.0.0

6 weeks ago, # |

+10

it was more like div 2.5

→ Reply

picoton

6 weeks ago, # |

worts round for me :( all my progress is gone in just one contest. B was so poorly written, and i couldnt figure out the integer overflow on D. why do i even do cp lmao

→ Reply

123gjweq2

6 weeks ago, # |

-13

Could a solution with time complexity $$$O(n \cdot \log(n)^4)$$$ pass for E or would it be too slow?

→ Reply

TrendBattles

6 weeks ago, # ^ |

I implemented a solution around O(N log(N)^3 + Q log(N)) and barely managed to pass.

→ Reply

Sarthak3204

6 weeks ago, # |

← Rev. 4 →

I thought in problem E O(Nlog^3(N)) would fit in TL, but it didn't :/ Submission Can finding the next index from current index i for which count of monsters >= current level is equal to k be done in O(log(N))? I tried binary search + fractional cascading in O(log^2(N))

→ Reply

sarthakj314

6 weeks ago, # ^ |

Hi fellow Sarthak.

It looks like the runtime of your solution is more to the effect of O(n^2/k) rather than O(nlog^3(n)) since you have nested for loops (iterating by 1 and ~ k respectively).

The approach I took was to find the smallest k for which monster i could fight Monocarp, each in O(log^2n) time (hint: I used a binary search + seg tree). This allowed queries to be answered in O(1). Hope this helps :)

→ Reply

6 weeks ago, # ^ |

I did it in$n \cdot log^3_2{n}$ by walking on the segment tree.

→ Reply

DmitryLzr

6 weeks ago, # ^ |

Yes, you can do it similarly to the range k-th order statistic problem.

Let $$$b_{x,i} = [a_i \ge x]$$$ for $$$x \in [1, n]$$$, i.e. each $$$b_x$$$ is an array that contains $$$1$$$s on the positions where $$$a_i \ge x$$$ and $$$0$$$s on the rest. Now, let's build a range sum point update segment tree $$$T_x$$$ on each of those arrays $$$b_x$$$. Finding the next index is just a matter of descending $$$T_x$$$, where $$$x$$$ is the current level, but building those trees naïvely is too slow. However, if you make those trees persistent, then all you need is to build $$$T_n$$$ in $$$\mathcal O(n)$$$ (since level does not exceed $$$n$$$), and then $$$T_x$$$ can be obtained from $$$T_{x+1}$$$ by replacing $$$0$$$s with $$$1$$$s in the positions $$$i$$$ where $$$a_i = x$$$. Since you do $$$\mathcal O(n)$$$ point updates in total, the construction of all $$$T_x$$$ works in $$$\mathcal O(n \log n)$$$.

I don't know if my code is readable, but just in case: 273556813.

→ Reply

Trozan69

6 weeks ago, # |

Please can someone explain what is the error in this appoach for D 273594204. although i know this is failing in test case one only but i am doing the same thing what question says or am i interpreting it wrong please someone explain

→ Reply

Trozan69

6 weeks ago, # ^ |

Please can someone tell me whats wrong.

→ Reply

randombernie

6 weeks ago, # |

I had this idea for D, but couldn't submit it in time. But I keep getting a runtime error on test 19. I'm using Python; can anyone see what's wrong with this submission? My submission to D (RE on test 19)

→ Reply

Divyanshu52Singhal

6 weeks ago, # ^ |

recursion limit 1e5

→ Reply

randombernie

6 weeks ago, # ^ |

Still didn't work. I even increased it to 2e5, but that gave memory limit exceeded

→ Reply

randombernie

6 weeks ago, # ^ |

I've found a solution. A bootstrap function I copied from @pajenegod, a GM who uses Python. It manages the call stack manually, and avoids recursion limit errors. I actually had it in my template, but didn't think to use it until now. It was accepted :)

Thanks. Feel free to check out my template (or pajenegod's code, I just don't know where to find it) for the bootstrap function. You can then use it as a decorator for the recursive function, and replace all your return statements with yield to get it to work

@pajenegod orz, once again

→ Reply

priyanshukaggle

6 weeks ago, # |

← Rev. 2 →

can anyone tell why this code for problem D failed at test case 19:

#include <bits/stdc++.h>
using namespace std;
#define ll long long

bool calculate(vector<vector<ll>>&adj,vector<ll>&vec,ll node,ll mid)
{
    if(adj[node].size()==0)
    {
        if(vec[node]>=mid)
            return true;
        return false;
    }
    ll temp = max(mid-vec[node],1ll*0);
    if(node !=1)
        temp = temp + mid;
    bool ans = true;
    for(int i =0;i<adj[node].size();i++)
    {
        ans = ans & calculate(adj,vec,adj[node][i],temp);
    }
    return ans;
    
}
int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n ;
        cin>>n;
        vector<ll>vec;
        vec.resize(n+1);
        vector<vector<ll>>adj(n+1);
        for(int i = 1;i<=n;i++)
        {
            cin>>vec[i];
        }
        for(int i =2;i<=n;i++)
        {
            ll p;
            cin>>p;
            adj[p].push_back(i);
        }
        ll lo =vec[1], hi = 2e9+1;
        while(lo<hi)
        {
            ll mid = (lo+hi+1)/2;
            if(calculate(adj,vec,1ll*1, mid)){
                lo = mid;
            }
            else
            {
                hi = mid-1;
            }
        }
       
        cout<<lo<<endl;
        
    }
}

→ Reply

InfernoStinger

6 weeks ago, # |

OOf. I solved B for the general case where multiple regions are present. Took me 50 minutes to come up with solution. At that point C already had like 6k solves. Thought solving D will help but nope. Ended up with a Pupil level performance even after solving D. D should not have more than 2k solves imo(even if we take into account how standard it is). Hope the cheaters get pruned.

→ Reply

cncqaq

6 weeks ago, # ^ |

In question B,it is said that the given grid contains at most 1 connected region;

→ Reply

6 weeks ago, # ^ |

Yaa i was also thinking about the general case first and using bfs in problem B Also problem D was a bit standard problem but still 5k submissions in quite high. Anyways best of luck for the next contest

→ Reply

AdityaTakkar

6 weeks ago, # ^ |

What was your approach for solving the general case?

→ Reply

InfernoStinger

6 weeks ago, # ^ |

← Rev. 2 →

Assuming that there are multiple regions present you can do a bfs on the grid to identify and mark all regions. Blocks belonging to region 1 will be marked with the value 1 and so on. While you do this you also have to keep track of the size of every region(can be done using a map). Now the only conditions are: 1. There is one region and we use the editorial logic. 2. There are 4 regions and regions made of a single cell can be blocked to make the total regions equal to 3. 3. Lastly if you have 2 regions and you block a cell such that a region gets divided into 2 regions. 4. The number of regions is 3 and you block a cell in a region which has a size greater than 1(I missed this case actually). If the number of regions is greater than 4 then blocking one block will not be enough. I might be wrong tho.

→ Reply

AdityaTakkar

6 weeks ago, # ^ |

it's messy for the when there are 3 regions. You can only block the end points of regions. Apart from that I also don't think there can be cases for greater than 4 regions. Your solution seems correct to me.

→ Reply

LiuXingJian

6 weeks ago, # |

Overflow may be the cause of the Wa test19 on D. When recording the value that needs to be provided to the parent node, it is essential to verify whether this value exceeds the upper limit that the subtree can provide. Otherwise we can construct a case such that all the a_i equals to 0 and the value being transmitted could be vey big.

→ Reply

RecursiveRanger

6 weeks ago, # |

how come 12k solved c. is it that easy.

→ Reply

rohhit

6 weeks ago, # ^ |

it was easier than B

→ Reply

Rohak

6 weeks ago, # ^ |

Cheaters most probably, no matter how easy it was aint no way 12k people solved it suddenly. Also I noted that it happened too quickly. One moment my rank is 2.5k, within minutes it's 6k. But whatever.

→ Reply

Captainfly

6 weeks ago, # |

Problem D if you WA on test19,please check your data scale. In the process of DFS,when the val exceed 1e9 you should return the process.

→ Reply

21Cash

6 weeks ago, # ^ |

Can u explain why the if check is required, overflow issue ??

→ Reply

cncqaq

6 weeks ago, # ^ |

← Rev. 5 →

Maybe your solution is different to his,no need for the if check,but

If you use binary search to solve D.Being able to construct data where all a_i values are 0 would result in leaf nodes requiring very large values, causing them to exceed the range of 'long long'.

→ Reply

6 weeks ago, # ^ |

← Rev. 3 →

i got it.

→ Reply

m_nature

6 weeks ago, # |

I guess I should re-learn how to read statements after implementing a much harder version of problem B and then deleting almost all of it...

(But please, something as important as "at most 1 connected region" should be bold or in capital letters, or have a bigger font size, whatever, the next time around please...)

→ Reply

6 weeks ago, # |

Is $$$O(nlog^3(n) + qlog(n))$$$ enough to pass E? If it is, could someone explain why my submission got TLE?

→ Reply

1BeeNY1

6 weeks ago, # ^ |

I also got TLE. Try Fenwick tree, it works for me.

→ Reply

MarioYC

6 weeks ago, # ^ |

Your precomputation step's complexity is actually $$$O(nlog^4n)$$$.

For each of the $$$O(nlogn)$$$ level changes you do a binary search which adds a $$$O(logn)$$$, and your query method has $$$O(logn)$$$ calls, and calling lower_bound inside adds an extra $$$O(logn)$$$.

I actually had the same issue, the query method can be changed so that the binary search is done inside the query.

→ Reply

6 weeks ago, # ^ |

Ok I miscalculate the time complexity, my bad :(

→ Reply

6 weeks ago, # ^ |

Could you explain the way to modify those binary search inside the query?

→ Reply

MarioYC

6 weeks ago, # ^ |

Instead of just returning a count you can return a count and also the position where it is reached. Also there is a maximum count you don't want to exceed and you need to remove a prefix which is not within the range of the query. You can take a look my submission

→ Reply

yellow_13

6 weeks ago, # ^ |

← Rev. 2 →

To do this you can use a method called 'Walk on segment tree'. Basically it uses the structure of the segment tree in such a way that you don't have to do an additional binary search. You can read about it from here.

I slightly modified your submission to use this concept and got AC:273649483

As you can see, instead of using the qry method along with binary search, I made another method called qry2 which makes use of walk on segment tree.

→ Reply

TrendBattles

6 weeks ago, # ^ |

← Rev. 2 →

that is around O(N log(N)^4 + Q log (N)), you may want to use walk on the merge sort tree to cut off a log(N) coefficient.

→ Reply

6 weeks ago, # ^ |

Okay, I just remember about the "finding the kth largest problem" and know how to walk on the merge sort tree. Thanks for your help.

→ Reply

puupil

6 weeks ago, # |

my best ever contest. First time abcd solve in div. 2. authors were also very nice, I had a very nice and friendly interaction with them while asking questions. Overall, loved the contest but ngl, D was a little bit easier

→ Reply

Le_Gusto

6 weeks ago, # |

I don't think I've ever blundered this hard in a contest, forgot a return statement in A and forgot to check one cell in B, so by 53 mins I had only C solved + multiple WAs for A and B. (+ I couldn't find the issue in B till the end of the contest :( )

→ Reply

The5threich

6 weeks ago, # |

Some people like problems like B, but I think such subtle statements in the problem statement reduce readability. It becomes more about reading the problem than actually solving it. (Might just be skill issue)

→ Reply

2021ceb1010

6 weeks ago, # |

← Rev. 2 →

is this solution of E hackable ? (https://codeforces.net/contest/1997/submission/273599912)

→ Reply

is_this_greedy

6 weeks ago, # |

D : For all the nodes u, find the maximum value they can have such that all the nodes in their subtree will have the final values atleast equal to the final value of node u . Now for root , the maximum increase in its value is " the minimum of the final values of all its childs " .

Code

→ Reply

6 weeks ago, # |

Recently cheating has increased quite a lot on CodeForces although problem D was bit standard more like leetcode contest hard question(6 pointer not 7 or 8) but still 5k submissions is really high, the contest went really well for me but still got around 2.7k rank. I have been stuck at specialist rating for some time now due to the high level of cheating. Hope CF will increase action on these cheater

→ Reply

hhhzzff

6 weeks ago, # ^ |

i wanna know they got the question before the contest or they interact each other ? how they do this ?

→ Reply

6 weeks ago, # ^ |

I guess these solutions are shared in telegram groups during the contest due to some companies using coding platform rating as screener but still it gets really unfare for genuine users

→ Reply

avengers2405

6 weeks ago, # ^ |

I definitely think a person being stuck at a rank has more to do with their skill level than cheating.

It is not that people have stopped becoming experts, have they? We should focus on what we can focus on, rather than finding excuses.

→ Reply

_HUECTRUM_

6 weeks ago, # ^ |

While cheating is absolutely a thing, I don't think attributing being stuck at a certain rating point to it is a good idea. What you're essentially claiming is that 5k people couldn't have solved D, casting doubt at each person with an AC.

→ Reply

6 weeks ago, # ^ |

Sorry didn't meant it like that just wanted to point that cheating does effect user rating as such assuming even just 5-10% users cheat. I understand it might also be difficult for codeforces due to high number of false positives in a stricter plag checker Also as you are a candidate master can you suggest mistakes to avoid and increase ones problem solving skill with time

→ Reply

21Cash

6 weeks ago, # |

awoo orz.

→ Reply

hhhzzff

6 weeks ago, # |

for D i try binary search and dfs .it looks right but i wa on 19 for 3 times so sad :(

→ Reply

6 weeks ago, # ^ |

make the if condition in the dfs function if(v > 2e9)

→ Reply

hhhzzff

6 weeks ago, # ^ |

thx very much i learn that the v will overflow long long int

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

solved.

→ Reply

shadow9236

6 weeks ago, # |

+24

D without binary search and overflow —

Let $$$dp[i] = $$$ maximum possible minimum value in the subtree of $$$i$$$ with optimal operations. We have —

$$$ dp[i] = \begin{Bmatrix} a[i] & \text{ if } i \text{ is a leaf} \newline \min\limits_{j \in \text{ child of } i}(dp[j]) & \text{ if } \min\limits_{j \in \text{ child of } i} (dp[j]) \leq a[i] \newline \left\lfloor\frac{a[i] + \min\limits_{j \in \text{ child of } i} (dp[j])}{2}\right\rfloor & \text{ if } \min\limits_{j \in \text{ child of } i} (dp[j]) > a[i] \newline \end{Bmatrix} $$$

Submission — https://codeforces.net/contest/1997/submission/273602376

→ Reply

Mohamed_Saad62

6 weeks ago, # ^ |

I read your comment so I went to fix the overflow in my code and got Accepted, lol

→ Reply

Mohamed_Saad62

6 weeks ago, # ^ |

It was confusing I kept asking, what is so different in test 19

→ Reply

puupil

6 weeks ago, # ^ |

same approach. Fist bumps!

→ Reply

6 weeks ago, # ^ |

Same here, however it is better to describe the approach instead of giving those formular, as it will be scare for people who didn't know how to do this.

→ Reply

wazz

6 weeks ago, # ^ |

similar approach but I don't know why I stored it in a segment tree tho, kinda dumb xD and a waste of time!

→ Reply

misaki646

6 weeks ago, # |

can anyone help show me what's the wrong test in my solution problem D: 273557414. My idea was collecting points from leaf to root

→ Reply

misaki646

6 weeks ago, # ^ |

← Rev. 2 →

nevermind I found the error, only put parents that have no child left into the queue. Skill issue again

→ Reply

MrLolthe1st

6 weeks ago, # |

Long time without writing segtree at contest + bad approach (ignored few cases) cost me -3 at final standings.

Approach: let's solve problem offline for each $$$k$$$ in queries.

If $$$k\leq K$$$ (let's choose $$$K$$$ later), than solve with stupid method (just implement statement), requiring $$$O(n)$$$ for each $$$k\leq K$$$, overall $$$O(nK)$$$.

If $$$k>K$$$, there is at least $$$ceil(\frac{n}{k})$$$ monsters to be passed before level up. Since there, we can make $$$ceil(\frac{n}{k})$$$ steps for each $$$k>K$$$. Where $$$W$$$ -- magical constant, stated as time to be done following: gived fixed $$$r$$$ -- left edge of interval and $$$lvl$$$ -- our current lvl, find minimal $$$i\geq prev$$$, such that $$$count(a_j\geq lvl, r\leq j \leq i)=k$$$. It can be solved in $$$O(\log^2(n))=W$$$ time using segment tree storing sorted vectors of elements on array.

So, let's take $$$K=1000$$$ and final complexity is: $$$O(Kn+n\cdot \log(n)+\frac{qn\cdot \log^2(n)}{K})$$$

WA during contest: 273573012 OK: 273599991

→ Reply

HackerGupta069

6 weeks ago, # |

It's sad to see that constraints on problem B were corrected(mentioned for the first time) around after half an hour.

→ Reply

Hussain_Elemam

6 weeks ago, # |

I just solved D after the end by less than a minute, very sad

→ Reply

the_last_smilodon

6 weeks ago, # |

How do we solve D without binary search?

→ Reply

is_this_greedy

6 weeks ago, # ^ |

Check my comment above.

→ Reply

6 weeks ago, # ^ |

Yes, we could use greedy. Knowing that if we goes up to a root of some subtrees, those children in this subtree won't be higher (as the operation will make them decreasing by $$$1$$$ each time), so we will aim for maximizing the minimum of all value of this subtree (including the root of this subtree as well).

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

let dp[u] be the max smallest value of subtree u after doing operations

for node u: without doing any operations then the min val would be min(A[u],dp[v]) where v are all the children

you could spend one operation to increase A[u] but that would decrease dp[v] by 1

so let a = A[u], b = min(dp[v]) if a > b then do nothing (aka dp[u] = b)

otherwise do k operations until min(a+k,b-k) maximizes (which just so happens to be (b-a)/2 operations) -> dp[u] = min(a+(b-a)/2, b-(b-a)/2)

for the root/final answer: you could freely do the operation so the answer is A[0] + min(dp[v])

→ Reply

anupam_713

6 weeks ago, # ^ |

check my approach explained in this comment https://codeforces.net/blog/entry/132049?#comment-1177386

→ Reply

_neooo_nishad

6 weeks ago, # |

can anyone explain me no. B simply, what should i do?

→ Reply

6 weeks ago, # ^ |

if you delete a cell then the most number of regions that can be created is the number of open cells that neighbours it directly -> it must have 3 empty neighbours

now imagine this:

1 v 3

a 2 b

v = the node you're deleting

if a is an empty cell then region 1 and 2 are actually the same region so you'll only get at most 2 regions -> a must be blocked

same for b and region 2+3

so the answer is just the number of patterns that are either

. . .

x . x

. . .

→ Reply

anupam_713

6 weeks ago, # |

Problem D using simple dfs 

Approach
now let's see the case when i would not like applying operation on root.. 

4 -> 4 -> 6 
1    2   3 

what i can do is .. apply operation on 3 .. so it would become 
4 -> 5 -> 5 
ans would be 9 .. 
so like i want all nodes to be equally in way you can say.. 

so i do dfs.. 
when i reach a node.. i first take min of all it's children. 
now if observer.. 
if node_value >= min_of_children then return min_of_children..   
as i can't make the children nodes largeer from parent.. 
if node_value < min_of_children 
    3      <    5 
    what i would do is.. diff = min_of_children - node 
    node_value += diff/2 
    then i return node_value 

so when i reach root node .. instead of focussing on returning .. 
i add whatever min value is coming from down to root's current value. 

// values[0] would be updated after this function called, return that
int dfs(int node)
{
    visited[node] = true;
    int min_value = INT_MAX;
    for (auto child : adj[node])
    {
        if (!visited[child])
        {
            int returned = dfs(child);
            min_value = min(min_value, returned);
        }
    }
    if (min_value == INT_MAX)
    {
        if (node == 0)
            return 0;
        min_value = min(min_value, values[node]);
    }
    else
    {
        if (node == 0)
        {
            values[node] += min_value;
            return 0;
        }
        if (values[node] < min_value)
        {
            int diff = min_value - values[node];
            values[node] += diff / 2;
        }
        min_value = min(min_value, values[node]);
    }
    return min_value;
}

→ Reply

__NO__NAME__

6 weeks ago, # ^ |

Nice approach. Even i did the same way..we do not need visited array if we make it directed graph.

→ Reply

_looser__

6 weeks ago, # |

very bad contest for me wasted almost 1 hour 40 minutes just because i thought x is capital and in the end i somehow figured out what was the mistake anyway cheating has been at it's peak today

→ Reply

nskybytskyi

6 weeks ago, # |

By the way, the custom invocation tab wasn't working today. I tried benchmarking my F to account for hardware differences, but it wasn't responding. Fortunately, it did not matter to me today, but you should probably fix it before the next big event.

→ Reply

Maverick_20

6 weeks ago, # |

+14

I don't know who introduced the Cloudflare checking system to codeforces (to check if I'm a human), but I suffered the worst. The problemset was quite standard but it took me aound 7 minutes to enter the contest as 'The system was still checking if I'm a human'. Then after solving A, I could not submit any problem as the same problem kept happening. I tried mobile cf, other browsers, tried to change my net, nothing worked. I guess yeah, my network was quite slow but I could not enter the whole contest after that! I do not blame anyone but it was really a sad contest for me as I was quite hopeful I could solve upto D.

→ Reply

Ami_Nul

6 weeks ago, # ^ |

same to me...

→ Reply

Shaydiesin

6 weeks ago, # |

Idk why my code is giving RunTime error on a particular case Question D With exit code 1:

Here's my submission Submission

→ Reply

6 weeks ago, # |

Maybe anyone is interested in non-recursive solution for D, I did it during the contest because was afraid of hack, I thought that recursion depth of 2*10^5 will cause overflow. Also left there recursive function for comparison: https://codeforces.net/contest/1997/submission/273588364

→ Reply

ayush_kumar912

6 weeks ago, # |

any body knows how to fix the friend glitch, i am unable to add or remove anyone?

→ Reply

salmanhussain9057

6 weeks ago, # |

Please check my approach for D, is it hackable or not ?? 273621989

→ Reply

Summer_Wind

6 weeks ago, # |

For Q-D wa on testcase 19 , putting a condition in dfs function as a base case that if the required subtraction need to be done from the subtree > 1e9 , return false may work !!

→ Reply

srrow_xhr

6 weeks ago, # |

← Rev. 2 →

→ Reply

delwar_03_

6 weeks ago, # |

Many people solved F with a Fibonacci idea. What was the actual idea?

Can someone link some blogs to read about it and also some problems of a similar idea.

TY in advance :D

→ Reply

jatrophalouvre

6 weeks ago, # |

Greedy for D works too, basically we add to each node until that node is less than or equal to the minimum in its subtree (excluding itself). I did this during the contest

→ Reply

-Jarvis-

6 weeks ago, # |

273574835 why my this solution for C is giving TLE?

→ Reply

treasuryonly

6 weeks ago, # ^ |

← Rev. 2 →

String formed = "";

formed += '(';

The string concatenation is slow because the new string is created every time, you can use StringBuilder for better performance.

StringBuilder formed = new StringBuilder("");

formed.append('(');

You can replace with these and submit again.

→ Reply

-Jarvis-

6 weeks ago, # ^ |

← Rev. 2 →

damnn! it worked. thanks a lot!

this is something new which I have came across. do you know any specific reason for this behaviour?

→ Reply

treasuryonly

6 weeks ago, # ^ |

String in Java is immutable which means it can't be modified. The way it handles the update is to clone the current one to the new one, then apply the changes on this new one, then assign the result back to the original one. This performance would be really slow for big string and especially in the loop.

→ Reply

-Jarvis-

6 weeks ago, # ^ |

thanks for sharing!

→ Reply

_regular_show

6 weeks ago, # |

It's really a good round. Thank you!

→ Reply

lyl_ccut

6 weeks ago, # |

Where's the text solution?

→ Reply

Misa-Misa

6 weeks ago, # |

Hack my solution to E.

→ Reply

drgrenkenstein

6 weeks ago, # |

Can anyone explain why the rank is decreasing during the hacking phase? Thanks!

→ Reply

anandchourasia007

6 weeks ago, # ^ |

Basically some people originally above you in the rankings got their solutions hacked.

→ Reply

drgrenkenstein

6 weeks ago, # ^ |

I am sorry I meant increasing in my mind it was decreasing I had a rank of 5880 something but during the hacking phase it went up to 5960

→ Reply

anandchourasia007

6 weeks ago, # ^ |

In that case you are probably seeing unofficial rankings, which includes virtual participants as well.

→ Reply

drgrenkenstein

6 weeks ago, # ^ |

Oh yes, that makes sense. Thanks!

→ Reply

rock_nroll

6 weeks ago, # |

Can anyone please help me find why below solution got me WA . I am binary searching on the maximum increment that i can do on the root node.


void dfs(ll vertex , vector<ll>adj[], ll vis[] ,ll value[] ,ll want  ){
    vis[vertex] =1 ; 
    vector<ll>leaf ;
     
    for(auto child : adj[vertex ]) {
        if(!vis[child]){
            leaf.push_back(child) ; 
        }
    }
    if(leaf.empty() ){ 
        value[vertex]-=want ;
    }
    else { 
        value[vertex]-=want ;
        ll extra ;
        if(value[vertex] <0 )extra = abs( value[vertex] ) ;
        else extra =0 ;
        
        value[vertex]=max(value[vertex],0LL) ;
        
        for(auto child:leaf){  
            dfs(child,adj,vis,value,want+extra) ;
        }
    }
}
 
bool check(ll mid , vector<ll>adj[] , ll n ,ll val[] ){  
    ll value[n] , vis[n] ;
    for(ll i=0 ;i<n ;i++ ){
        value[i] = val[i] ;
        vis[i] =0 ;
    } 
    
    vis[0] =1 ;
    for(auto i : adj[0] ){
        dfs(i,adj,vis,value,mid) ;
    } 
    for(ll i=0 ;i<n ;i++ ){ 
        if(value[i] <0 )return false ;
    }
    return true ;
}

Thanks in advance....!

→ Reply

Scourge_Seraph

6 weeks ago, # |

← Rev. 2 →

Someone tell me why my solution to problem D is giving TLE? 273573102

→ Reply

cwz2024

6 weeks ago, # ^ |

When you call the function traversal, the function will make a copy of m. So if it is called n times, the m will be copyed n times, which will cause TLE. You can pass the reference of m to the function so it won't be copyed when you call the function.

Spoiler

ll traversal (map<int, vector<int>> &m, ll arr[], int node)

→ Reply

Scourge_Seraph

6 weeks ago, # ^ |

Thank you! I will remember it for future problems

→ Reply

omjoshi7206

6 weeks ago, # |

second question was a quite tough for begginers maybe but finally i did it without using bfs. I use mapping for both strings and then solved it further.It was such satisfying and good experience. Thank you.

→ Reply

gokugod02

6 weeks ago, # ^ |

i dont think it was tough , it was just a pattern that needed to be observed , if you can make a 'V'OR 'A'with x at the vertices, its done.

→ Reply

Atma_

6 weeks ago, # |

-11

(B,C,D) <<<< A <<<<< (E,F)

→ Reply

parag776

6 weeks ago, # |

+21

F is a beauty!! loved that the Fibonacci is hidden in plain sight idea!! it had everything, memory optimization, knapsack, and lovely math.

→ Reply

6 weeks ago, # |

"This round will be rated for the participants with rating lower than 2100." Is this contest was rated for newbie or not ??

→ Reply

parag776

6 weeks ago, # ^ |

yes its rated for newbie

→ Reply

6 weeks ago, # ^ |

But it is showing unrated on my profile

→ Reply

ShauryaH4X

6 weeks ago, # ^ |

wait till system testing

→ Reply

6 weeks ago, # ^ |

still not updated

→ Reply

_inaccurate

6 weeks ago, # |

D was a very great problem, but some of my friend get WA on the 19th test

→ Reply

6 weeks ago, # ^ |

he didn't handle the overflow like me

→ Reply

_inaccurate

6 weeks ago, # ^ |

oh, i see!

→ Reply

srrow_xhr

6 weeks ago, # |

← Rev. 2 →

first time to solve problem D in contest, and hope to solve problem E in contest one day :)

→ Reply

b00s

6 weeks ago, # |

Hi, can somebody tell me about the complexity of 273675185

→ Reply

6 weeks ago, # ^ |

$$$O(nlog^4{n})$$$ assuming the LTE function is $$$O(log^2{n})$$$, I don't know wavelet trees.

→ Reply

b00s

6 weeks ago, # ^ |

I have used the implementation in this link. it says that, Counting elements less than or equal to $$$x$$$ in a given range is $$$O(\log {n})$$$.

→ Reply

6 weeks ago, # ^ |

Hmmm, that is very OP, what is the point of merge sort trees then?

→ Reply

b00s

6 weeks ago, # ^ |

given that, the counting happens in $$$O(\log n)$$$ time. the complexity of this solution should be $$$O(n\log^3{n})$$$ . but it is giving TLE. can you spot any mistake in this.

→ Reply

6 weeks ago, # ^ |

I don't understand your code sorry. Are you sure that your complexity is $$$n log^3{n}$$$, I solved it in $$$n log^3{n}$$$, maybe your constant factor is too high.

→ Reply

deadnecro18

6 weeks ago, # |

Editorial when?

→ Reply

6 weeks ago, # |

← Rev. 3 →

I am wondering why someone with red name is official participants. (20240731 08:05 GMT)

However, it said "This round will be rated for the participants with rating lower than 2100" in the announcement.

→ Reply

6 weeks ago, # ^ |

After system testing you will be able to see the standings for Div. 2 separately.

→ Reply

6 weeks ago, # ^ |

Thank you very much!

→ Reply

cwz2024

6 weeks ago, # ^ |

In edu rounds, every participant is "official", but only participants with 2100- rating will be rated.

→ Reply

https://codeforces.net/contest/1997/submission/273676836

6 weeks ago, # ^ |

← Rev. 2 →

-9

Thank you

→ Reply

aabidraina

6 weeks ago, # |

What is wrong with the following submission, it is giving a? as output for s = "a", locally it is working fine.

→ Reply

anandchourasia007

6 weeks ago, # ^ |

Your first for loop starts from s.size()-2, but input size is 1. Maybe this causes undefined behaviour.

→ Reply

aabidraina

6 weeks ago, # ^ |

Yeah, size returns unsigned it which causes the issue. Casting it to int solves the issue

→ Reply

6 weeks ago, # ^ |

← Rev. 2 →

In this part of your code:

        for (int i = s.size() - 2; i >= 0; i--)
        {
            if (s[i] == s[i + 1])
            {
                n = i + 1;
                break;
            }
        }
        if (n == -1)
        {
            char ch;
            if (s[s.size() - 1] == 'z')
                ch = 'a';
            else
                ch = s[s.size() - 1] + 1;
            cout << s;
            cout << ch << endl;
            continue;
        }

The function s.size() returns the type of unsigned int, so it can't be negative.

However, you have written int i = s.size() - 2.

So $$$s.size() == 1$$$ and then $$$s.size()-2 < 0$$$.

Therefore, $$$i$$$ becomes a extremely big number, then will be somewhere successfully match the scentence if(s[i]==s[i+1]), and $$$n$$$ will also become really big, that is, $$$n$$$ will not be $$$-1$$$.

Thus, it cannot get into the block if(n==-1).

→ Reply

IsItFakeMe

6 weeks ago, # |

Tricky but interesting problem F, enjoy it.

→ Reply

luyouling08

6 weeks ago, # |

→ Reply

PCT2506

6 weeks ago, # |

Good luck!I hope I can achieve green after this contest if I have time to participate in this contest.

→ Reply

_Unseen_

6 weeks ago, # |

Heyy anyone solve D using BS?

→ Reply

contest submission, resubmission

6 weeks ago, # ^ |

Lots of people.

→ Reply

CatchMe_

6 weeks ago, # |

I want to know that why system testing take much more time than div 1? Can you explain me?

→ Reply

FuyuMai12

6 weeks ago, # ^ |

First, open hacking phase adds an extra 12+ hours delay.

Second, actually easier rounds (educational/div3/div4) are more appealing to lower-ranked people, which actually holds the majority of the users, resulting in more participations, and more codes to rejudge.

→ Reply

CatchMe_

6 weeks ago, # ^ |

Ok,that means no of participant fact.

→ Reply

djm03178

6 weeks ago, # ^ |

This time especially was slower due to crazy amount of TL hacks on E, which was solved quite a lot for its position, and most of solutions on it used a few seconds on each test. Each solution alone took 5-15 minutes to be fully judged.

→ Reply

awoo

6 weeks ago, # |

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

→ Reply

pagol

6 weeks ago, # |

Wow! Now everyone is rated for EDU!

→ Reply

MIYAD_KERNEL

6 weeks ago, # |

Is this round rated for DIV1 participants?

→ Reply

nichke

6 weeks ago, # |

MikeMirzayanov Why was this contest rated for me even though I've long been a master??? I want my rating back.

→ Reply

mrmind12

6 weeks ago, # |

it was better when you make the error

→ Reply

Hong_Meiling

6 weeks ago, # |

I found my contest submission had got a TLE, but when I resubmitted it after the system test, I passed. What's wrong with it?

→ Reply

6 weeks ago, # ^ |

The running time depends. The running time of your resubmission is 3406ms, it's also very close to the time limit. So maybe submitting during the contest again also makes you accept.

→ Reply

Hong_Meiling

6 weeks ago, # ^ |

I was hacked after the contest, and as far as I know, resubmission doesn't count in the system test.

→ Reply