Hello, Codeforces!
I am happy to invite you to Codeforces Round 771 (Div. 2), which will take place on 14.02.2022 17:35 (Московское время). The round will be rated for participants with rating lower than 2100. You will have 2 hours to solve 6 problems. The problems were authored and prepared by me.
I would like to thank the following people who made the round possible:
- Artyom123 for coordination, help in problem preparation and translating the statements.
- KAN for helping with round preparation.
- geniucos and spatarel for discussing problems with me way before the round was proposed.
- gamegame, Kirill22, AlexLuchianov, Monogon, wxhtzdy, generic_placeholder_name, BlueDiamond, Devil, Ziware, Utkarsh.25dec, TeaTime, null_awe, manish.17, gojira, shishyando, snowysecret, ak2006, namanbansal013, viovlo and sus, for testing and providing valuable feedback.
- MikeMirzayanov for great Codeforces and Polygon platforms.
I hope you have no plans for Valentine's Day find the problems interesting and enjoy the round. See you in the standings! ❤
Scoring distribution: $$$500-750-1250-1750-2500-3250$$$
UPD: Thanks to ak2006, video editorials for some of the problems will be available on his channel after the round.
UPD: Editorial is out!
are you cursing us
Emotional damage.
...
My valentine day ended at a good note (+101 predicted by cfpredictor), thanks for the amazing problems atodo,Artyom123 and all the contributors of this contest.
hhhhhhhh
Sorry but I have plans for Valentine's Day — participating in your round! ❤
Do Programmers celebrate valentine's day? :)
Yes lucky ones
Looks like the Codeforces Round 771 will be my Valentine this time:)
As a tester, good luck and enjoy problems!
My plans for valentines day were to take this contest.
Now that I got the notification that I tested it, I no longer have plans :(
Good luck and have fun to the rest of you.
maybe now you will have enough time to spend with raingirl
I hope you have no plans for Valentine's Day .
Now Codeforces is also playing with my emotions :(
I will remember this valentine for my color change :)
Nicee :)
sorry losers, I have plans for Valentine's Day :>>
me too =)))
Nice ! Contests without dumbs like you are more interesting :)
I am not a Proctologist but I know an asshole when I see one.
my man, what is wrong with your username?
I am not a Proctologist but I know an asshole when I see one.
Probably he sees his own username?
I hope your partner ditch you before the contest starts.
That's why you are grey
Please stop daydreaming on codeforces.
Wait, What's Valentine's Day?
Expert (my ex) ,i hereby propose you to be mine again .❤
Hopefully ,i won't FST on some problem and regain my love (expert) back. Probably a happy valentines for me.
Sorry but I have plans for Valentine's Day
Valentine's day is for Div 1 only.
No Valentine's day -- lets write codeforces contest!
Codeforces Single's Round.
SingleForces
Nicee
Virginforces
This contest may be easy than previous contest
She left me because I'm still newbie. :))
PinkieRabbit pls stop participate div.2 round to enjoy Valentine's Day with me because it's unrated for you but I'm important for you!
Hopefully, I can get back to specialist :)
on this brilliant ocation of valentines day :)
Will it contain any interactive problem?
Goodluck at Valentine's Round #1
I hope I won't need my registration for this round and will enjoy the date with my gf...
I rather prefer cf rounds than a piece of chocolate! This round's a such nice present for me
I'm having a plan on Valentine and will also participate in the round.
Petition to rename contest to:- Singles Counting contest for cf
This round is like my Valentine's Day now see my Valentine goes good or bad
Same here, I hope I become green this Day. And good luck to all...
Kitna juth bolenge ap
I have plans, it's my birthday!!
I
have no plans for Valentine's Dayhope problems are interesting! ^_*Will AI participate in this round?I guess AI dose not have a girlfriend.
Considering that AlphaCode is pre-trained on natural language processing models, I guess we could find a way to ask AlphaCode whether they have a girlfriend and it's likely their answer would be true :|
Maybe he will be hanging out with google assistant on the google cloud :)
On February 14, 1946, the world's first general-purpose computer was born at the University of Pennsylvania in the U.S. Please spend more time with your computer on this special holiday!
bad: Have a meal with bf/gf
good: Take part in contest!
EVEN BETTER: HAVE FUN IN THE CONTEST WITH YOUR BF/GF!!!
As previous contests shows: [](https://codeforces.net/blog/entry/57721) [](https://codeforces.net/blog/entry/50404) [](https://codeforces.net/blog/entry/23515) [](https://codeforces.net/blog/entry/6677) Programmers usually don't remember the festival unless the announcement notices it...
So plz don't mention it next time(
Happy
Valentine'sContest Day !Yeah yeah you are right. I dont have any plan tonight except for the contest because no girls will like an anime-fan boy. : (
thx, am on the cliff of leaving problem solving, but i will keep going forward now
When your kid from the future comes back in time and threatens you to work hard, so that he can have a better life.
AIs have plans for Valentine's Day, so they won't participate in this round
what a pity！
In fact, my girlfriend's name is codeforces.
Sorry to say, But I spent my most of time with codeforces only. (:
Let's see if Valentine brings some good fortune for us.
Thanks for arranging the contest on valentine's day. Single me at least find something to have some fun and make my day memorable.
Recently i came across the problem "Long Comparison" . Since i am new to competitive programming , i am solving more new questions to build my problem solving ability . Now when i submitted solution to this problem with my own approach , it gave "Run Time Error" with "Exit Code 3" . Can anybody tell me what is going wrong with the approach which i have submitted .
Problem : 1613A - Long Comparison My Submission : 146344211
Please give your precious advice .
Hi, next time you can check the editorial of the contest, there is a tutorial button in the downright of problem page.
About your submission, since $$$p$$$ can be really large, you cannot represent two numbers with type int (int only has $$$\le$$$ 10 digits).
POV — You have solved A B C and you are randomly roaming in the site and waiting for the contest to end.
Wtf problem E is not about segment tree(((
Is D long implementation or i am wrong :/
Not particularly. I wrote a relatively lengthy bfs idea and even then its below 100 lines incl template.
Came up with a solution literally 1 min after the contest ended. Now have to wait till system testing to see if it works lol.
Unfortunately, I found a hackable submission 146415862 of krishnagskr983 but when I clicked on the Hack button, the web started to load and never charged, so I couldn't hack it. I had 10 minutes before the contest ends, the time when I discovered the submission. I have sent the code before the contest ends to one clarification, proof that I could submit the hack. What can we do now? atodo MikeMirzayanov
And another thing, a lot of times, when I open a link with ctrl+click for example, the page doesn't charge and stays white forever (ends to reloading). Anyone is experiencing the same?
I'm experiencing the same:
How to solve C?
Hint — if there is any $$$i \lt j$$$ such that $$$p_i \gt p_j$$$, $$$p_j$$$ will be part of some previously created component.
Hint for E?
Hint for D?
Think in reverse direction. Which squares were painted in the end? How does this help you to determine other squares?
Is there any solution faster than $$$O((N+Q) \log (N+Q))$$$ in E?
I guess no. But seems you need to be careful with your constant. I had to optimize a lot and use fast input methods to squeeze my segment tree solution through.
My comments for each problem:
A. Not bad, but quite implementation-based problem. Unfortunately, I got FST. XDB. Fine. It seems there are some hack on this problem.C. Today I became second-solver of C. Yay!D. Quite interesting.E. How to solve it?F. Read, but didn't thought deeply about it.Also, I think the gap between C-D-E is a bit large.
E: maintain the set intervals of contiguous same colored indices. When you are about to color a sub-array [l, r]:
Suppose we have a BIT built on the values of the array. Whenever we "touch" an interval [L, R] of current color C in step 1 or 2, we will make sure this interval's values are up to date. Suppose, X = the sum of all updates happened to C after the last update on this interval. Then, we will add X to L and -X to R+1 on our BIT. So, basically we are keeping only the intervals which we are accessing up to date.
Took me like 30 min to solve C, but couldn't solve B. :(
Frankly, I feel the idea used in B is very standard. I've heard $$$n + 1$$$ "is it sortable" problems that use this trick. If you don't know it, its probably tougher to think of.
Hint, $$$a_i + a_{i + 1}$$$ is odd if exactly one of $$$a_i$$$ or $$$a_{i + 1}$$$ is odd and the other is even.
Can we swap the order of two odd or even numbers?
what are the hacks for problem B.
Ig many solutions are gonna give TLE, because some peeps have manually swapped each element of the array, with a time complexity of O(N^2)
Now I think I should have tried hacking instead of trying to solve D.
solved c, connected component will always be a subsegment. not sure if it's totally correct.
It's correct, in fact.
When processing operations in backwards order in D, how to avoid bfs / dfs? I see some participants have solved it with simple loops and I don't get how there is a guaranteed order with that.
How to solve D ? I noticed that for correct painting there must be consecutive 2 equal elements in every row & column. So I built a graph such that if consecutive element is to the right, I add edge to the (j+1)th element else to the (j-1)th element. Similarly for column. Then do topological sort. I also kept two arrays right and down stating if for the particular cell, the consecutive element for the row is to the right & for column to the down. And if not right, then while printing i will reduce the column number & similarly if not down, i will reduce row number. But this doesn't work. Could you help me where I got wrong ?
My idea was a BFS backwards through the painting operations. Starting at the end, your 'next' (previous) operation must be a 2 by 2 square either of equal numbers, or of equal numbers which are unpainted (and any already painted numbers, since these are fixed now). Start with all the 'good' squares in a BFS queue, paint them, then paint any 'nearby' 2 by 2 squares which are now fine to be painted, and so on.
If you reach the end of the queue and there are cells as yet not fixed, it's impossible. Otherwise print the operations back to front.
lets say you have a $$$2 \times 2$$$ square of following configuration somewhere in your canvas...
lets say your code pointed both cells to $$$(1,1) \to (2,1)$$$ and $$$(1,2) \to (2,2)$$$.
but i guess in reality it should have been $$$(1,1) \to (1,2)$$$ and $$$(1,2) \to (2,2)$$$ or something but not the first case.
how do you deal with such cases ?
I was thinking along these lines for some time, I suspect very complex cases can occur for single cells or L shapes areas.
As for the actual solution:
Suppose we're processing operations in backward order.
Lets call a "fixable" cell one that is coloured by a later operation.
We can colour a square without affecting later operation if all non-fixable cells in it are of the same colour.
It never makes sense to colour the same square twice since the later operation on the square will make the earlier one irrelevant.
Colouring a square can make at most the $$$9$$$ squares adjacent to it colourable now when they weren't before, so we can use a bfs to do this in $$$O(n ^ 2)$$$.
F is actually a nice problem, thanks! E is not bad too.
Quick idea of Problem D, but bad and buggy long code implementation due to my debugging ability
(UPD: The bottleneck is that I used scanf & printf instead of cin & cout with ios::tied which gets AC after the contest, that's really a lesson when I met the scale of input or output more than $$$1e6$$$.
Although I liked most problems Problem C was very very similar to this. I just copy pasted my code with one line modification. https://www.codechef.com/COOK137A/problems/ERASE/
I think it's insane to get TLE like that on problem B just because I am using python
146366116
Just to let you know that peeps with same implementation in C++ got TLE as well. 146367557
Use "\n" instead of endl
the pretest cases for problem 2 are not at all good they can be a lot better-got tle while system testing if it would be during the contest, at least I would have tried fixing that at the time of the contest
Did someone leak a hackeable solution on B?
I mean that's a great idea.
yeah :P , CHECKMATE cheaters
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
very disappointed by the problemset... Problem C was easier than B... Took me 15 min to solve C but even after hours can't figure out B... Setters should verify the difficulty level of any problem before rendering it....
Problemset was godlike, only problem that wasn't that good was D, because it was heavy implementation based.
But other problems? Really nice.
problem B...
146420483 Can someone please help me figure out why am i getting tle
Replace endl with "\n"
(look at my submission history :P)
Thanks bro
Can anyone please tell me why my solution 146399384 takes so much memory, while similar implementations have very less memory. According to me, total array and vectors size included will be at max $$$2*n*m$$$ integers,which should not consume so much memory (242 MB).
Well You have ans size of 1e6 of vectors of sizeof 3 integers
Vector innately may have capacity up to twice the size (well it depends on the state) plus they have ~3+ integers for their internal representation IIRC
You can reduce consumption significantly if you replace nested vector with struct/tuple/array
Example with array is here https://codeforces.net/contest/1638/submission/146453838 It reduced mem consumption by 60MB
You can also use 32-bit compiler and it reduces consumption even more https://codeforces.net/contest/1638/submission/146453507
Thanks, that helps
Bad pretest (:
You failing systests doesn't mean pretests are bad
But they are bad. Quadratic solutions were passing on B, while the case (n, n-1, n-2,....), that have quadratic edges, was not on the pretests of C.
Your code used a lot of memory indeed ! Pretest were fine . You are the first one i heard saying pretest are bad on problem C though . Yeah for B they allowed O(N^2) which later got fst
I guess pretests for problem B aren't that strong, for there is few test case containing duplicate.(Especially for sort based algorithms)
Actually I'd rather celebrate ENIAC Day than celebrate Valentine's Day as a competitive programmer.
P.S. though ENIAC Day is celebrated on Feb.15, ENIAC was announced to the public on exactly Feb.14, 1946.
Can anyone tell me how to optimise this one to avoid TLE I tried using DSU and to avoid O(n^2) complexities thought of a[I]>I and parent[I] is not =-1 i.r it isn't yet included in any of the connected components https://codeforces.net/contest/1638/submission/146477193
you don't need to use DSU.you can do it in O(nlog(n)).Here is my submission 146445395
If we tweak problem A as :
Given array is not always a permutation. I was wondering if is there any better ideas then N^2.https://codeforces.net/gym/103495/problem/H is then what you're looking for :) (although it is on strings, the idea could be further extended to any array with numbers <= 1e9)
Thank you for sharing the problem ! Got to know something new. :)
can someone explain to me how (https://codeforces.net/contest/1638/submission/146492255) these types of implementation for problem B works?
Sorry complete beginner here
a way to solve problem B is to check whether the odd number sequence appeared in the origin array is non-decreasing, also the even number sequence.
so lst[0] means the last number appeared in the even number sequence, as lst[1] means the odd number sequence.
When you see a "x&1" operation you can see it as the same as "x%2". While bitwise AND operator (&) and MODULO (%) is a very different concepts, both expression above produces the same result
Yep. People should just write x%2, the modern compilers don't need that extra hint. They can figure out using bitwise operator themselves.
But sometimes we are just too used to the arcane versions.
I hope you have no plans for Valentine's Day
In fact, I did have plans: participating in another CP contest which overlapped with this one
... Why does everyone hold competitions on the same day ;-;