Привки, Кодефорсес (ﾉ◕ヮ◕)ﾉ*:･ﾟ✧
Igorbunov и я рады пригласить вас поучаствовать в Codeforces Round 777 (Div. 2) (шутка про казино), все задачи которого будут про маленькую девочку Мадоку. Он состоится в 11.03.2022 17:35 (Московское время). Раунд будет рейтинговым для всех участников с рейтингом строго меньшим 2100. И у вас будет 2 часа, чтобы решить 6 задач.
Также хочется выразить благодарность следующим лицам:
- Нашему милому координатору Artyom123.
- Милым тестерам за милый фидбек по милым задачам: FelixDzerzhinsky, lesssia, eyakm1, _Vanilla_, morzer, welleyth, TeaTime, Dart-Xeyter, Kon567889, Renedyn, Pechalka, talant, Ziware, vaaven, princebelkovetz, Alexdat2000, crazyilian, antontrygubO_o, generic_placeholder_name.
- MikeMirzayanov сами знаете за что.
- Нашим милым матерям.
- purplesyringa за улучшение английских условий.
Желаю высокого рейтинга, а также надеюсь, что я помогу вам хоть на немного отвлечься от не самых лучших новостей (❤ω❤)
Разбалловка: 500 — 1250 — 1500 — 2000 — 2500 — 3000
UPD1: Разбор на русском
UPD2: Поздравим победителей контеста
Div 1+2
| 1 | jqdai0815 | 9457 |
| 2 | Geothermal | 9219 |
| 3 | rainboy | 8649 |
| 4 | End. | 8529 |
| 5 | kshitij_sodani | 8250 |
Div 2
| 1 | shnirelman | 6955 |
| 2 | zzfzzfzzfzzf | 6558 |
| 3 | Kaname-Madoka | 6539 |
| 4 | peuch | 6317 |
| 5 | rsy | 6301 |
cute ^.^
(´･ω･`)
As a tester of one problem I can say that only anime girls can solve all problems
May I become a cute girl if I solve all the problems? >_<
Yep! >_<
We desire that (σﾟ∀ﾟ)σ.
You still cute though ;)
looks like I'm not anime girl((((
can i get an UWU for solving till D
Great contest!
I would also like to express my gratitude to the mother of princebelkovetz ♡
And also to all the Mothers.
As a tester, I am sad I can't participate in this awesome round (ಥ⌣ಥ)
Good luck in participating in round!
Hoping you wouldn't get -100 contribution after your first round, as it happened to ilyakrasnovv before
hoping you wouldn't get -100 contribution after your second comment.
As a tester, I recommend you to read all problems
a chance to be close to specialist :)
GL
почему мою мать не поблагодарили?
Good luck everyone! I won't wish everyone nonnegative delta because that would make the round unrated :P
мегахарош
madoka is a cute magical girl anime suitable for little children! the design and atmosphere of the show is so bubbly and warm! the girls are all lovable in a world of happiness!
Of the minuses, almost everyone was simply killed there :/
You would probably wanna spoiler that xD
is this minus applicable to the round?
Are you sure?
As a tester... Oh, wait, I wasn't included in testers list. Well... So... Just good luck everyone!
Fixed=)
I see that the authors are very cute! UwU
Измените FelixDzerzhinsky цвет на циановый.
Нет (там должна была быть посхалка, но координатор заставил покрасить красных тестеров в красный, так что не получилось)
Сейчас рейтинг дадут и тебе придётся извиниться :)
cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute
Upvoted for the Madoka Magica propaganda
Why so cuteeeeee >~<
Madoka!!!
nice testers list
╱/( ◕‿‿◕ )\╲
Madoka/se
Puella Magi Madoka Magica(魔法少女まどか☆マギカ) is the best anime I've ever seen.I hope the round goes well.
Same. I have yet to seen a better anime than madoka magica.
please motivate me i am tired of getting wrong answer and lacking the will power to start over again and again
It's a sport and we play sport for fun, we don't have to be good at it untill or unless we want to be professional player. So enjoy buddy...
Sorry for this rude behaviour :/ I apologize
По-по-поднял рейта (у!)
Стали другими дела
Стали считаться со мной
Знают, кто теперь я
По-поднял рейта
Машина в линию дала
— У тебя талант, братан
— Ка-ка-какой?
— Решать онлайн! (Решать онлайн!)
Все говорят: «Гена, а как поднять рейта?»
«Куда нажать?» — «К-К-К-КФ-зино» три топора
Я апаю и не сливаю
То, что поднял вчера
Поймал удачу и держу за оба крыла
«КФзино» три топора
На-на-началась игра!
Все по-чесноку
Если поднял
Отгрузят рейта
Дёрнул за канат
И макака поймала банан
Сегодня я гуляю (Сегодня я гуляю)
И рейт не влазит на сайт
Жестоко навалил
aww >_<
expecting a cute contest
Gonna use baryon mode then!!! First contest in expert yay
goofy ass announcement made me skip round
Very rude, mihai ♡(ӦｖӦ｡) uwu
Why didn't you guys downvote this comment? Don't you respect cute anime girls?..
no, no we dont
stfu furry
Not everyone likes that, bro.
stfu furry anime girls
Who is Madoka
https://myanimelist.net/character/37832/Madoka_Kaname <3
I hope I will become Candidate Master tonight UwU
Artyom123, will you marry me?
( ❤ ω ❤ )( ❤ ω ❤ )( ❤ ω ❤ )
777 is a good digital.I think the digital will appear in problem. Good luck everyone !
It is guaranteed that the sum of the values of n and the sum of the values of m for all test cases do not exceed 777.
in problem b do not exceed 777
Hope the problems will be as cute as Madoka ^v^
I love this contest! Good B C D
Wow! I really like this anime! My avatar is even Homura (cp of madoka >_<). Hope everyone has a happy round!
expecting cute statements like the cute blog
People with high rating in this contest will automatically become magical girls to save the world!
Nice meme.
Problem "B" has a score of 1250 where "A" has a score of 500 !!! This would be great for those who will start with "B" and score as quickly as possible.
Thank you for sharing this AHMADUL!!
Problem F has 3000 score!!! This would be great for those who will start with "F" and score as quickly as possible.
well... let's say you can solve A or B on 5m, and the other on 10m.
B first -> 1250-penalty*5+500-penalty*10=1750-penalty*15
A first -> 500-penalty*5+1250-penalty*10=1750-penalty*15
no difference XD
Actually the penalty of a problem per minute is dependent on the original point value of the problem. There is a subtle difference. But it is probably unnoticeable, maybe just ten points or something more, even less than a penalty submission.
I have already fallen in love with this little girl named Madoka. I hope she will bring a great happiness to me in this contest.
FBI open up
No worry, those Russians, who are not involved with the war, have my full supports.
Good luck and high rating!
disgusting
FU ANIME HATERS!!!
I want to comment here so badly and I want to be familiar with you all.. But I am afraid of getting downvotes in my comment. I have already negative contribution. I am sad!
to tears
Saluting cf for organizing so much contests
Че за аниме вокруг.
Dear everyone, I'm very sad right now because of my powerless. I have gone through my examination of national olympic about CP. It's not hard but … I'm really hopeless.
Why make so confusing statements?
after reading statement of D 10 times, i can confirm i still didn't get anything. you gotta have peak mathematical reasoning to actually understand that.
yeah...I wrote at least 3 versions of code before I realize what it really means.
She: I hate it when you can't catch up on my hints.
Also, the hints she gives : statement of D.
Had a stroke trying to understand the problem statement of B
same here...esp the third test case
its not good to put such big implementation problems in A B its hard for new coders and newbies/pupils to implement that much
implementation is a secondary thing..first thing is itself the language of question.
I struggled so much in B,and I felt that C is much easier than B, anyone else?
but overall I liked the problems!
How to solve D?
It felt like a heavy case work problem to me ;_;. Though maybe it has a simpler idea
In Problem D I calculated how often you can divide $$$x$$$ by $$$d$$$ , called this amount $$$c$$$ and called the residual $$$r$$$. So $$$r \cdot d^c=x$$$ and $$$d$$$ does not divide $$$r$$$. Then I checked, whether $$$r$$$ and $$$d$$$ are prime. Then I had a huge casework. Most of the cases were simple, the most difficult one was $$$d$$$ not prime, $$$r$$$ prime and $$$c=3$$$.
But somehow I still must have had an error in my reasoning... 149309714
Edit: Oh, I forgot, the first (annoying) step was parsing the task. $$$g$$$ is a good number if $$$d$$$ divides $$$g$$$. $$$b$$$ is a beautiful number if $$$d$$$ divides $$$b$$$ but $$$d \cdot d$$$ does not divide $$$b$$$. You need to find two different sets of numbers, that are beautiful and multiplied together yield $$$x$$$.
Edit 2: Found my mistake. When searching for factors of $$$x$$$ by iterating $$$i$$$ from $$$2$$$ to $$$sqrt(x)$$$, then not only $$$i$$$ is a divisor of $$$x$$$, but also $$$x/i$$$ ... Brainfart.
"Аррр, тысяча ифов!". Seems there is no straight translation of it. I think, the closest one is "Bloody hell(ifs)". Thank you
Yeah, as long as it solves the problem they are fine I guess. I wasn't happy either, trust me.
And I speak fluent ukrainian so I got the gist also without translation :D But is this some kind of common saying/insider? Never heard it before.
How to solve C -.-?
Notice you only need to do [0, 1] operation either vertically or horizontally (chessboard of size 1x2 or 2x1). Do this backwards for every row and column where there is a black cell. Edge case is when top left column is black.
DANGGGGGGGGGGGGG, I didn't think of using anything smaller than 2x2. Thanks.
Notice that the cell at (0,0) can't be 1. In all other cases, if cell (i,j) is marked '1', then you can take a window of size (1x2) or (2x1) on the cells (i,j-1),(i,j) or (i-1,j),(i,j) respectively and then color it like a chessboard.
If grid[0][0] is black then answer is -1.
Otherwise answer exists always. To color a cell (i,j) black apply operation (i-1, j, i, j) or (i, j-1, i, j). To color a cell (i,j) white apply operation (i, j, i, j).
The $$$2 \cdot 1$$$ and $$$1 \cdot 2$$$ rectangles paint the cell to white and the bottom/right cell to black. These rectangles are enough. Iterate from bottom/right to top/left and set all cells to corresponding color, except the $$$(1,1)$$$. Notice, that this cell is always impossible to paint to black. This is the only case, when the answer does not exist.
Note that if the first cell of the table is 1, then answer is always NO, as it is impossible to paint it black.
Now each and every other cell can be painted black.
1)for cells not in first row by taking that cell and cell left of it.
2)for cells in first row except 1st cell, by taking that cell and cell above it.
these paintings should happen in reverse order so that the latest chosen color is considered
any
hintabout how to solve D?if you understand the definition of beautiful numbers well, then it is pretty easy.
Is this what had to be understood?
for beautiful numbers,
b%d == 0 but (b/d)%d != 0where b is beautiful numberIf yes, I still couldn't get further approach.
yes u got that right
so now from the definition if x is beautiful number then ans is no
now we can write x = d^n*t (where t may be prime or composite) ans n > 1 now if t is composite then ans is yes (bcz we can split t in its divisor to write x in different ways) else we have to split d into its divisors ( there is one more case to consider, i leave it to you to consider :P)
Extremely helpful, thank u
how to divide x into multiple of beatiful numbers? first, recursively divide x by d. then check the left number. Now you have one candidate if you get at least 2 d. Then, check the left part y. if y is not a prime, you succeed. if y is a prime and d is also a prime, you fail. Now the only left case is y is a prime and d is not a prime. if x has at least 3 d, you can try split d * y into several parts, so that each part could not be divided by d.
Could anyone explain why was output of 1000 10 yes whereas 8 2 is No since 1000 =10^3 8=2^3 ?
1000 = 10 * 10 * 10 = 20 * 50
1000 = 20 * 50 = 10 * 10 * 10 8 = 2 * 2 * 2 = 2 * 4, but 4 is not beautiful
for 1000 10 two possible combinations are [10,10,10] and [20,50]
Implementation forces...
I agree this time. B's code is more than A+B+C in usual.
Bruh, B is very easy to implement (just check if there exists 2x2 square where sum of elements is equal to 3).
nice observation, but solving B in a straighforward way is implementation heavy
Part of problem solving is also finding a nice way to implement solution :D.
oh, I didn't think about that. I used a quite complex solution... anyway it survives from system testing...
Oh, dang, nice!
GridForces
CasesForces
The whole round is not bad,but I thought that D is a little troublesome :(
I feel the same（
f**k the D
Agree, spent half an hour on finding two small bugs in D. Kind of a boring problem.
Looking for four small bugs with four "Wa on #2"
I have also spent about 40 mins,so that I didn't finish my E in time :(
I have to say that I feel not good about D which cost me one hour to solve it.But it's laudable that the pretests are strong and few people FST.
With the power of the girl Madoka, I can finally reach Codeforces purple
According to the Google Chrome extension I should go to 1919 rating :-)
Well I should sleep now I don't want to wake up my mother in the middle of the night, I am from Hong Kong. Good night!
HK ?
Hong Kong
Thanks for good tasks. Especially for task E:)
Me in this contest
This is not the first time I notice that building binary jumps is so satisfyingly short in Kotlin:
what was crux in problem b? any hint?
If any 2x2 square contains 3 ones, then it's NO.
Can someone explain the last test case of problem D .
4^3=8^2
We have $$$x = 2 ^ {14}$$$ and $$$d = 2 ^ 2$$$. The possible divisions are $$$x = 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 = 2 ^ 2 \cdot 2 ^ 3 \cdot 2 ^ 3 \cdot 2 ^ 3 \cdot 2 ^ 3$$$.
Igor_Parfenov But $$$x = 2^2.2^2.2^2.2^2$$$ is not a beautiful number as we can represent it as $$$4.4.4.4$$$
Hey! Thanks I got . I had missed the part that $$$x$$$ can be broken into multiple beautiful numbers.
is there something wrong with the last eexample case of problem E？
Problems B and C should have been swapped.
I think {2^2, 2^2, 2^2, 2^2, 2^3} and {2^2, 2^3, 2^3, 2^3} are the same, because this two "sets" are both equal to set {2^2, 2^3}, but the solution must distinguish those, so for X=2^11 and D=2^2, the answer is Yes...
that was the fastest system test i've ever seen
Can someone explain the last test case of problem E?
ok.im wrong.the last test case is right.
A backtracking solution for D passed in 62ms: 149323602. Is it possible to hack it?
Can You explain your solution? I am new to backtracking technique.
I think it's very similar to jqdai0815's solution described here, but without memoization.
I sort the beautiful divisors in decreasing order (increasing
got TLEworks too: 149357544), then try to take or skip each divisor recursively while maintaining the product of the taken divisors. A divisor can be taken multiple times. The product should always be a divisor of x (if not, return 0).It was a very nice contest :).
When I realized the solution for problem E, I was all https://www.youtube.com/watch?v=cDu-2h8ZDhI
Thanks to problems B and C, and my overwhelmingly poor observation skills, I am going to receive my 7th consecutive rating drop.
RiddleForces
Solution video for A-D for anyone looking
When you realise that ...Total time spent reading statement of problem B > Total time taken for system testing
UPD: Oh, it's just the same as solution 1 in the editorial. And I thought it was not the intended solution.
My solution to D:
To avoid the casework, we can simply count the number of factorizations and check if it's greater than $$$1$$$.
We can consider all the beautiful numbers those are the divisor of $$$n$$$, denoted as $$$d_1, d_2, \dots, d_k$$$. And then it's a standard knapsack-like problem.
Let $$$f_{i,j}$$$ be the way that we only consider $$$d_1, \dots, d_i$$$, and the product is $$$j$$$. Like knapsack problem, we have $$$f_{i, j} = f_{i-1, j} + f_{i, j/d_i}$$$. We only need to consider the product $$$j$$$ that is the divisor of $$$n$$$ here. So the time complexity is $$$O(d(n)^2)$$$.
The time complexity is not good. But nobody likes casework, right?
RiddleForces
This is a test case for D that should fail anyone who used an O(n) algorithm for checking primality as opposed to O(sqrt n)
https://codeforces.net/contest/1647/submission/149344533
why runtime?
the problem is here:
what is a problem, and what have to do to solve this problem plz help me out
'a' is vector of 'n' strings, each of length 'm' i in 0..n-1, j in 0..m-1 'a[j][i]' is trying to read data outside the array boundary
then what should i have to do to run this same code plzz edit my code my send me plzzz
149491731
i cant get your logic ...
see editorial
One of the best rounds I have ever seen!
Здравствуйте! Требую вернуть мне мой рейтинг так как считаю неправильным считать что моя посылка с номером 149283145 похожа на посылку 149275798. Возможно коды могли быть похожи из-за того что у нас одинаковые идеи решения или из-за того что пользователи чей код похож на мой могли скопировать мой шаблон из вкладки "Статус"-а. Прошу пересмотреть этот вопрос
Например посылка 148598512 имеет небольшую схожесть с кодом который обвинён в списывании и возможно именно из-за этого они кажутся похожими.
I received two messages saying the following:
"Your solution 149270007 for the problem 1647A significantly coincides with solutions timaktimak/149265121, ylc0/149270007."
"Your solution 149280463 for the problem 1647B significantly coincides with solutions ylc0/149280463, timaktimak/149289518."
I am confused as the answers were indeed written by me and that the message says the answer coincides with itself. I would really appreciate it if someone can tell me what is going wrong here.
Edit: I now understand that the message is listing the coinciding solutions, after looking at the solutions. I think it is just a pure coincidence of a similar method, and there were still differences, as well as more differences in q. C. I hope this can be moderated, I have local version history on my IDE avalible if needed.
Appeal against plagiarism
I would like to point out that I've received an email from CF System that my submission significantly coincides with another one submitted during the contest by ktk5901.
While the two submissions do look very similar (surprising!), it's purely a coincidence since Problem A is very straightforward and a simple one (not so surprising). There was no intentional or unintentional leakage of either of our solutions.
Hence, would like to appeal against this accusation and request the system to process both submissions without considering it a violation.
Thanks.
big fan magaaaaaaaaaaa
nice contest
For Problem A, writing char by char doesn't make it pass the time limit (eventhough O(n/3) implementation) (check my submission here). I think the time limit is tuned to match only some implementation styles.. is it?
EDIT: even writing 2 chars at a time didn't pass the time limit (my code), maybe C printf is too slow?
I am not sure if vfprintf is buffered or not, but if it's not, then it's probably the reason of tle.
I tried solving problem D before reading A, B and C. But I failed because problem D is too difficult to consider all situations. Anyway, thanks for such a good round!
Madoka!!!