Neko Nya, Кодефорсес =＾● ⋏ ●＾=
Я рад пригласить вас поучаствовать в Codeforces Round 926 (Div. 2). Он состоится в 15.02.2024 17:35 (Московское время) и в нем вы будете помогать мальчику Саше добиться девочки. Раунд будет рейтинговым для всех участников с рейтингом строго меньшим 2100. И у вас будет 2 часа, чтобы решить 6 задач.
Тута благодарность всем соучаствуюшим в раунде:
- Самому милому координатору Artyom123. (Не обижайтесь оставшиеся)
- KAN, geranazavr555, MikeMirzayanov за ЛУЧШУЮ платформу.
- Легиону тестеров: A_G, AgafonovArtem, Alexdat2000, Vladithur, wuhudsm, petyb, induk_v_tsiane, sevlll777, mz1, SomethingNew, AVdovin, NewLul, damirsit, skylak3_3, Andreasyan.
- Также этому замечательному человеку за неоценимый вклад в раунд teraqqq.
Жду всех на раунде >~<
UPD: Разбалловка: 500 — 1000 — 1500 — 2000 — 2500 — 3000
UPD2: Разбор
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 :)
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 intensifies
sure...
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 Distribution of the round?? Score -> Updated
uwu
Kudos to the authors for continuing the trend of attaching their photos!
OWO
stealing my meme bro?
I don't mind
nya
scoring distribution???
Пришлось поменять аватарку на Тайлера Дёрдена для этого раунда. Stay hard! Stay focused!
Няшкаааа
~ Огоонь! ~
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.
Score distribution? ≽^•⩊•^≼
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!!!
GOOD LUCK!!!
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 .
что означает neko nya?
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 get more of "Good luck and high rating!"
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
В итоге эта девушка окажется 40-летним мужиком, решающим этот контест в подвале своей мамы
Doesn’t the average tester rating seem quite high? :)
Hopefully I can do the first four problems！
I hope everyone has a good score.
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
I see that FairyWinx has created a round, I'm happy to register.=＾● ⋏ ●＾=
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
All the best
Neko round lets gooo!
ฅ(=･ω･=)ฅ
As a particapant i alreary know this is gonna ne a great round
Good Luck to all the participants.
lovely score distribution (´･ω･`)
I need someone to help me,as sasha
As a participant I like the vibes
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
anime = gay
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 max k 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
very bad contest "A7A" very bad description
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 BULLSHIT going 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 correct This is disturbing
cout << 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 D can 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.
I wonder why D was very standard? It was easy to see dp can be use like dp(i,j) where j={0, 1,2). But according to your dp definition dp(i, 1) it was like simple path starts from i then go to the below leaf node having only one dangerous node. while my definition was simple paths that passes from current node i and have only one dangerous node. Due to this change you are making combination of childs in dp(i, 1) and this also helps in later calculating i parent node dp(par, 2). But according to my definition I have to make those combination in dp(i, 2). B/c if I will consider more than 1 children having 1 node in dp(i, 1) Then it will become 2 dangerous nodes as my definition says passes from current node. But due to this it is missing some cases in calculation of i node parents dp(par,2).
So my point was many people could come up with my dp defintion as it give a sense that we are considering all the simple paths. Because you are only considering paths starts from node i . Here's a comment Link of someone having same assumption. I think I can AC it with one more array for storing those combinations. But it will become more complex. So Please could you share some problems using this same thinking difference I can relate it with and consider this as standard problem .
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 DIRTY but NECESSARY.
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.
B — непонятно, зачем было разделять рисунок на две части, когда можно было просто нарисовать все диагонали на одном квадрате.
С — нужно было в условии написать, что казино само оптимально выбирает исход всех ставок, это бы упростило понимание.
D — просто ужасная формулировка, понятен вопрос задачи, но непонятно, как читать условие.
Читать условие надо сверху вниз и слева направо
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.
The problem statement of C could have been better if it has that announcement in a note
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!
TreeForces
D: 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.
IELTSforcesyes 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.
for c explain why 3 3 6 is NO: 1-you put 1 coin, if you win you+3-1, you+2 if you lose: you put 1 coin, if you win you+3-2, you+2 if you lose: you should put 2 coins this time, because if you put 1, he let you win, then you+3-3, it means you didn't get anu coin, that why you can't get n. if you win you+6-3, you+3 but if you lose, you have only 2 coins to put you will+6-6 so there is no way for you to make coin must get up, so is no
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 still cant comprehend problem C . It should have been bit more clear .
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
coutafter doing division with2.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).
Very poor statement of the problem
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.me/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
O2optimized the code.When I set the compiler option
O0, I got TLE https://codeforces.me/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.me/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 D appeared 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
Test data for D are weak. Many people just printed
ans + 1or evenans + n + 1without performing modulo, but they still got accepted.Here's a hack that creates an answer that is exactly 0 — or 998244352 + 1: https://codeforces.me/contest/1929/hacks/983200
E>>F
In problem C , how for test case : 2,3,15 , answer is yes ?
betting sequence 1 2 4 8 in any scenario you you atleast once have total coins > initial coins so after that you can repeat the sequence and get as many coins
Not clear, what 1 ,2 , 4 ,8 sequence here are you referring to??
this is a no. of coins you bet each round
someone please explains the problem C.
you can't lose x times continuously and win/lose is random so your win expectation is >money you've lost. do this x times if your money isn't 0 you must win money.
I think that problem C was not clear before the announcement was made and it became clear afterwards
Can C be solved using Binary Search??
Yes it can. (but not necessary)
https://codeforces.me/contest/1929/submission/246543979
can't understand the mean of C
Can anyone explain me the D question.
Can anyone explain me D
"Sasha" lol, it reminds the character "Sasha Blouse" from AOT.
I feel like the problem set is rather imbalanced.
A B C all math
D E F all trees
also E, F is of similar difficulty (from number of solves). Should make F harder I think.
Hey guys, I saw this blog post about problem C. This is really unfair for many of us who legitimately participate in contests on our own. https://codeforces.me/blog/entry/125935
I did problem C with what seems a solution identical to the other ones, but I kept getting Incorrect Answer 7, can someone please explain what is wrong? Thank you
https://codeforces.me/contest/1929/submission/246537505
If I am not mistaken, my code failed on the test 2 1 6 for which my code wrote YES, but the answer seems to be NO, can someone explain this?
i am new at CP ,was this contest rated because i didn't got any rating.
The value of
prev_sumcan overflow out oflong longdatatype. You need to break early ifprev_sum > aat any point.Ow thank you very much!
couldn't escape expurrt after spending first 30 min trying to understand D >;-;<
Although I was not a participant in this round, the Problem and sample analysis of Problem C was terrible and bewilderingly.
luv u in:)
No-sigma raund
Why the f is that my problem d was in russian : |
C is nice , bit hard to understand
quite hard ....
deleted content
Problem D is a good introduction to DP on Trees. For training purpose, I added the problem to a mashup and simplified the problem statement, so that it's easier to remember it by name.
You can access it here.
"Please do not ask questions about test cases in the example that are not explained. We cannot answer them, as it is a hint to the solution of the problem."
this was the most naive response I have ever seen. I believe I'm not the only one that thinks that the statement was a real mess.
As a newbie my small brain got fried trying to understand the question no C :))))
Problem C statement was not clear ...
Me to ques C ---> Link ;-;
Problem C video solution with live coding: https://youtu.be/XRjHt1rnzqs
I spent too much time on problem C and Did not attend problem D which was easy . Problem statement was not clear and ended up with negative rating change.Regret giving this contest(T_T).
great contest, and love the catgirl!
I've got no idea why my code for D doesnt pass the official test.
It says that it expects output '12' (instead of '11) on test number 2.
But when I run this test locally I get result '12' :O
We need more anime rounds. Please naruto
I love the concise statements.
I love the well-bedded difficulty distribution.
Sasha Lol, it reminds the character "Sasha Blouse" from AOT.
D is an easy version of https://atcoder.jp/contests/abc340/tasks/abc340_g. Just set Ai=1.
Is E's hack opened?
dislike! dislike! dislike! anime Haram!!!!! Don't put anime
I failed Sasha. He will be single forever.
this c i feel bad QAQ
Can anyone please tell me why my answer is wrong?
In the statement of problem C: "Note that the bet amount must always be a positive (>0 ) integer" and "Sasha also knows that there is a promotion at the casino: he cannot lose more than x times in a row." As we can see.. two very clear RULES. the statement also says: "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." Meaning, the casino must never let his money reach 0 -THE FIRST RULE IN GAMBLING IS THAT YOU MUST HAVE SMTH TO GAMBLE WITH OTHERWISE YOU HAVE LOST-, and if he reaches the limit of losses in a row, the casino must make him win -THE MADE UP RULE OF THE GAME, BUT YET STILL A RULE-.... And as we saw in the testcases along with the tutorial, when his sum of money reaches 0 while his losses in a row aren't past the limit yet.. the game ends... In a logical world.. Sasha will always win... cos... "any outcome that DOES NOT CONTRADICT the RULES described above" but the tutorial, the judging server, as well as the test cases proved differently.. I hope for less ambiguous statements in the future. edit: I read the problem after the contest and the adjustments were not yet added to the statement..
shinonome ena???
Почему в случае "3 3 6" ответ "Нет"? Может кто-то найдет ошибку в моей логике, но смотрите. Саша знает, что он может проиграть не более X раз подряд, стало быть он точно знает, что если он уже проиграл X раз подряд, то следующая ставка будет ТОЧНО выигрышной. Тогда давайте ставить 1 монетку всегда, кроме того случая, когда игра ТОЧНО выигрышная, будем обозначать П — проигрыш, а В — выигрыш. Рассмотрим 2 случая, когда Саша проиграл X подряд и X+1 раз будет точно выигрышным, и случай когда ТОЧНО выигрышных ситуаций нет. Пусть у нас идет последовательность ПППВ, мы проиграли 3 подряд, значит следующая игра выигрышная, значит Саша может ставить на нее все деньги. Как говорилось ранее, на игры которые не точно выигрышные мы ставим 1 монетку, тогда за 3 проигрыша мы потеряли 3 монетки, 6-3 = 3, тогда мы ставим 3 и выигрываем 6, в сумме имеем 9, то есть, мы ушли в плюс. Теперь рассмотрим ситуацию, когда точно выигрышных игр нет, тогда мы будем ставить всегда 1 монетку. Несложно заметить, что худший случай — ППВППВ.... Тогда перед каждой победой мы проигрываем 2 монетки, 6 — 2 = 4, имея 4 монетки мы ставим одну и выигрываем 2, итого мы имеем опять 6 монеток. В условии сказано, что Саша должен иметь возможность бесконечно не уходить в минус "Другими словами, правда ли, что для любого целого числа n , Саша сможет делать ставки так, чтобы при любых их результатах, не противоречащих описанным выше правилам, в какой-то момент времени у него было хотя бы n монет." В чем я не прав?
Казино делает такую подставу: вместо ПППВ оно делает ППВ...
$$$6 \rightarrow 5 \rightarrow 4$$$, два раза проигрываем, и тут случается подстава:
$$$4 \rightarrow (4-1) + 1 \cdot k = 3 + k$$$ (победили)
Если $$$k=3$$$ или $$$k=2$$$, то мы не уходим дальше $$$6$$$, следовательно, ходить по единицам в этом тесте проигрышная стратегия.
Да, я это тоже описал в комменте, но мне уже объяснили в блоге, что я как оказалось неправильно понял условие, я думал, что надо не уходить в минус, а надо было строго в плюс, можешь почитать, если интересно
The system has suspected of me copying the code for problem C. I think it is because I have never solved C in div 2 before or whatever the reason may be. I was pretty close to solve C in the previous div 2 as well. Anyways here's proof I did not cheat
I had seen similar questions before, and knew it was a gambler's ruin problem https://youtu.be/Ne2lmAZI4-I?si=C6cn7-NH0nUfwroV Pretty popular video on the problem. Once that was known, I only had to check if I had the required amount of money to bring back my amount lost after every gamble. And the most I could lose was x no. Of times. So that's only what I've done. I don't know how it was similar to other people's code but it's only normal for them to write in Java with the same logic and very little scope of picking other variable names. And Gpt will write the same code for the command I have written above. It is that simple. I rest my case. I hope I am heard.
Same exact situation for me, except I never saw a video about it. Incredibly frustrating.
Great problemset
Does rating will change after this contest ?
Ok, same problems. thank you, i'm still scared
I got my problem removed for rules violations despite the fact I did and do not share or receive solutions. This is where these solutions probably came from https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/.
wuw