Привет, Codeforces!
<almost-copy-pasted-part>
Привет! Во 25.03.2021 17:35 (Московское время) начнётся Codeforces Round #710 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы будем расстроены, если у многих попадают решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи на этот раунд были придуманы MikeMirzayanov, Supermagzzz, Stepavly и sodafago
Спасибо darkkcyan, bugdone, harlequen, iankury, bfs.07, songsinger, infinitepro, sodafago, Gassa, Rox, sharepoLOVEDDD за помощь в тестировании раунда.
Спасибо MikeMirzayanov за платформы и координацию нашей работы. Удачи!
</almost-copy-pasted-part>
UDP: Разбор опубликован
Finally another Div 3! I was half expecting to go a month without one... Wishing everyone an enjoyable contest and positive delta!
Always so exciting to have these div 3's in my life!
Always so exciting to have these Div 3's in my life!
Isn't it risky to have a round without testers? Are there are some hidden testers for Div-3 rounds :P?
its_Atrap
Welcome to the community of negative contribution
:ghosthug:
I went ahead and downvoted you all its_Atrap lady_b1rd Torehalt :clownglasses:
Can't wait for my first Div3 Round....
your wife is hot man
I'm waiting this contest since days ... it's best for me ^_^ We hope that are no any mistakes during the contest ... Thanks for your efforts !!
Wishing you all A big positive delta!!
U should have wished for positive upvotes in comment section.
wow, there's no comments with more likes than dislikes.
Let this be the first!
Are you saying no matter what I write I will still get downvotes
)
َ
.
Will any comment here get upvoted?
They think div3 contestors like us are inferior
:(
After the div2 brutal round hopefully this contest will serve as a motivation to continue CP! haha
plot twist: this comment is gonna get downvoted
Guys let me compete with Monogon for 1 rank in contribution, I need your help to achieve that goal!!!
Upvoted. I think you have a lot of work to do. You made a few mistakes with this comment, such as not posting it immediately after the announcement comes out. Also, in this comment you state that you have a particular goal and people should upvote you to help you reach that goal. Unfortunately, this will isolate people who are willing to upvote you for different reasons. So, you should not state any reasons or argument for why the reader should upvote you. Instead, just directly command them.
.
Why am I commenting in a downvote hell?
Why all comments are getting downVote?
The highest upvoted comment in this blog has -10 upvotes!!!(why so much hatred).We Want vovuh in upcoming div3 rounds :P
Is it rated?
I just asked a simple question. Why downvote me?
Because you don't like reading blog carefully, Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
master_is_here ok thanks. btw are you a girl or a boy?
A boy who knows he will get more and more negative contribution if he posts any comment on this blog.
Downvote
I was gonna post a meme but I changed my mind
BanjoByster who?
I am banjobyster
Don't lie man. You wrote it because u need up-votes.
I am happy :)
One who dislike this post doesn’t love his/her mother!!
One who dislike this post doesn’t love his/her mother!!
Why go on mother, you could have gone on anything like keyboard, mouse, CP, electricity, Edison, etc. but don't comment such to just gain some upvotes, PLEASE!!!
The comment is hidden because of too negative feedback, click here to view it
where to click?
plz downvote me, i'd like to have anticonributiuon on this acc
¿Quieres?
Enjoy getting downvotes with your pizza.
.
This is my first comment.Hoping to become pupil. P.S. Don't Downvote
I am not scared of anyone of you......... >.<
The round starts in 20 mins, make sure you registered. I wish everyone participating good luck and a fun round !
please don't downvote
good luck everyone! hope to get rating increase
wish you the same
why so many downvotes???????
my solution to problem E: https://youtu.be/efrkmxiEDNc
code: https://codeforces.com/contest/1506/submission/110998366
nevermind i think i missed the joke.
Comeon Man, this isn't fair... Your video was posted way before the contest was gonna end... Atleast could have waited for the contest to end! Your videos must be source of logic and thinking for upcoming coders, not a way to help them seek an easier way to just copy and paste
no it wasn't. it was supposed to premiere at 10:15PM IST. I made it live at 10:05PM IST exactly when the contest got over. do you seriously think I would do something like this for a few hundred views?
I don't have a personal grudge here man... Just that someone has commented there exactly 15 minutes ago... Meaning at 10:01(+5:30). This would mean that your video got uploaded before 10:01 itself
if I premiere a video on youtube, the thumbnail will be visible way before it goes live. people are allowed to comment, like/dislike but not watch before the premiere begins.
Almost all solutions are aviable online : C: https://www.geeksforgeeks.org/longest-common-substring-dp-29/ G: https://www.geeksforgeeks.org/lexicographically-smallest-string-formed-by-removing-duplicates/ @MikeMirzayanov It should be made unrated cause it is not fair to those who are giving.
How to solve problem D?? but nice contest though loved it:)
If some number occurs x > floor(n/2) times, then, it is 2x — n. Else, its 0 or 1 depending on the length of the array
I was just going to submit D and contest finished :-( :sadpuppynoises:
I wanna know abt D... It took so much brain power and idk why but i feel it's gonna be damn easy
Just use priority queue keeping frequency of nos...Run a loop untill its size is strictly greater than 1
In loop reduce frequency of first two nos and insert each one iff its frequency is still greater than 0.
firstly, sorry for my english
let max be the maximum number of times the number occurs. if max>n-max, then the answer is max — (n-max) tk we can delete this number with all the others, but we can't delete it with ourselves. otherwise, the answer is n%2, because we can delete the remaining numbers up to the number of our number, and then delete them with our number. well, if n%2 == 0, then we can delete everything, otherwise everything is clear
How to solve G?
Try using stack !
why does my implementation using sets fail
https://codeforces.com/contest/1506/submission/111057558
Afaik the time complexity must be O(N*log_2(N))
Try using left.lower_bound()
I didn't go through your code but I had used priority queue for this question and it got accepted (at least in pretests).
Submission: https://codeforces.com/contest/1506/submission/111027634
what the heck happened to the comment section?!
A massacre
Thanks for the round! Here's my screencast (HD versions forthcoming): https://www.youtube.com/watch?v=s7owI7Uo2rk
Is there any difference between :
auto itr = st.lower_bound(val); and
auto itr = lower_bound(st.begin(),st.end(),val);
One solution gave TLE and the other passed and the only difference is listed above, ACCEPTED and TLE
yes for set its the right way -> st.lower_bound(val);
and it totally wrong ->auto itr = lower_bound(st.begin(),st.end(),val);
i once faced that.
Okay I understood that it is wrong, that is why it must have given TLE, but what is the exact difference between them or their time complexities
In lower_bound(set.begin(), set.end(), val), std::set doesn't have random-access iterators (think of them similar to array indexing), so the time complexity is linear. With set.lower_bound(val), std::set has that lower_bound built in, so it's much faster, logarithmic time complexity.
Edit: Just realized that b23v said pretty much the same thing :/
I see too many downvotes in this blog post. I'll investigate it in few days. Sorry, no time to do it right now. But I'll try to revert unfair votes and prevent such behaviour in the future.
Hey, MikeMirzayanov Just wanted to bring before you plagrism of two users
cyborg_7459 and cyborg7458
Both of these Users don't know whether same persons or different has submitted solution of Problem A and B with minor Changes. Please Do look at their submission. Even their template is same. Since Even submitting Solutions from alternate account is clear voilation of policy please Review their submission. Maybe they would be same person just submitting solution from one account to confirm its correctness and escape penalty, which is voilation of Rule and needed to be punished if really found guilty.
Their Submissions:
Problem A: 110996666 and 111008607
Problem B: 111007814 and 111006918
MikeMirzayanov plag_report Yeah my bad, but I have an explanation for that which I think might be justified. Since the past 3 contests I've been facing issues with the CodeForces server being down, as might be evident from the bad results of my past 2 contests as well as the fact that I could not give the Division 2 immediately preceding today's contest. Thus, to prevent a negative effect on my rating I started today's contest with my alternate account but switched back to my original one after facing no issues for about half an hour.
I had no idea that submitting from 2 accounts is also a violation of Rule, and I thought that since I could easily prove the 2 accounts to be mine, I would be able to show that the code is completely original in case someone said otherwise.
I can assure you that it wasn't a case of trying to avoid a penalty because I did get penalties in my D and E as well. If I had been trying to avoid penalties by testing solutions with my alt account, then I obviously wouldn't have stopped that for the harder problems
Moreover, I submitted the solution for A from my main account 15 minutes later, which covers up the 1 penalty advantage that I would've received in problem B
Still, you should have read the rules. They are right before registering into the contest. And also, don't you think it is unfair to whenever you have a good performance in your alt to you switch back to your main? This way it would be very easy to farm rating, just create an alt where you compete normally, and if you have a good performance switch back to your main account. This attitude shouldn't be tolerated since it is unfair to other participants. There is no justification to this, it is obviously unfair and violates the rules.
.
I wish that could be prevented but I wonder how especially that deciding if a comment should be downvoted or not is an opinion
is CF oke ?? may be some bug for downvoting . mesanu sir do something
I will
Almost all solutions are aviable online : 1. C: https://www.geeksforgeeks.org/longest-common-substring-dp-29/ 2. G: https://www.geeksforgeeks.org/lexicographically-smallest-string-formed-by-removing-duplicates/ - - @MikeMirzayanov It should be made unrated cause it is not fair to those who are giving.
It wasn't phrased as "find longest common substring" so the task was really figuring out that lcs was optimal. And constraints are low enough to brute force.
Garbage Contest and Discussion!
Is there any specific reason why B is always tougher than C on CF contests ?
There is no specific reason because it isn't true.
can someone help me understand why my code is giving tle hacking, i am not able to find the test case in which it can give tle.
https://codeforces.com/contest/1506/submission/111050778
The reason.
Probably because you are printing Time elapsed at the end which is causing TLE
That only prints once, that definitely isn't the cause of the TLE lol
When you miss B because you type k instead of j.
Could anyone tell me how my code to E 111026430 being hacked... :(
see you are deccrementing x and then finding the max avaiable number there is to fill. maybe this is causing tl in some very specific testcase.
for example lets read
N=8
5 5 6 6 7 7 8 8
answer is 5 4 6 3 7 2 8 1
now see to get to 4 at index 1 you decremented x 1 time
for index 3 you decremented 3 times
for index 5 you decremented 5 times
for index 7 you decremented 7 times
total complexty is 1 + 3 + 5 + 7 + 9 + 11 + ... n (sum of all odds upto n). this looks like n^2. and exactly where tl is coming from.
Thanks for your reply :)
I am black. If u downvote me — u are racist.
My computer was just used by others.I'm sorry to say rev.1's words
Yes,I used his computer because of this easy round.
He who fights with monsters should look to it that he himself does not become a monster. And if you gaze long into an abyss, the abyss also gazes into you.
Why I get TLE in question D upon using unordered_map instead of map ! Isn't unordered_map is implemented using a BST which makes me think it should be faster than map ?
Same I too got TLE on 8th case in problem D this is because the value of a[i] can be 1e9 if in any case there are more values greater than 1e8 then it will form chain structures to hold key-value pair so instead of O(1) per query the amortised complexity may be O(n) resulting in O(n^2) overall. So better to use map which has constant factor of O(log(n)) it won't hurt you!
hi, it was my first contest and I solved 3 questions. will I get a rating, if yes when will the rating changes be announced?
will be updated soon! have patience.
and congrats for positive delta!
hello guys can someone help me out with problem D (Epic transformation). IDK why i am getting tle
my solution is given below code
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
hello guys!!
i am getting a tle for my solution of problem D(Epic Transformation)
Can anyone pls look at my code and help me correct it??
My Code
endl is too slow.
It is bad comment. I tested changing endl to '\n' but it is not fast enough.
unordered_map => map
MikeMirzayanov wrote 2 yr. ago (https://codeforces.com/blog/entry/65383):
This was another good Div.3 round! (After https://codeforces.com/contest/1490).
So thanks for authors for their problems, and keep composing!
in problem d i used unordered map and time limit got exceeded but replacing unordered map by map ans is accepted how is it even possible .111012090 time limit exceeded 111111133 accepted
(
)
Worst case time complexity of unordered map is O(n)
Same Happened with Me. use this https://codeforces.com/blog/entry/62393 to design custom hash for unordered_map
thanks buddy
For question B what will be the output for-
11 2
....*.....*
It is invalid input
G was an easier version of https://ncna19.kattis.com/problems/earlyorders
My solution was skipped even though I neither copied nor showed anyone my solution.How can I prove that I did not copy?This is really disgusting.This contest was unrated for me but what if it was rated.Please do review this. My D problem matched with someone I neither know and neither follow
was not expecting you to cheat :(
I didn't
no one submission of d skip without matching of same code nd its not A its d almost all with honest submission have different code,,,Anyways please dont give contest in couple thing,I hope u will be honest from nect tym
Don't interfere if u can't help
My solution was skipped for this contest even though I neither copied nor showed anyone my solution.How can I prove that I did not copy?This is really disgusting.This contest was unrated for me but what if it was rated.Please do review this. My D problem matched with someone I neither know and neither follow