The future is bulletproof
The aftermath is secondary
It's time to do it now and do it loud!
Привет, Codeforces!
Мы с 74TrAkToR рады пригласить вас на наш совместный Codeforces Round 705 (Div. 2), который пройдет в 06.03.2021 17:05 (Московское время). Обратите внимание на необычное время проведения раунда. Он будет рейтинговым для всех участников, чей рейтинг ниже 2100.
Мы уже проводили раунд и провели работу над ошибками:
- условия будут короткие и понятные
- мы постарались сделать претесты еще сильнее
- разбор будет опубликован сразу же после раунда
Мы хотим поблагодарить всех, кто оказал нам бесценную помощь в подготовке этого раунда:
- Нашего координатора KAN за великолепную координацию раунда.
- Наших тестеров Tlatoani, sava-cska, DIvanCode, BLIZZARD, Mlxa, plagues, voventa, hg333, golions, kassutta за отличное тестирование и полезные замечания.
- MikeMirzayanov за прекрасные системы Codeforces и Polygon.
Вам будет предложено 6 задач. У вас будет 2 часа 15 минут на их решение.
UPD: Разбалловка $$$750-1250-1750-2250-2750-3250$$$.
UPD2: Разбор
UPD3: Поздравляем победителей!
Div. 2:
Div. 1 + Div. 2:
Желаем всем удачи!
We will miss the main ponies from My Little Pony in this round. :(
Why no ponies this time :(
I hope ponies would have sort of cameo in the problems :)
Last time when they did, editorial got 80 downvotes :)
.
Wow dude! you've got $$$69$$$ downvotes!
I won't downvote you :).
There were 70 ,i made it back to 69 to maintain it.
They were again 70, I made it back to 69 to maintain it
It was -66.. so --;
It is -68 now...
fixed
short and clear ? okay
I think everyone love this line : the statements will be short and clear
But I like this line : the editorial will be published shortly after the round ends
For a moment I thought you were replying to your own comment. XD
this contest totally killing my rating :v
after saw this i went to check you in the tester list xD
Finally became Specialist after a continuous +ve delta change in past 9 contest XD
That surely is a slow climb haha
Yes , that seemed a long way from 1300 to 1400 but I enjoyed it
Somehow from slow climbing, I started fast descending. Gotta fix that!!
Lot more to come !!
And we have a lot to go XD
Inspiring !! Consistency Level inf!!
XD
Ur graph is lowkey inspiring as u didnt giveup :)
Thank you :) Next milestone is expert XD
the statements will be short and clear means challenging.
I like it.
Do you know INGLISH? this means problem statements are not wordy.
but pretest should be long and strong (just kidding I know that may result in a long queue)
I want strong pretest.
Failing test after passing pretest hurts more.
statements will be short and clear, strong pretests, and also hoping for nice problems.
Liked the intro :'3
Is it rated?
No, You can give this in GYM section.
Why do you guys even comment without reading the blog? @dreamkiller
I've seen it in many blogs... Wondering why many people asking this kind of question. :(
Hope I can reach 1300 in this round :)
May the Force be with you!
From the past 5 contests, I've been losing ratings consistently :/ I hope I'll break this streak in this contest :P. Wish me luck :)
good luck brother :)
Good luck!
You will surely... This one will be positive 100 delta :)
Maybe next time :P
So many people wishing you to do well here... Next time for sure.
With You Brother All the Best
Good luck bro
Good luck !! :)
Good luck bro! :)
Rating is not important but your ability is,good luck!
Good luck and have fun! :)
Success is the next chapter of failure... Wish you all the best bro.
here you got +26. ratings are like a roller coaster sometimes up sometimes down.
Yes, I totally agree. Although I was close to problem D but couldn't complete it within time, I'm pretty happy with the positive rating change lol xD.
What a way to end the streak with a plus 200 delta... Amazing stuff
Thanks xD
74TrAkToR congrats on the first playoff win, well done!
Thanks!
I hope this time Question B is better than last contest
As a participant, wish you all satisfying rating changes :)
As a single, I wish you all to become double XD
What does that mean?
It's the name of the song from intro
I believe that you've got the key to hold a nice contest and this time I'll enjoy the problems!
Wait the coordinator is not AntonThe problem setter doesn't enjoy the immense pleasure of rejected problems by our emperor anton. ;-)
In your last contest C is bad(pretest is nothing),so this time I solve C first but C is still bad(example is nothing),so disappointing...
The time of the competition is unusual, please pay attention :>
It feels awkward when you don't see any comment with As a tester.....
As a tester, I think that it's a wonderful round
As a participant, I think Div2B is most shit problem of 2021
As a participant, I think you just said that cuz you haven't solved it yet
Same for me, but with C ;)
2 Div1's after this contest are ruining my chances of becoming an Expert.
Bruh what went wrong for you?
I think I am color blind
Is this an intentional move?
Я считаю, что надо объявить бойкот и не писать данный раунд, поскольку многоуважаемые его авторы, Екатерина Шиляева, 80-ый призер Всероссийской олимпиады школьников по информатике 2019, а также Евгений Карпович, 95-ый призер той же олимпиады(да еще и 10-ый класс), имея БВИ, наглым образом позволили себе принять участие во Всесибирской олимпиаде школьников по информатике 2021 и забрать два диплома 1 степени, которая является перечневкой и служит исключительно 11-классникам, помогая им поступить в ВУЗ. Иными словами, теперь два человека пойдут не в институт, а сами понимаете куда, потому что кому-то очень захотелось взять лишний диплом.
Мне кажется, но многие люди на всесибе возьмут в этом году призеров всероса. Вопрос: зачем они писали всесиб и занимали чье-то место? А вообще, пофиг на то, что вы с фейка не поучаствуете. И еще я 11 класс
какой же ты смешной, чел)
My 69th contest. Hope to reach current year in rating
It will be very good if the statements of problems will not contain any legends, stories or histories. And then the problems will be easy to understand.
This is going to be my 50th contest and I am still stuck on grey. Someone, please guide me.
-> I can see you are pretty comfortable with problem A , So I will advise you to up solve problem B of every div 2 round.
-> practice daily , I can see you are not regular in doing problems , its fine even if you do just 2 or 3 on a busy day but do it regularly.
-> Whenever you come across a new concept (eg : prefix sum, binary search) learn that concept and solve few problems on that.
-> solve problems slightly higher than your rating , for you case solve up to 1400. and solve problems with different tags not just brute force and constructive.
May this helps
just wanna tell u, it inspired me !
Hope to become cyan in this contest.
the statements will be short and clear
ONE LOVE
Little suggestion: the competition announcement should include a link to the competition: Codeforces Round 705 (Div. 2) but not Codeforces Round 366 (Div. 2)
UPD: Have been fixed :)
Maybe I don't get what you mean, but when I click on the link it works just fine
I like your hair
No room for sexual harassment!
Wtf XD XD
// a joke
I know you actually made me really laugh XD
Here is the link below the blog:
And when I enter in the round Codeforces Round 366 (Div. 2) the announcement change to this blog...
Thank you, now I see. We're gonna fix it as soon as possible
All participants get happy when they read this: The statements will be short and clear.
It is very fun. Thanks AlFlen and 74TrAkToR for this round!!
Note: unusual time it will start at 14:05 not 14:35 UTC
Hey Mr. white We got an order for 5 barrel crystals. wanna cook?
After the round XD
In public,you have to be in danger
I'm not in danger Nan-{many 'O's} I'm the danger XD
So, you are the one who knocks?
You got damn right XD
Hows skyler?
she is now with Ted, I will ask her when come XD
74TrAkToR lost our respect
Why?
Потому что всесиб написал :)
Соглашусь, не прав
As a...
Hope strong pretests XD
Hoping that this contest will make me pupil. See my rating :))
Same brother
what about those who can't even find a solution ? :(
This scoring distribution has partial Div1 vibes
You were right
The scoring distribution is quite different from normal div.2!
Div 1.5 coming!!!
its_Atrap!!
everything harder than usual forces?
So i have reached college and this will be my first contest from my hostel. Me and my 4 friends are also participating today alongside me. Super Excited for this round and Good Luck to all ..
Please don't cheat if you are participating alongside :P
No bruh, he is my best friend and his only goal is to compete me.
The time(2h15min) maybe means the contest is a hard one. I will try my best to solve it. Good luck to me, and to everyone.
Stay Cheeki Breeki!
"the statements will be short and clear"...meanwhile problem B: Am I joke?
At least the statement is clear but I doubt short...
P.S. Just for Div.2B...
I swear I will throw all digital clocks far away from my house after this round.
In the 3rd test case of problem B. Why is 52:26 invalid
[Deleted: Sorry I thought it would be a silly doubt and so didnot bother to ask directly ther , But i will remember that! ]
the mirror image of 52:26 is ?5:52, the ? here is not a number.
You're not allowed to ask here, you can ask in the "Ask a question" section.
Are you high while making the question??
I've never seen a contest so full of cancer before
Submit Code button not working.
Dear antontrygubO_o please coordinate every codeforces round and never let this kind of shit pass,taking part in it is just a waste of time!
Even if you have a bad experience of the contest, please respect the work of the authors and the testers. Making a contest is not as easy as you think.
I'd argue that comment is aimed more at the coordinator than the setters. I'd say its pretty normal as a setter to sometimes think a problem is nicer than it actually is. Its the coordinator's job to ensure that the problem quality is up to the standards of the platform.
To tell the truth, the experience of this round is truly bad. But your words maybe too extreme...
toxic comments should be removed just make constructive criticism or don't I don't see it as a bad round A was ok B wasn't easy to code and C was hard to think about so each problem from A B C makes you try to improve in something which is good if a problem looks bad for you that doesn't mean it's bad others might like the problem you hated and might hate a problem you like
I had a stroke reading that
Well you're mad from your WA in A so I won't blame you
Oh I'm not (actually the other way around), you're triggered cuz of my simple comment on your punctuation
You're completely wrong about that What you said doesn't mean anything so I'm not triggered about it at all
Ok then
Test Case 3 of D is killing me!!!!
Help me with D once the contest's over.
yes bro you are god
How?
Segment tree
Lauda
Create for every prime number $$$t$$$ segment tree, that will store array $$$p_{1}, \dots$$$ such that $$$p_{i}$$$ is equal to degree of factor $$$t$$$ in number $$$a_{i}$$$. Assume we multiply $$$a_{i}$$$ by $$$x$$$. Factorize $$$x$$$. For every factor add his degree to appropriate segment tree and check, if the minimum on whole segment $$$[1,n]$$$ become bigger. If so, multiply result buy factor $$$newmin - oldmin$$$ times. But $$$18000$$$ segment trees with sizes $$$n$$$ need much memory, so notice, that the value for segment tree can become bigger that zero not earlier, than $$$n$$$ queries for this segment tree was applied. So we will just store queries for every segment tree in array and once the number become $$$\ge n$$$ apply all them to appropriate segment tree. After this, apply all queries to this segment tree immediately.
The worst B I've ever seen...
I totally agree, implementation heavy B atleast for me :( I just got last 15mins to solve D :(
I spent 25 min solving B...
No FST plz!!!
rainboy orz
Disclaimer: I realize the authors work hard to set problems and I appreciate that, the following are just my thoughts about problems like this contest's Div2B in general.
Just why... it takes barely any time to arrive at the solution for problem B, but then becomes a really bad implementation problem if you're not being careful.
I thought the majority of the community agreed that these types of problems weren't interesting at all.
I mean what is the purpose of problem B in a Div2? Is it just there to ensure that people new to competitive coding will have something to spend the contest implementing?
In my opinion B should be an elegant idea that it is possible for newer participants to solve after thinking about it for a while. It should be something that makes them satisfied (or even better, amazed) when they solve it (or read the editorial). Remember, this is the problem that will make the biggest impression on a lot of people who are fairly new to competitive coding.
I get it, original interesting ideas that are easy can be difficult to think of, but at least try to come up with something slightly interesting that isn't an utter and complete pain to code. For example — problem A, its a fairly nice idea that isn't too tough.
People rant (or joke) about antontrygubO_o rejecting a ton of problems, but frankly I think that's a good thing if it is to remove problems like this one.
I totally agree with you, the best part of codeforces rounds are logic/ideas behind each and every problem there in contest. But if we see problems like B then I don't think people would appreciate the round, and it may be uninteresting for many participants.
Even a single problem like B can spoil complete round.
Exactly, problem B was quite dumb as it was just brainless implementation
I agree with everything you said. Problem B was a bad problem even for Div2 (which is usually not the best in terms of beauty and originality).
However, I want to put in a good word for the authors. Problem B wasn't all that implementation-heavy (I mean, I've seen worse). Part -- or should I say, the entirety -- of the challenge to overcome was to find a sensible way to translate the idea into code, which wouldn't lead to a complete mess. And if done right, the implementation is actually quite short.
I've seen this same theme reappear in problem D. One could, in theory, solve it by means of segment trees (which, at least in my case, is the first thing that comes to mind), but that solution is hell to implement. Here, again, the challenge was coming up with a good approach. This one I enjoyed solving.
Of course, I'm not saying that B and D are on the same level, not even close. Problems like B should be eradicated, period. I'm just saying that the implementation alone is not bad enough to justify such a negative feedback.
Todays B and C would have perfectly fit in educational contest, since there are often implementation heavy problems which feel like school homework.
You guys are getting this kind of school homework? I find homework way more boring than any problem on CF. The typical homework in my school is "draw the plot of $$$\frac{1}{2}^{\frac{2+|x-1|}{3-|2x|}}$$$".
I think these types of problems are good for A and B. Sure I didn't have to think theoretically at all, but I had to think more overall than normal trying to figure out how to implement, and had to think about actual coding in a coding contest rather than just basic mafs.
As far as for beginners, who they're for, beginners often don't have basic implementation skills and when joining a programming contest with almost no programming for the problems they see would leave a bad impression for me, as I would not expect to feel like i'm in grade school math writing equations but actually programming.
Also people who think these are "implementation heavy" surely have never done a single hard cp problem, or severely need to practice implementation...
I think the term "implementation heavy" needs to be explained. I use it not to describe the difficulty of a problem, but the ratio of creativity and work to do to solve it.
See Connect the Dots as an example for a simple implementation heavy problem.
I believe a problem can need creativity and thinking for its implementation, which others either don't believe or, what I think is more likely, seem to purposely exclude that type of thinking ability. JOI Port Facility is a great example where solving on paper is not too hard but figuring out how to execute such an idea takes work.
Also, I believe when people call such problems as you gave for an example a "implementation heavy" problem, they just have very poor implementations that can be greatly condensed. My implementation for that problem would be likely around ~50 lines including template. Is that still a high ratio to you? Is my implementation to B from this contest a high ratio to you? If so, then ig we just have different ideas on what defines such ratio, though keep in mind this is a "programming" contest. But otherwise, it is your own fault for not taking the time to think of how to write a nice solution, which in a timed setting is a part of the thinking and contest.
Problem A and B are basically always going to be close to 0 brain for anyone at least my level, so imo why not at least add an aspect of implementation thinking necessary to solve? And I think having too low an implementation to thinking ratio makes it a math problem not fit for cp.
Statement of B has been changed without any announce, and "future" also means "now" ? Very bad experience.
How to solve B non-implementation heavily?
sadly, it was a pure implementation-based question.
I think that my implementation came out well: https://codeforces.net/contest/1493/submission/109236256
This is implementation heavy
You can slightly clean up the implementation by processing the reflection using maps and performing it on strings to avoid the pain with leading zeros while reversing, but I don't think there is a way to make it properly clean.
Edit: My attempt at coding it in a clean-ish manner — 109282647
`
Although this code still seems a bit big to me
You could have simplified it additionally with:
1.Brute-forcing it and verifying if it's correct. I think the more optimal version was probably uglier.
2.In C/C++ you could have read the hour and minute separately when they had : between them simply with
scanf("%d:%d", &h, &m)
If you can use python, a lot of the annoying parts are pretty smooth (parsing the string to int, reversing the strings, padding with 0): 109244789
I think this is pretty ok: 109352844
Как решать задачу B? Я могу выйти на всерос по инфе, но не могу решить дурацкую B....
Why does Segment Tree implementation TLE for D?
How to solve C?
greedy, move from the end, try to change s[i] to be >= s[i].
i.e s[i] to 'z'
then you just need to calculate the remaining characters and see if all of them are divisible by k if not you can take from the characters after s[i] as much as you want to make it divisible by k, if there's still remaining characters after s[i] you didn't replace you just need to replace it with 'a' and make sure it's also divisible by k.
What was the desired complexity for the problem D?
My solution idea which didn't pass was as follows.
Number of primes in the possible gcd across all the queries would be pretty few. So, we iterate over each prime p, and count its contribution for each query. My time complexity was #(number of possible gcds) * n * log n.
But it didn't pass, gave TLE on test #4.
how can you calculate number of possible gcds? Anyways I think my solns worst case time complexity was $$$O(n \log^2n)$$$
For each prime number p, I checked whether it is a divisor of each a[i] (including the numbers in the queries as well). Basically, I maintain for each prime, the positions in the array where it appeared (including queries) and check whether the cnt of positions >= n or not.
Can anyone tell why the solution to D will not exceed the memory limit. As in my accepted solution I am creating a map of multiset of the number of each prime that I am getting. and in worst case, if a prime is present in all n elements then the size of this map of multiset will be (2*1e5)*20000 memory (as there are more than 20000 primes from 2 to 2e5), which is too huge to pass. But I am not sure how it is getting accepted?
Given that there are 200 000 queries that change just one element, it is highly unlikely for many primes to have many elements they are part of. If every element was a prime and every query was a prime, you would have about 10 primes at most that were used by all elements (given your calculus of 20 000 primes). And realistically, given that 2^18 is about 200 000, an element will have at most 18 primes (even less, since pretty much all primes are bigger than 2). Those two realisations alone should help you figure out about how many elements could be maximally in the maps.
instead iterate over each prime present in x and add their contribution to new GCD.
So I spent the whole round (A-D) going like : ok this is obvious. Now lets write 300 lines of code.
can someone please help me in D, getting WA on pretest 3 :(
the statements will be short and clear== False
The statments of B was not too much clear :)
The future is grey
The aftermath is negative delta
It's time to implement it now and do it forever!
Implementationforces!!
Boring problem b, I don't like problems that don't really require any thinking(and just implementation) and probably most people don't tbh.
Hmm I think the time limit for Problem D was a bit too tight.
Agreed. I spent whole contest in constant optimizations for this problem :(
B should've been C, C should've been D or E.
Can anybody please help me in figuring out whats wrong in my solution for Problem B Code
50:00 in the mirror would be 00:02. But your code gives 00:05. You didn't flip the digits
I made the same mistake.
[DELETED]
First of all, I want to thank the contest setters for putting their time and effort into this contest. I understand that a lot goes into this. However, I don't understand how anyone could have thought it was a good idea to make B. The main thing I like about codeforces is the clever solutions for problems. However, problem B was a completely boring implementation problem with absolutly no thinking. I hope that this is the last time a problem like this is set.
Problem D can be solved using Segment Tree?
My question is also the same. Nothing different. No difference.
Translation: Have you ever got this type of pretests failure after writing 150+ lines of code with SegTree, seive, etc.?
One of my friend Zesty_Fox faced the same situation :TLE #4 -> MLE #6...
Here is what he submit in D. I found him debugging this problem until 1a.m.(UTC+8)...
Nice problem set, but imo C & D were not worth 1750 & 2250 respectively. 1500 & 2000 would have been a better score for them.
weak pretest for D...
Hi. I liked the problems. But this one was harder than an usual div 2.
problem B, C and D are a bit hard to implement.
But beautiful problems!! nice job!
For problem B, a test case in pretest 2, why answer of 50 3 30:00 is 50:00 ? isn't The time in the mirror (00:05) illegal, the minutes is larger than 3
Time in the mirror is 00:02
Memes kill frustration
The round is too implementation-heavy to my liking
Good Problems
C was not C
I think the round was good. Yes, there was an implementation in it, but the tasks were not without ideas (except for task B, but with the help of it it was possible to create a struggle between div3 participants, since they scored different points). Also, the round has a good balance of tasks (many div2 participants solved either C or D)
No offense. The Problem C(K-beautiful Strings) may need to be declared that the length of string s is n. I find some accepted codes couldn't work when the length of s isn't n. Or maybe I'm missing something.
This is not true, in our checker all this is taken into account.
In the input section n is denoted as the length of string s
I agree it's in the problem statement, but it was hard for me to find (I had to re-read a few times).
It's written in the problem statement.
The first line of the description contains two integers n and k (1≤n≤k≤105) — the length of string s and number k respectively.
Thanks for explaining.
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Hi Mike,
During contest I submitted code in C++11[submission:109246439] and it gave TLE during system testing and again I submitted same code in C++14[submission:109283562] after system test it seems to pass? Please look into it i will loose lot of rating points
Why copypast strings (in reflect twice copypasting)? Can't check now but my guess that compiler with c++11 just can't optimize this.
I got message that my solution of problem A matches with other guy. Solution of A was too trivial, so it may match with other. My sol — 109233079 Other Sol — 109231770
MikeMirzayanov AlFlen KAN
Have you forgotten to change rating? QAQ
Second question was a question lol!
My Code for C is failing on 170th Case of Test Case 3 . Can Anyone please share how Can get That test Case , I want to upsolve but unable to find The Failing Case .
Sadly I think that's impossible it happened to me several times and I searched alot about it but found nothing
I wish a new feature would be added by which the person searches for the test case that he wants, and it appears to him, and in this way we get rid of the annoyance that afflicts programmers :)
Yes , There should such be such a feature . We always tend to find error in our own code by looking at the test cases , but when these cases our not visible to us and our code is complex enough we are unable to upsolve it. Codeforces Team should make Provision of Test Cases after the contest so that we can find the mistakes in own code and learn from it
I know this solution is not scalable but it might help in some cases.
Something like this:
cin>>t;
for(int case=1;case<=t; case++){
int n,k; cin>>n>>k; string s; cin>>s; if(t<100){ // solve problem and output }else if(case==170){ cout<<n<<endl; cout<<k<<endl; cout<<s<<; exit(0); }}
Using this I got, n=4 k=2 s=acad
as 170th case of Test Case 3
Hi I actually Tried This for(ll T=1;T<=t;T++) {
} at the 170th case I was printing The input as output the the verdict was : wrong answer The string is not beautiful (test case 170) which clearly Implies that the test case 170 was not what you are saying . Thanks anyways.
Hi,
I have corrected the typo in original comment. It is actually s="acad" instead of s="acac" for that case. May be still I have done some mistake while getting the 170th case but you can use this idea for getting it by yourself.
Also, I suspect that in your original solution you have printed some output twice or nothing for some case before case 170. That's why you might be getting a different judgement.
Also, I checked with your code and found that for: n=4, k=2, s=acad
Your output is "acac" which is lexicographically less that s. You might use this for some additional debugging.
Thanks , Finally It Got accepted .
The worst B I've ever seen..-
just sad to know that i had gotten fst in B because of my bad coding logic and style
Hi MikeMirzayanov, I received a message from CF stating that my Solution for problem A for Contest 705 Div2 -lakshya492/109235173 coincides with solution 9851551/109233522. I assure that there has been no sharing or leakage from my side. I never use ideone.
My submission link: 109235173 Coinciding code link: 109233522
I request you to look once again at both the codes and understand that whatever the similarities are in both codes they are very likely to happen as the The problem A had a very small code because of which there is a very high chance of coinciding with someone else's. I hope my ratings will not be rolled back and all my submitted solutions will be unskipped.
This is exactly how the institution of reputation works:
Yes I have plagiarized code once before, but that was the first and last time. I never even commented anything then because I felt guilty and learnt from it, it was never repeated again. I have worked hard at data structures and algorithms since then to become better at CP. I assure you I am the author of my submission and any similarities are pure coincidence due to the fact that div2 A problems have usually very short solutions. Please understand.
Can someone please help me why I'm getting runtime error in my submission for problemD: https://codeforces.net/contest/1493/submission/111289467? I thought it might be because of memory allocation but saw that author has implemented the solution with same memory requirements as mine. Please let me know where I'm making mistake. Thanks in advance!!!