## Neko Nya, Кодефорсес =＾● ⋏ ●＾=

I'm happy to invite you to participate in Codeforces Round 926 (Div. 2). It will take place on Feb/15/2024 17:35 (Moscow time) and in it, you will help a boy named Sasha win over a girl's heart. The round will be rated for all participants with a rating strictly less than 2100. You will have 2 hours to solve 6 problems.

Here is a big thank you to everyone involved in the round:

- The cutest coordinator Artyom123. (No offense to the others)
- KAN, geranazavr555, MikeMirzayanov for the BEST platform.
- Legion of testers: A_G, AgafonovArtem, Alexdat2000, Vladithur, wuhudsm, petyb, induk_v_tsiane, sevlll777, mz1, SomethingNew, AVdovin, NewLul, damirsit, skylak3_3, Andreasyan.
- Also to this wonderful person for his invaluable contribution to the round teraqqq.

Looking forward to seeing everyone at the contest >~<

**UPD:** Scoring distribution: **500 — 1000 — 1500 — 2000 — 2500 — 3000**

**UPD2:** Editorial

As a tester I highly recommend you writing this round!

As a part taker, I trust your recommendation!

wow, that's cool, thanks

cutie FairyWinx

Finally, a catgirl round!

Finally, a catgirl round!

As a tester,this round has a clear and concise statement. I highly recommend you to participate :)

Yeah, right

cnx

sxksnx

hello

jiekd

sm sx

xwnxknw kwnxd

*crying intensifiessure...

About that.....

Am I the only one who could not understand this statement of D?

`If in the city only the intersections contained in this set are dangerous, then any simple path in the city contains no more than two dangerous intersections.`

They probably used google translation to get the statements xdd

Me too

Score Distribution of the round?? Score -> Updated

uwu

Kudos to the authors for continuing the trend of attaching their photos!

OWO

stealing my meme bro?

SpoilerI don't mind

scoring distribution???

score distribution ?

Sasha is a determined young man, and he's not afraid to use his programming skills to win over the girl of his dreams. In this Div. 2, Sasha will have to solve 6 problems in 2 hours. But with the help of the cutest coordinator Artyom123 and the best platform KAN, geranazavr555, MikeMirzayanov, Sasha is sure to succeed. And if he needs any help, he can always count on the legion of testers: A_G, AgafonovArtem, Alexdat2000, Vladithur, wuhudsm, petyb, induk_v_tsiane, sevlll777, mz1, SomethingNew, AVdovin, NewLul, damirsit, and skylak3_3.

Good luck, Sasha! We're all rooting for you!

Thank you, but you'd better help me and solve as many problems from the contest as you can.

>.<

What about the streak of announces with photo of authors???

still maintained for div 3 rounds

It is in announcement.

Maybe its the cat girl.

Hope to become expert in this round.

GOOD LUCK

GOOD DUCK

Why do I feel like I'm being called for by the announcement? (•‿•)

╱|、

(˚ˎ 。7

|、˜〵

じしˍ,)ノ Good luck to all ≽^•⩊•^≼

I don't have a GF in real life, and I also can't use my limited coding skills to help you. So sad......

its soo ovER

But you have a chance to help Sasha do it

I 'll try my best!

the cat is cute

koshka

Do you mean "Elena Koshka"?

No, just koshka

I'll try my best to solve problems to help a boy named Sasha win a girl's heart. ≽^•⩊•^≼

kawaii catgirl !!

You are cute !!

No girls, only hardcore

Love the theme of this round. Let's goo. Hopefully it is a good one. All the best everyone❤️

Short round blog !

I hope I can solve 3 problems!!!

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

This comment did not age well

Short statement Blog … nice

Either way gonna sweat on 14 or 15

Hope to become expert in this round!

Mid sem from 19 but CF round is the first priority

brooo sameee, its is soo over

kawaii neko ^-w-^

As a tester, i wish good luck to all participants.

Sasha, I'll try to help you get her number)

But I knew Sasha is a girl's name from AOT .

Nice of you to keep up the trend of problemsetters including their photos in the announcement

Oh, just noticed that I'm not the first one to think of that(

hoping to win heart three times very quick....

Hoping to do better after a disastrous run of contests.

hope for the best....

its either cyan or gray time no inbetween for me

CM next contest calling it from now

Doesn’t the average tester rating seem quite high? :)

Hopefully I can do the first four problems！

I want to solve ABCD

A lovely catgirl! I have to take part in this round. Will I become a catgirl after this round?

Your text to link here...

WOOOOOOOOOOOOOOOOOOOOOOOOOOOOOH

I finally have a legitimate reason to show my catgirl side in front of others. So after this contest I'm going to meow meow meow meow meow meow meow meow meow meow meow meow meow meow meow meow!:3

that is crazy

cute catgirl.

New profile picture

## catgril !!!

Looking forward to "Good Luck and High Rating"

Ended up with “Bad Luck and Low Rating”

All the best

Neko round lets gooo!

ฅ(=･ω･=)ฅ

As a particapant i alreary know this is gonna ne a great round

Good Luckto all the participants.lovely score distribution (´･ω･`)

As a participant I like the vibes

lets see if this sasha(me) can be specialist or not,, wish me a good luck..

I need someone to help me,as sasha (*_^).

IDK that Codeforces changes its name to Kawaiiforces now =✪ ᆺ ✪=

I might top this round

I will start from $$$C$$$

Wanna help Sasha badly

Finally, score distribution released

Nice score distribution

Even in kindergarten, Sasha liked a girl.

I'm a bit confused, I guess I forgot registering for contest, and there's timer stating: "Before extra registration", yet I'm unable to register? New here. Edit: my bad

i love catgirls

C statement is not clear to me?

Same, no idea what its asking. The sample tests seem to contradict the problem statement

I have the same issue with the problem, I even tried to guess it with samples (which shouldn't ideally be the case), but still I don't get it.

They should add some explanation to more sample cases, or add extra information in the problem.

In C I am not able to understand the condition for Yes

very unclear statement of problem C.

Spent 30min reading the problem and just 5min solving it.

can you explain problem statement ... testcases are contradicting from problem statement, why testcase 4,7,8,9 are no

For Problem C the explanation is the most unclear explanation I saw

Edit : Thanks for answering our questions by " do not ask questions " XD

You'll change your mind after reading D

sasha is such a simp rizzing girls in kintergarden.. phh

i dont get the c question . is it math ?

same, the cases are making no sense according to the test case

yeah after the hint i finally get this . pretest 7 was something very hard to find

In case of 3 3 6, Can't I always bet 1 and get as many coins as required. I am taking the case where there is no consecutive x losses

1 1 1,

If you win in 3rd time then you get 3, you achive 3-1 = 2 extra. But you already loss 2.So your coin will be no change.

Hey can you please hint me on pretest 7? I failed it and could not figure out why :(

I start with y = 1 and s = 1 (where y is the money I spend on this round, and s is the total money I have spent). I loop x times, each time update y to 1+s/(k-1) and s to s+y. Finally I check if s>a (i.e. if I have enough starting money for the worst case).

Edit: Okay.. I just figured out long long is not enough, I need unsigned long long... This makes me feel bad :(

Few testcases are literally so weird w.r.to the problem statement.

I just think C is clear.

In which aspect cant you understand the statement?

why wont he bet all his money after he end the losing streak , that way he doubles his money and he can get the amount he wants?

I was initially thinking the same but there is a catch and that is what this problem is all about.

cant see the catch , if u dont mind explaining it to me ,after the contest ofc.

Well the casino can 'fuck him over' by giving him a win just before he is guaranteed to win, making him go into a cycle of losing money.

How this works for the test-case 3 3 6?

Sasha can bet just 1 coin in each round:

1 coin — lost

1 coin — win; receives 3 coins, total coins = 6 — 1 — 1 + 3 = 7

And so on... Any amount can be created with just 1-1 coin bets!

What if he loses for the first 3 times !! Then he is remaining with 6-3=3 coins.. Then if he again uses just 1 coin, he will be left with 3+3=6, so no improvement, right !!

But, what after loosing 3 times, he bet with the amount 3.... this time he will have total score of 9

Yes, but if he loses first 3 times, as x is 3, won't he bet all his coins for this round.

Dude, the point is that the casino can LET HIM WIN on play 3, think about that case

But how is gonna know when he will win or lose !?

He can lose

maxk times in a row..suppose when he uses 1 coin, he wins but when he uses 3, he lose ! :(His goal will be to make 7 coins from 6, right !Then, that can recursively increase to 8, 9 ans so on..

Step 1: He can use 1 coin: If he wins, he is left with 6-1+3=8 (>=7) But he loses, left with 5

Step 2: He can still use 1 coin: If he wins, he is left with 5-1+3=7 (>=7) But he loses, left with 4 now.

Step 3: Now, if he uses 1 coin, even after winning, he will be back to 6..which is less than 7.. So, he must use 2 coins.. If he wins, OK But he again loses, so left with 4-2=2

Now, he is bound to win..but at max he can reach upto 2*3=6, so no increment..

I hope you guys get it :)

Thanks for the explanation. I understood it now!

Take a look at my other comment where I explained the 3 3 6 case.

The casino can decide whether to win or lose if there are no more than x number of games. If you keep betting on one dollar and win in the middle, the total amount will be smaller.

so should i keep betting one and see if i run out of money or not?

Each winning streak resets, and if the casino allows you to lose money in a losing streak, the total amount will not go up no matter how much you bet.

so if after the first streak, my money is decreased , that means he lost or what

Of course it means that he loses because he can't possibly have more money than the principal.

there is no guarantee that he will lose every single one till he gets the guaranteed win. His lose streak could go zero at the x-1st try.

D is not clear at all what's wrong with the writers

I think the contest is made for the writers to understand only <3

What's amazing is that dozen of LGMs just solve anything, I wonder do they need problem statements at all? )

From their experience they solved many problems so they know what the writer want by reading some main points from the statement, one day we will be some of them <3

Yeah, that makes sense indeed. It's like extra skill to be able to understanding the message from a pile of random words.

At least this round showed me the area I need to practice it a lot :)

It's pretty clear if you ask me, and English isn't even my first language. Can it be worded better? Definitely. But the statement along with the testcases are adequate I think

now I won't participate in any contests which have something like love stories in the problems, first diskoteka and his stories about Vika and now this one.

Bring back competitive programming please.

There is some real

BULLSHITgoing on with me cout << ceil (value of something); is apparently incorrect in some cases but if We take, ans = ceil (value of something) cout << ans; is correctThis is disturbingcout << ceil(value) returns a floating-point value and ans = ceil (value of something) cout << ans; will typecast that float to integer (assuming ans is of int or long int type)

Thnx Bro didn't know that, it just caused me an hour, so I knew ceil of(val/2) is equivalent to (val+1)/2 so I just randomly changed it to: cout << (val+1)/2; and I was even more furiated when this got accepted :(

That's how we all learn :)

Why are we gambling on codeforces?

felt Question C was not clear at all

I wish I could have visited Casino once :(

WTF the language of problems is so uncertain and hard to understand,like in b i didnt saw sample test case,and confused in what diagonal means, in c what any number of coins means was also uncertain and i read d 12-15 times and didn't understood the problem, plz work more on problem statements,it sucks

Unromantic problem wordings :(... Dreams tonight for ppl solving D, E, and F:

i gonna give u a downvote,unless the people who wrote these questions became a cat girl and date with me. :)

Rigged ah casino , house always wins!

C is an interesting problem that is very poorly worded

C is the hardest problem, change my mind

The language is hard :)

Problem

Dcan be solved using the technique of adding children incrementally to a tree, for which I've recently created 2 tutorial and 2 practice contests.Tutorial 1 and Tutorial 2

Practice Contest 1 and Practice Contest 2

My submission using the ideas from the tutorial.

I feel dumb to be unable to solve C. Goodbye Specialist and welcome Pupil :(

goodbye codeforces (╥﹏╥)

D and F are very standard, while C was really hard (for me).

I saw F after the contest. Seems easier than D and E unless I'm misunderstanding the problem..

True wasted time on C.

The easiest div2 contest I've ever seen (but understanding problem statements is harder than solving them).

A: max(a[i])-min(a[i])

B: If you color cells (1, 1), (1, 2), ..., (1, n), (n, 2), (n, 3), ..., (n, n-1) by this order, you color 2 new diagonals for each cell. And coloring (n, 1) and (n, n) will fill last 2 diagonals. So the answer is ceil(k/2) if k<4*n-2, 2*n if k==4*n-2.

C: Suppose you place a bet of t[i] coins if you've lost i times in a row (0<=i<=x), in order to make the number of coins increase, we must have k*t[i]>t[0]+t[1]+...+t[i] for each 0<=i<=x, and t[0]+t[1]+...+t[x]<=a. So we can calculate t[i] greedily: t[i]=floor((t[0]+...+t[i-1])/(k-1))+1.

D: We consider 2 types of good set: First, assume we take node 1 as root, and for any two different nodes (u, v) in the set, u is not the ancestor of v. In this case, we can calculate the number of valid sets by dp: dp[u]=1+prod(dp[v]), where v iterates over all childs of u, and the number of sets of the first type is dp[1]. Second, assume there exist nodes (u, v) such that u is the ancestor of v. In this case, the set must be contained in the subtree of u, and if we remove u from the set, there will be exactly one child of u, such that the set is contained in the subtree of that child. For each edge (u, w), there are dp[w]-1 sets of second type(we need -1 because {u} is already counted as first type).

E: Let mask[j] = the set of paths that the j-th edge is contained in. We can calculate them by brute force in O(n*k). In fact, there can be at most 2*k different values of mask[j]. Then we let dp[mask]= the minimum number of edges we need to color paths in mask, then we have dp[0]=0, dp[mask]=min(1+dp[mask&(~ t)]), where t iterates over all values of mask[j]. Then we can solve the problem in O(k*(n+2^k)).

F: First turn the binary tree into an array by pre-order traversal, and prepend 1 at the front and append C at the end of the array. Then for each maximal block of consecutive -1 in this array, let L be the number before this block, R be the number after this block, and t be the length of this block, we need to fill this subarray by t numbers within [L, R] and sort them in non-decreasing order. By a well-known conclusion, there are C(R-L+t, t) ways to do this. Because sum(t)<=n, we can calculate it directly and solve the problem in O(n).

how to prove

`In fact, there can be at most 2*k different values of mask[j].`

?Let's prove this by induction. Situation for k==1 is obvious. First, the intersection of several simple paths in a tree is empty or a simple path. Therefore, for any M>0, S(M):={j: mask[j]==M} is empty or a simple path. Then when we add a the k-th path, if S(M) is contained in the new path, then S(M) will become empty (and S(M|(1<<k)) will become previous S(M)). If S(M) have no intersection with the new path, it will remain unchanged. Otherwise, S(M) will have intersection with the new path but not contained in it, and this can only occur at two ends of the path. Therefore, the number of different values of mask[j] can increase by at most 2 when we add each new path.

thanks (●'◡'●)

Thanks for the explanations. But I do not agree with some points in this proof (or I may have misunderstood you):

1) Based on S(M) being the set of edges i whose mask[i] is M, "S(M) is a simple path" is not necessarily true. Although S(M) must be a part of a simple path (the intersection of paths in M), but it does not necessarily has to totally cover it.

2) "The intersection can only occur at two ends of the path". We can have cases where 2 paths intersect at their middle.

A case demonstrating the previous 2 points:

If we add the paths [5, 6] and [7, 8], S({[5, 6]}) = {(1, 2), (2, 5), (3, 6)}, S({[7, 8]}) = {(1, 4), (4, 8), (3, 7)}, and S[{[5, 6], [7, 8]}] = {(1, 3)}. Also, the intersection between the 2 paths did not happen at any of their ends.

3) "the number of different values of mask[j] can increase by at most 2 when we add each new path", this is not necessarily true, consider the following case:

If we add paths in the following order: [4, 5], [6, 7], [10, 11], [12, 13], and [11, 12], the addition of [11, 12] introduces 5 new different mask values ([11, 12] with every previously added path as well as [11, 12] alone). And we still have mask values for each of the previously added paths alone, e.g., mask[(2, 4)] = {[4, 5]}.

I think we could rephrase the statement to something like "There's always an order of insertion such that the number of mask values increases by at most 2 for each new added path"

Is this correct though? Assume that we have a tree

1-2 2-3 2-4 1-5 3-6

We have a path 3-4 and another 6-5

In this case, S({5-6}) = {3-6,1-2,1-5}, which is clearly not a simple path.

E big brain, I just did $$$ans$$$ or-convolutions (so $$$k^22^k$$$ total)

Still found it easier than D (probably exactly because I skipped the thinking part)

Could you please further explain your approach with or-convolutions?

Let's solve the following problem: let $$$S$$$ and $$$T$$$ be two families of subsets of $$$\{1, \ldots, k\}$$$. Let's find $$$f(S, T) := \{s\cup t\,\colon\,s\in S,\,t\in T\}$$$.

If we find out how to do this, the original problem is easy: start with $$$S = \text{the set of all submasks for the edges}$$$, $$$T = \{0\}$$$ (or $$$\{\varnothing\}$$$ in the set-theory language). While $$$T$$$ doesn't contain the full mask, increase the answer by $$$1$$$ and replace $$$T \leftarrow f(S, T)$$$.

To find $$$f(S, T)$$$, we just create two arrays of size $$$2^k$$$, fill $$$1$$$ at all positions corresponding to the masks that are present in $$$S$$$ or $$$T$$$ respectively, then calculate the or-convolution of them. Now at position $$$m$$$ we have the number of pairs $$$(s, t)\in S\times T$$$ so that $$$s\cup t = m$$$. If this is not zero, replace this number with one. Since this number cannot exceed $$$3^{20} = 243^4 < 256^4 = 2^{32}$$$, we can calculate this in unsigned ints and be fine (I even calculated it in signed ints, though their overflow is technically undefined behaviour).

for Problem C, I was thinking of the below 2 conditions (t_i is amount bet in ith round):

k * t_i > t_1 + ... + t_i-1 (if at any point we need to restart it covers for previous losses) for all i in 1 <= i <= x

k * (a — (t_1 + ... + t_x)) > a

in F, I guess it is in-order traversal.

I estimated different values of mask[j] $$$k^2$$$ during the contest. (it's much easier to prove)

C problem sucks!

Can anyone explain the testcase "3 3 6" in problem

C?The rationale for that test case is very poor. I was also confused about the same. They are stating that the casino will always play optimally, and so the player will always just break even, if they apply the best possible strategy.

Basically, the casino is rigged against you and it's not a game of luck.

Very poorly prepared problem.

From the statement, which hasn't been modified:

"In other words, is it true that for any integer $$$n$$$, Sasha can make bets so that

for any outcome that does not contradict the rules described above, at some moment of time he will have at least $$$n$$$ coins?"Does this not make it clear that this isn't a game of luck?

I understand it now. It was tricky wording to understand without having context.

same

Suppose we want to guarantee a profit if we ever get a win. This will ensure that we won't play more than x+1 games. Because if we lose all x games, the x+1st game is guaranteed to bring a profit.

Now considering the 3 3 6 case, lets place our bets like this: 1, 1, 2, 2

You can check and see that, if we at any point except for the last one we get a win, we will be in a profit. But what in the last case? If we win on the last bet we are going to be back at 6 chips. That way the casino can keep us in a loop forever, therefore never giving us a profit.

why do we have to make a profit, can't we just break even(no profit no loss).

In other words, is it true that for any integer n , Sasha can make bets so that for any outcome that does not contradict the rules described above, at some moment of time he will have at least n coins.

If you always break even and never make any profit, how can you reach $$$7$$$ coins in the above example?

If you want to bet all at once on x+1, then the casino can let you win the penultimate game; If there is a bet of more than 1 in bets, the casino will keep you losing, and your total amount will still be less than 6 even if you win the x+1 game.

This makes sense , Maybe they should have worded it like a two players playing optimally type problem.

Bets can be placed in the order 1 1 1 2 (repeating this sequence if achieved a win before).

Doesn't this guarantees a win? Probably I understood the question wrong :(

Treeforces

╱|、

(˚ˎ 。7

|、˜〵

じしˍ,)ノ It was a awesome round. I solve 3 problem. I hopefully reached specialist ≽^•⩊•^≼

The integer range check for problem C was

DIRTYbutNECESSARY.The problem C was very ambiguous and confusing. The test cases were poorly explained, and clarification provided extra information not included in the original problem. This should have been a two-player problem where both players play optimally.

Part of the task was understanding that the worst case scenario in a random setup is an adversary.

It was never stated that the task had an adversary. A casino is supposed to be random. If I can break even in the worst case and profit in the best case, then I will eventually profit. It is not stated that the process is not random but deterministic, it is a fault in the problem.

When you analyze an algorithm like quicksort, does the universe tell you there's an adversary making it as unsortable as possible? No, but that's how worst-case analysis ON a RANDOM process is conducted.

Please, do better problem statements.

If I hadn't given that explanation, I might not have been able to understand the C in this game

I am going to be a gambler!

Took me 1 hour to understand C (in fact I used that time to solve D, but couldn't).

Because understand statement is part of solution

So, you didn't think this might be an issue?

If it's difficult to understand what it means to get an arbitrarily large number and what an adaptive strategy is, then you probably just aren't ready for this task.

Correction: understanding

I think I know why the statements were unclear.

Could anyone please explain C? I thought I would bet 1 coin for x times, so after losing x times i have a-x coins. Then i can simply bet the entire remaining amount, right? But the test cases dont match. Someone please help me out!

Me too!

It's worse than Good Bye 2023.

If nothing else, my name is going to be gray (and within 10 rating of green).

UPD: Just looked at it with the plugin, down to 1199 rating...

casino is smart he will only let you loose x-2 times and will make you win on x-1th time so the counter starts again, i realised this in contest but still could not solve it :(

think of it as two player game with condition that player 2( casino ) can't win more than x times

EDIT: added second paragraph

Ouu damn! Didn't think of it that way :')

we have to think that every time, from the 1st to the x+1th time,

if we win the bet we will make a profit, but if we lose, we will lose the least.

And we have to check that we can do this without running out of initial money.

sorry for my bad english.

You're assuming that the casino would make you loose if you bet 1 coin, they also want you to loose as much coin as possible. So what if they let you win if you bet 1 coin so that the streak for x breaks and then they can take the bigger amount of coin.

hint for D pls?

Root the tree at vertex $$$1$$$. Try to find out all the configurations of subtree at node $$$u$$$ such that all upward path to node $$$u$$$ have a maximum count of black vertices as $$$0$$$, $$$1$$$ or $$$2$$$.

For D, I tried to find the number of distinct paths of length in the range [3,n]. For this I copied the code for the problem Fixed-Length Paths II of CSES Problemset Link. Then I subtracted this value from 2^n (Total no of possible sets). But my answer didn't match with sample test cases. What was I doing wrong ?

Number of distinct paths of length >= 3 does not equal to number of subsets such that at least path exists with length >= 3.

l don't like this time in rating:b+(600~800)=c,a=b and c=d

Problem C was like a horror experience

С>D=E=F

In my opinion E>C>D>F. Didn't found that there are just 2*k different masks :(

i dont wanna stay in grey forever :(

Can someone explain the 3rd question of the 4th question, how does Sasha lose? Sasha always plays 1 If the number of consecutive losses is less than 3, he always gets at least 1 point If the casino gives 3 losses in a row, Sasha will have at least 3 coins and get at least 9 points As a result, he can always increas his mony

They don't necessarily lose three in a row.

"He always gets at least 1 point If the casino gives 3 losses in a row"

What If the casino doesn't?

Well, if they don't do this, then we have a maximum of 2 losses in a row, and with the next win, the number of his coins will be -2 + 3

No, after losing a game, the losing streak is reset to 0.

Can you explain more?

Initially, you have streak = 0, money = 6

If you bet 1 and lose streak = 1, money = 5

If you bet 1 and lose streak = 2, money = 4

If you bet 1 and win (the casino can control this) streak = 0, money = 6

It's back to the beginning. :D

Anyone can explain problem statement of D atleast then i could think of solution.

+1

+1.

I will simplify the statement in a more straightforward way.

There is a tree given with $$$n$$$ nodes. Let's say you choose a subset of nodes, then you will mark those nodes in the tree in red, now this subset of nodes will be called "bad" if there is any possible simple path in the tree such that there are more than $$$2$$$ red nodes lying on it.

You have to count the number of subsets that aren't "bad", the subset can be possibly empty.

PS: I also had to read several times to come up with some understanding of it. The terms "city" and "intersections" are confusing together.

Pretty good round, the hardest problem was getting to the round in time

Statements be like:Thanks for the great problem C FairyWinx.

I surely enjoyed the clear problem statement and will cry to bed tonight with a 5-digit rank and -100 delta. Thanks once again.

OHHHH catgirl power! I may become purple this round!

btw thanks for the great round, FairyWinx

Give me some hint for D pls

u can see my code, use dp.

dp[u][i] means in u's subtree (includes u), pathes that start with u has a maximum of i dangerous node (i ∈ {0,1,2})

for the staus's transformation, u can look through my code or just think with yourself.

Code

For me, dp is a lifelong enemy:(

Why do paths that start with root node correspond to number of sets? Are we covering all the paths, what about the ones that do not start at root?

Tree ᓚᘏᗢ

Am I the only one who couldn't find the logic behind problem C?

Youre not alone :)

I like how the contest concluded that the best gift for your girlfriend in Valentine is a binary search tree.

I can understand what C means, but I can't understand D... I guess the questioner wrote the question in his native language and then used software to translate it into English, just like this comment.

The problem statement of C could have been better if it has that announcement in a note

Sample tests for prob D are just rubbish

Literally it took me half an hour to understand what problem d wants to say btw thanku for the contest

Didn't know Codeforces was a gambling site :(

When you participate in a contest you are gambling on your rate.

I'm very glad that I solved CD and nearly F. Thanks for the problemset!

TreeForcesD: I think my solution 246547495 is strange. I did 2 passes of DFS and DP on the tree, and the calculations are not that straightforward.

F: How do you manage to calculate C(C, n) mod M where C=1e9 and M=998244353? Neither preprocessing or Lucas worked. Or is my solution not the intended way? 246561698

Sum n for C(C, n) less N and you can calculate this with for

Try this formula: $$$\binom nm=\frac{n(n-1)(n-2)\cdots(n-m+1)}{m!}$$$

Thank you! I have just completed round 925G and everything I thought of is to copy paste that part.

`IELTS`

forcesyes it's true

There is a participant in my room submitting obfuscated solutions to avoid getting hacked. I think that conduct is against the official rules of the contest. Who should I report this issue to?

In my opinion, dear Fairy Winx should learn human language before learning programming language, so as not to put such unclear and incomprehensible questions in the context.

System test was fast, anyways

Do you know "Ha Jimi" ?

After this round, I will definitely not get involved in gambling.

Get a job Sasha!!And stop Gambling!!

Very unbalanced

I think it will be beneficial for ones who has known about the "doubling bet" strategy to solve C, although it is just the case when k = 2.

D easier than C I think.

I get the error "wrong output format Expected integer, but "2.6917e+07" found" with Problem B in test number 4.

How to fix or avoid that error?

246566145

Transform your answer into integer but not float.

This part you

`cout`

after doing division with`2.0`

, so the result will be a float (That's why it has the e+07 part)I understand this problem now, thank you everyone.

bad statement for problem c

Sasha's girlfriend confirmed imaginary.

Conclusion: Sasha's girlfriend exists only in his imagination (not surprising)

yeah, espe. for coders :)

I think problem C statement is good, at least you can figure it out by yourself that casino isn't always gives you win only after $$$x$$$ loses. Maybe it would be better if it had been written "you don't know will you win or lose, but you guarantee will win after $$$x$$$ loses in a row"

One Moment of Silence for all those who struggled the entire contest in problem-C...

(Just because of unclear statements).

for C just think there is one man who control you lose or win, and you should find a way to get coins more. so, for every bet you should think if this turns you win your coins how to increase. so, if you have lost k-1 coin, you should put 2 coins next time, if you don't do it, the man will let you win and you will get k coins but you have spent k so your coin didn't increase. so, if you have lost b coins, next time you should put b//(k-1) +1 coins. for my code https://codeforces.com/contest/1929/submission/246544539

Great contest ! Any hints for D ?

1) What is a path in a tree?

2) What pairs of vertices $$$(v,u)$$$ should we observe?

This code must get TLE,but why am I get Unsuccessful hacking attempt?

Not all codes with while(1) are unable to terminate...

input 100000000 399999998

On my IDE,it will be TLE.

But in codeforces,it is AC???

I think the compiler option

`O2`

optimized the code.When I set the compiler option

`O0`

, I got TLE https://codeforces.com/contest/1929/submission/246569188But my compiler option O2 optimized the code too.

I also use O2 option but it is so fast compared to O0.

Maybe your compiler options are not working? Could you try

`#pragma GCC optimize("O2")`

at the top of the code?and the code only uses 0 ms.

https://codeforces.com/contest/1929/hacks/983147/test

In my opinion F<<D... So why is a BST written in the statement? Just to make it scary and match our past impressions of the difficulty of problem F?

btw why is C (in F) up to 1e9, not 998244352?

For the C in problem F: Both options "overflow" the binomial, as you need to use the stars-and-bars method, so it does not matter.

Can someone say what really problem C ask for? I can comprehend nothing

in simple terms it's asking can you have infinite amount of coins

If

Dappeared in an Atcoder contest, here's what the statement would've been.Yes, Atcoder is very good at writing statements . Nothing rubbish is written unlike todays C.

can you give me the link to the contest?

I didn't mean that it has appeared in an Atcoder contest. But if it did appear, this is probably how the statement would've looked like.

BTW, I did reword the problem according to this statement in this mashup contest

Oh sorry, i misunderstood your comment.

Bad statements

any hint for B...please

Think about how much the number of diagonals can increase if we color in a single square. Also, think about how to include all diagonals with the least amount of colored squares.

thanks

If k!=4n-2 then the ans is ceil of k/2. If k==4n-2 then ans is (ceil of k/2)+1 because some cells will have only one unique diagonal. Take n = 5 and 1<=k<=18 and draw a grid with diagonals and try to find ans for each k then you will understand what I am saying.

thank you

I really hope that Sasha was able to win the girl's heart.

I recently came with a rule that in a contest when there are multiple submissions then last pretest passed submission will be used for system testing and previous submissions are skipped. In this contest, I submitted 1st question under 2 minutes and got pretests passed (Submission id- 246491221) and i accidentally submitted similar code again after almost 1 hr 50 minutes (Submission id-246561262) and as per rule my 1st submission skipped system testing and 2nd submission got accepted which made my score drop and my rank drop from nearly 3300 to 5330 which will affect my rating.

I wanted to request that there should be some feature to lock any submission you want and not just last pretest passed submission as it is just taking penalties/lower scores without any reason. And also, if no submission is locked then next submission should only be tested if previous submission failed system testing which is done in some of the contests.

There literally is a feature to lock your submission. Furthermore, after this you can read the codes of other people from your room to this problem, and if you think the solution shouldn't work on some test you know, you can even provide the test and get some points if their solution fails!

Ah, I reread your comment and understood that you want to lock a submission that is not the last one

Yes, exactly i haven't locked my 1st correct submission and submitted it again. Then i was trying if i can lock my previous submission but was not possible and instantly my score and rank was dropped.

for Problem C, Are these 2 conditions correct (t_i is amount bet in ith round):

(k — 1) * t_i > t_1 + ... + t_i-1 (if at any point we need to restart it covers for previous losses) for all i in 1 <= i <= x

k * (a — (t_1 + ... + t_x)) > a

How to solve the C? I think binary search