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!
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
sure...
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.
GOOD LUCK
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......
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. ≽^•⩊•^≼
"Давайте продолжим серию анонсов с фотографией авторов :)"
Из предыдущего анонса
РАУНД ОТ ЮРЫ КОТОРЫЙ ОН ОБЕЩАЛ В КОМАНДЕ ОСЕНЬЮ!!
Я сам офигел
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
kawaii neko ^-w-^
As a tester, i wish good luck to all participants.
Sasha, I'll try to help you get her number)
что означает 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 get more of "Good luck and high rating!"
Hoping to do better after a disastrous run of contests.
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?
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
cute catgirl.
New profile picture
catgril !!!
Кто этот прекрасный человек который написал такое в описании раунда? На инфе надо мной весь класс угорал
Looking forward to "Good Luck and High Rating"
Ended up with “Bad Luck and Low Rating”
Neko round lets gooo!
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
I will start from $$$C$$$
Finally, score distribution released
Nice score distribution
Even in kindergarten, Sasha liked a girl.
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
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
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!
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.
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)
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 :(
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 \lt 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).
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.
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
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!
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
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.
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.
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 :(
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:
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?
Am I the only one who couldn't find the logic behind problem C?
I like how the contest concluded that the best gift for your girlfriend in Valentine is a binary search tree.
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.
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
This part you
coutafter doing division with2.0, so the result will be a float (That's why it has the e+07 part)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"
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://mirror.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://mirror.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 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
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.
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://mirror.codeforces.com/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://mirror.codeforces.com/contest/1929/submission/246543979
Can anyone explain me the D question.
Can anyone explain me D
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://mirror.codeforces.com/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://mirror.codeforces.com/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?
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.
No-sigma raund
Why the f is that my problem d was in russian : |
C is nice , bit hard to understand
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.
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
I love the concise statements.
I love the well-bedded difficulty distribution.
D is an easy version of https://atcoder.jp/contests/abc340/tasks/abc340_g. Just set Ai=1.
Is E's hack opened?
I failed Sasha. He will be single forever.
Почему в случае "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$$$, следовательно, ходить по единицам в этом тесте проигрышная стратегия.
Да, я это тоже описал в комменте, но мне уже объяснили в блоге, что я как оказалось неправильно понял условие, я думал, что надо не уходить в минус, а надо было строго в плюс, можешь почитать, если интересно