Заметьте необычное время старта.
Привет! В 28.09.2020 11:05 (Московское время) начнётся Codeforces Round 674 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд в основном состоит из задач первого этапа Всероссийской олимпиады школьников в Саратове и будет проведен во время реального соревнования. Задачи были придуманы и приготовлены Иваном BledDest Андросовым, Александром fcspartakm Фроловым и мной.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда. Также спасибо Артему Rox Плоткину и Дмитрию _overrated_ Умнову за обсуждение идей и тестирование раунда!
Удачи!
UPD: Спасибо Ивану MrReDoX Ушакову, Ивану Ivan19981305 Георгиеву и Дмитрию nuipojaluista Кадомцеву за тестирование раунда!
UPD2: Разбор опубликован!
*Notice the unusual start time.
Thank you so much!! I would have missed it.
I think vovuh should update the blog mentioning unusual start time.
weird time tho
Sorry cannot participate because of the practical class at the same time
Same but I am bunking them.
Gonna get my ass kicked for codeforcing at work xD
Me Also. xD :) (
)
Why so unusual start time ?? :(
"This round consists mostly of the problems of the first stage of All-Russian Olympiad of School Students in Saratov and will be hosted during the real competition time."
I See, its going to be fun then!!!!!!!!!
Чтож. Прийдется во время уроков с фейка писать.
So unusual time. Its lunchtime here in India.
And the standard time is dinner time ;_;
dont say lunchtime...it confuses with codechef lunchtime ....lol
but lunchtime is at dinnertime
All-Russian Olympiad alright imma skip this one
This is the first (of 4) level of Russia National Olympiad. Problems usually are really easy.
I am trusting you
me too
Me after remembering the previous div2 contest based on russian Olympiad for school students: i am gonna skip this because of unusual time.
Its Div-3 bro, what do you got to lose, its unrated for you
really wanted to participate but wont be able to due to my online classes.hope for some magic
you guys are attending online classes?
No, TBH.
F**k online classes. They are not worth attending!!
I am skipping classes.. not worth enough a CF contest lol.
i am also skipping my class
Really excited for this contest, but it's unusual time is not suitable for most of the college students in India as we have online lecture at that time.
you guys are attending online lectures?
submit F in last 5 seconds and find my output is following:
instead of
Hope my solution is wrong XD
Round is not even started yet, but u already submitted, Ur coding speed is so enormous!
I miss the golden time in which I can delete the misplaced comment. T_T
well looks like your wish came true xD
Deleted for posting at a wrong place.
Too bad this contest is Div 3.
Gonna wake up at 4 am(my local time) for this contest! Very excited!
Time too bad. Have classes. Any after 3pm UTC works fine.
Every time I want to improve my CP skills, my college is letting me down and this is another example.
It would be pretty good if CF were in this time rectangle in the future.
Another suitable time for Chinese......
But "based on" makes me afraid!
I can finally have a CF competition and have not to sleep at 1:00 in China :)
Don't be afraid!It isn't hard at all!
Oops, sorry It was the wrong post :((
Coding is love.
Same here bro xdd
vovuh score distribution plzz..
There are no score distributions in Div.3
IN INDIA IT's OUR ONLINE CLASS TIME
It's impossible to conduct a contest such that time will be suitable for everyone across the world.
This is the first time a div3 round is not rated for me!
idk i just want to share this
After a long time, a rated div3 for me :P.
glhf
How to solve F?
we want to count the total number of abc, ab?, ?b?, ???, ??c, a?c, a??, ?bc subsequences occurring in all the strings, we can replace ? with the character that we need to make it abc. I've named variables for better understanding. In my code, k = count of ? so far submission
how to solve c?
For this, I got a pattern of the required number of moves like
0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, ......Hope it will be helpful.
Took time for figuring that out. Found editorialist solution more easy btw.
Suppose we perform the +1 operation $$$x$$$ times and the duplicate operation $$$y$$$ times. Clearly we want to perform all the $$$x$$$ operations first, so that each subsequent $$$y$$$ operation adds as much as possible. Then the sum of the array will be $$$(1+x)+y(1+x)=(1+x)(1+y)$$$. We want $$$(1+x)(1+y) \ge n$$$, so each of $$$(1+x)$$$ and $$$(1+y)$$$ is either $$$\lfloor \sqrt(n) \rfloor$$$ or $$$\lfloor \sqrt(n) \rfloor+1$$$. Then we can just try the cases.
94077437
so each of (1+x) and (1+y) is either ⌊(√n)⌋ or ⌊(√n)⌋+1. Then we can just try the cases.
i didnt get the last part how this is possible?
and why the solution does not go beyond the root n thanks
If we want to minimize $$$a+b$$$ and want $$$ab\ge n$$$, then we want $$$a$$$ and $$$b$$$ to be as close to each other as possible (just try a few values... it's very intuitive). That means each of $$$a,b$$$ must be around $$$\sqrt{n}$$$. In this problem, $$$a=1+x$$$ and $$$b=1+y$$$.
it is better to increase 1 up to some number let say x and then append this x up to when the array sum becomes equals or greater than target value n
here x should be the floor(square root of n) or 1 plus to this value
here is mine solution 94092529
what was the testcase no 10 of problem D??
Something like this.
5
-1 1 -1 1 -1
What will be the correct ans for this
4
Can some one give me idea about B & D
thanks in advance
for B: if any 2x2 tile has diagonal element same then answer will be yes, keep in mind that tile length and width is 2 so the the resultant square will be multiple of two
Problem F is exactly the same as ABC104 Problem D
How to solve D neatly ? I can think of one way where we count the disjoint subarrays with zero sum.
Think of it as you have, say $$$k$$$ intervals (imagine as segments on the $$$x$$$-axis, from $$$interval[i][0]$$$ to $$$interval[i][1]-1$$$) and each interval has elements that sums to $$$0$$$. Now basically, you need to find the total number of vertical lines to make, such that every segment is cut at least once. Implementation
How to solve D? went upto prefix sums and thought if prefixsum[i] is 0 or has already occurred then add 1 to the answer but it doesn't seem to work because segments can collide. Can anybody explain a neat approach?
i counted all the segment that collides in one then also ans was coming wrong on testcase 10 anyone can explain
went up to prefix sums and thought if prefixsum[i] is 0 or has already occurred then add 1 to the answer— it's perfectly okay till now then you just need to clear your container and do everything that you need by assuming the current position of the array as the starting position. Hopefully, it will do your job.Think of it as you have, say $$$k$$$ intervals (imagine as segments on the $$$x$$$-axis, from $$$interval[i][0]$$$ to $$$interval[i][1]-1$$$) and each interval has elements that sums to $$$0$$$. Now basically, you need to find the total number of vertical lines to make, such that every segment is cut at least once. Implementation
Can someone help with with this submission? I could not think of a testcase that fails. 94110488
your code will fail for when n=1 and X =1 Cuz (1-2)/1=-1 So else part will give -1+1=0
Bruh there goes my rating
Thank you
Did codeforces recently changed the rating formula?
I dont know but maybe this might be the reason...the number of participants is less hence you may see less change in delta even if you have good rank.
Yeah, I thought that I was really hoping to touch expert but nevermind I try next round.
Yes and I wanted to be specialist..sed..next round.
I followed you, and I think if you are not hacked, you will turn blue.
Excuse me! Why is E like A in terms of difficulty?
The fact that it is E has psychological effect hence the number of solves is almost 10 times less then A..despite the difficulty level.
Number of solves is 10 times less mainly because there are 3 more questions between A and E which people attempt, and mostly move ahead only when they are done with those.
There is a general thing. People can solve A because its A, people cant solve E even if its easy cause thats E
There is a question: I did not participate in this round because of something. If I hack someone, will I be rated?
No
I started the contest half an hour late... yet managed to solve A,B,C,D ! Today was a good day for me!
Thanks vovuh for the awesome round :)
Why good day? You managed to get lot of penalties with better performance due to be late
Today's Div. 3 (Round #674):
The advantages of being a Chinese have been revealed ：） The start time is 16:05 for me.
Is there any benefit for successful hacking, in this round?
Why don't we go beyond sqrt(n) in problem C ?
is there any point for hacking in div3?
Can anyone tell me on what test case my solution for B fails? It is hacked. Here is my submission.
1
2 2
3 5
6 4
3 6
5 4
Your code print YES. But the ans is NO
Can someone explain how hacks work for ICPC-style rounds like this one? Is there any competitive reward for successful hacks?
Hands down the best contest I have participated in so far!
Can anyone explain how this works:
Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.I see xin_chen, CupCapCup and midheight at places [3, 4 and 5] accordingly. But that doesn't seam right: Their places are increasing but their (finish time + #WA * penalty) is decreasing >> [ (55 + 4 * 10) == 95 , (70 + 2 * 10) = 90 , (62 + 10) = 72] Plus, their number of WA decreasing: [4, 2, 1] but Penalty is increasing: 188, 193, 199 — it could make sense if their finish time was increasing, but it's not the case.
How to make any sense of it? Thank you in advance.
The penalty of xin_chen is: 2 + 9 + 13 + 27 + 42 + 55 (number of minutes since the start until the task is solved) + 4 * 10 (for WA) = 188
Hope that will make it clearer
Wow, Super! Thank you, that made everything clear.
Why my rating is still not updated?
Will it not be rated for untrusted participants? As my ratings haven't changed yet, being < 1600 and already 5+ hours have passed after the end of the hacking phase.
This is because they might be working on the plagarism tests now and removing the cheaters.
As I am new to Codeforces so can anyone tell me that in this contest will I get any rating or not because I have solved the 3 questions but and also got my rank but not any rating and even in my contest section it is not showing anything.
please help me out?
Wait for some time, it will get updated.
When are the ratings going to update for this round?
The same question
Within 12 hours after completion of hacking phase
Isn't it over?
Why hasn't the rating updated after the contest? it's almost 24 hours now...
system testing just begins,omg
When the ratings will be updated?
Hi everyone! Can someone please help me with this solution from ecnerwala. How did he find max-flow in non winning edges in the code here — https://codeforces.net/contest/1426/submission/94072786
How did he arrive at that one liner solution? Just a little insight will be very helpful.
Thanks a lot