И снова привет, Codeforces!
17 декабря 2017 года в 09:35 MSK состоится очередной раунд Codeforces #452 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Обратите внимание на необычное время начала раунда!
Раунд будет рейтинговым.
Этот раунд проводится по задачам второго тура муниципального этапа Всероссийской олимпиады школьников по информатике 2017/2018 года г. Саратова. Задачи были подготовлены силами Центра олимпиадной подготовки программистов Саратовского ГУ.
Хотелось бы сказать большое спасибо Николаю Калинину (KAN) и Григорию Резникову (vintage_Vlad_Makeev) за помощь в подготовке задач, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также Алексею Рипинену (Perforator) за прорешивание задач.
Участникам будет предложено шесть задач и два часа на их решение. Разбалловка будет объявлена позднее.
UPD Разбалловка 500-1000-1500-1750-2250-2500
UPD Дорешивание, виртуальное участие, а также возможность просмотра решений и тестов будут отключены до окончания олимпиады в Саратове через 2-3 часа. Надеемся на ваше понимание. Разбор также будет опубликован после конца олимпиады.
UPD Поздравляем победителей!
UPD Разбор
Эх, а имя vintage_Vlad_Makeev с анонса прошлого раунда так и не пофиксили. Или его действительно зовут Григорь (что-то между Григорием и Игорем)? UPD. Пофиксили, значит, не Григорь.
You wrote two consecutive rounds! Wow!
You wrote two consecutive rounds! Wow!
UPD Never mind, I didn't know that the rounds were based on Olympiad. Sorry.
This round is the based on problems from the same contest as today's contest. Does this mean the round, Div 2 in particular, will be of similar difficulty to today's round? It was a great round (personally anyway), don't get me wrong, but it was definitely easier than normal.
Many people solved problem D and E in today's round.
LOL dude i thought i was going to end up like you at the end of the contest but i messed up really bad today
Why is it so late?
You mean early? That's how time zones work mate.
Пересекается с олимпиадой Иннополис
In this month will be some codeforces round
1:35 PM in Hanoi.
It would be good if my class wouldn’t start at 3:00 PM... :<
You can solve this issue recursively! If you know what I mean ;]
i hope that this round's problems will be as difficult as the previous round's problems
so as the queue
Нужна помощь по задаче (не этот раунд). Если есть кто-то, кто может помочь, пишите плз
First contest without Russians?
Not really :D
But lots of Chinese：D
An UTC+8-round :)
While is the upd point for each problem?
1:35 AM in Cuba , nice!!!
I really hope this round will be better than the round before.
Six problems? Sounds good. And the time is quite friendly to Chinese participants :)
The classic: Is it rated?
All right... It seems that today's problems are much better than yesterday's. I like this round very much. -- Though my B was hacked.
6.35am(UK) is so early XD
the last contest in Cuba was at 6:30AM and this contest is at 1:35AM , very early XD
asd
apparently the link described in the rules,
http://codeforces.me/blog/entry/456 and http://codeforces.me/blog/entry/4088
was not found on Codeforces's server on my end. anyone know how to access this?
...damn it. it was two links. i'm stupid.
wh2001_ZY will solve all problems in the contest!He's the best!
whan I want to hack, I couldn't see other's solution .
why????
You lock your solutions in the dashboard before hacking other solutions, but beware, after locking your submission you won't be able resubmit any solution after
How to solve D and E?
I got no idea for D.
For E, though I was not able to submit because of too much code writing but my idea involved range min query and lazy propagation.
I think E requires some clever use of data structure like set . Couldn't get AC though because of time but I think my approach is correct.
I solved E simulating the array with set and map
Yes. That's what I did . but got wrong answer in pretest 7 . Finally when I corrected my solution , Contest was already over. screwed up badly !
Sorry man. But dont worry, I also had a bad contest :)
Hi , TwiceBig I was not able to solve E in contest timings Will you share your thinking and solution , that would be really great.. I am attempting the problem now, your method will surely help..
Thankyou.
Hi. Well basically what I do is simulate the array using a set. For that I store a pair of integers. First frequency and second what position of the array it is. Since set has data stored by minimum, I store The first value as negative. Also I have an extra map for helping me in the merge. While there is something in the array ( the set ) I erase the first value of the set, cause it is the next range that has to be erased. When I remove an element I search the left and right element with lowerbound in the map. And if left and right has same value I merge them. So I have to remove from the set the left and the Right. And add the new pair I just merged. And update the map. And that's all. Hope it helps
good approach.
33347025, got AC with Disjoint Set Union. Each connectivity component — is segment with equal elements. I kept this components in set, selecting component with maximal size. Time complexity approx O(N log N)
20 31 31 30 31 30 31 31 28 31 30 31 30 31 31 30 31 30 31 31 29 Взлом для B
Ответ YES?
Да
I thought I finally found the bug right before the end, but still WA on pretest 4! What's pretest 4 on problem D?
n is 109
You should note that there is no shovel with the price of 0.
I got stuck there too. Costed 4 submissions and a whole fortune of time.
what's the answer for n = 1000000000? Ishan.nitj
I think I made sure there is no shovel with the price 0! Don't know what got wrong?! AkiLotus
5 * 108
gives correct answer. I checked this at first, this is not pretest 4
how to solve C? my recursive solution fails on pretest 5 :|
Make cases for each remainder of n with 4.
If you want code and some help, you can have a look here.
Code — https://paste.ubuntu.com/26200030/
I just found a segment of numbers which sum to (sum_of_sequence) / 2
Not sure why it works, and if it's correct(did pass the tests though)
I just got my solution for problem C accepted with only linear loops (
O(N)time complexity), but my approach looked pretty weird I think. I did think of modulo 4 but I didn't write code that way. Can anyone suggest or show me proof of correctness? http://codeforces.me/contest/899/submission/33346265Get the sum of the first
Melements. Get the absolute difference of it and the sum of the rest.Mdoes not exceedN/2.Get the sum of the last
Melements. Get the absolute difference of it and the sum of the rest.Mdoes not exceedN/2.Get the sum of the middle
Melements. Get the absolute difference of it and the sum of the rest.M = {N/2 - 1, N/2, N/2 + 1}.I wrote a little code brute-forcing all the cases and notice that with some N there exist solutions where the middle elements are chosen, and with some other N there exist solutions where the first (or last) elements are chosen.
Any hint on what's 7th pretest in E?
I got it wrong because I wasn't recalculating the lengrhs correctly after merging, if that helps.
I think something like 13 1 1 1 2 2 2 3 3 1 1 2 2 1
try this case:- 1 3 3 3 2 2 3 3 3 1
thanks..found the mistake giving 5 instead of 4
I have this one that is easier to debug:
7 1 1 2 2 2 1 1
Answe should be 2.
Очень классные задания!!!! Спасибо, было ооочень интересно решать))
in the end of contest, i tried open hack attempt page but it not opened two min
so sad..
Another nice round. It's harder and suits Div.2 better though. Cheers. ;)
Problem D. Shovel Sale ********* Note that it is possible that the largest number of 9s at the end is 0, then you should count all such variants. **** if they neither give n<5 in pretest and nor in announcement then standing will be completely different.
They did give n < 5 in the pretests, because I failed on pretest 7 before checking this condition.
thst's what i am saying If they don't...
They did give n < 5 on Pretest 6. I realised, two Runtime Errors and one WA later.
I'm sure n < 5 was given, one of my submissions hardcoded the values for n < 5 incorrectly and it worked once i fixed that.
If n=4? Please tell!
answer will be 6. 1 2, 1 3, 1 4, 2 3 ,2 4 , 3 4.
Shucks I didn't consider this. I was like n<=4. cout<<0<<endl; Stupid me. :/
I did that too, but got a WA. Then corrected it for an AC pending systests
Exxxxxxx! I didn't understand! **** Note that it is possible that the largest number of 9s at the end is 0, then you should count all such variants ****
If N < 5 then all pairs making up sum ending with no 9 are counted. Refer to Enigma27's comment. Right at 5 the answer will be 1 since there exists one pair (4, 5) making up the sum 9 having one trailing 9. You can hardcode the case N < 5.
i didn't like the recent contests on this site :)
Ok
people disliking my comments 4 good ure all just haters
True nigga true
What was your Hack test case for B?
20 31 31 30 31 30 31 31 28 31 30 31 30 31 31 30 31 30 31 31 29 Answer "YES"
*28, not 20
Edit: My bad, it's right
20 is n
Sorry
lol
Hehe...
Thanks a lot for the suitable contest time. Due to the inconvenience of the time zone, it's really hard for me to find a CF contest to enter when I am not sleepy...
// Although today I realized contests wouldn't become easier for me when I'm awake :(
Hints Clues Solutions anything for D?
http://codeforces.me/blog/entry/56391?#comment-400946
I'm not sure this is the right solution. I want to hear a solution for D too.
Yeah I was thinking something like that too but failed the pretest #4
The system testing is starting now, but upsolving, virtual participation and viewing solutions and tests will be disabled till the end of the olympiad in Saratov (around 2-3 hours from now). Hope for your understanding.
UPD: Everything is up now.
I was able to see solutions :\
I noticed the lack of graph, DP, combinatoric and geometry problem in this year Olympiad.
what is C pretest 5?
overflow
DIV2 A IS SO HARD TO UNDERSTAND PROPERLY DUDE!
Wrote a simple stack solution for E after contest. I would be so suprised if it passes, but I dont know why it shouldnt pass. Is it possible that E is this easy? Edit: No its not, I didnt real statement carefully lol.
I think that order of removing matters, without handling that I got wa on pretest 7.
Order does matter, but I dont think it will be problem in my solution. We will see soon.
Everybody in Russia uses Gregorian calendar. In this calendar there are 31 days in January, 28 or 29 days in February (depending on whether the year is leap or not)... People like me have no idea that leap year means 29 days in Feb....
when wil be rating changes
How to solve C without knapsack?
My approach: if n=2, just like pretest. else:
1.Put n in set 1 and n-1 in set 2.
2.For each other element (n-2,n-3,...,1), just check (in descendig order) if it's better that the element goes to set 1 or 2.
How to prove that always works?
I solved it using a simple approach.
find the sum of integer from 1 to N.
if sum is even number then answer will be 0 otherwise 1.
in both the cases method of finding the numbers are same,do the half of the sum of 1 to N and store it in a variable called SUM.
then start from (i=N ; i>=1 ; i--) and do this if (SUM — i >= 0) then subtract i from SUM and push_back i into you answer.
you will get your answer vector.
I also thought of same logic but could not submit correct code in time . btw how do u prove your claim?
I wrote down some test cases on copy and checked it manually...
you can think like this if you are subtracting a number from SUM and then your SUM becomes less than zero it means that you need to subtract a number which should be smaller than current number and i am going from N to 1 so it is sure that i will get that number.
I just wonder, if someone can tell me why I am disqualified?
probably because you cheated
how? how did he cheat. ??
Because you, Birjik, used fresh account to take part. It's ugly, unethical, disrespectful to me and the community.
How did you know? There must be other users using fresh accounts too.
I wonder how did you detect his fresh account through his submissions?
First of all, it's not Birjik even though we do share same template code.
Secondly, my real username is banned from CF (due to I cheated once a few years ago) and I gave you my sincerest apologies for that (several times), and asked to be unbanned in my real account.
After several attempts, I even changed my PC and could somehow login and was eligible to participate in contests from my original account, but some times later, I couldn't even login into my account. After 5 mins of logging in, the site takes me out and I have to login again. Moreover, in most of the times I can't even register to the competition (due to my account was banned).
I already noticed organizers about that issue. Didn't receive any reply. Okay.
Well, so I decided to create my new account since I can't normally participate in competitions from my original account and this decision was made by me not because I do wanna cheat, I just don't have any options.
How to solve problem-F?
I saw some submissions for D with Digit — DP. Can someone explain their solution using Digit — DP ?
for problem C: I noticed that the difference between every two adjacent numbers is 1. So if n is even, there will be two situations:if n/2 is even, answer is 0, or answer will be 1; Similarly, if n is odd, there are also two situations:if n/2 is even, answer is 1, or answer will be 0;
What??? Is it semi rated???
Good contest, the problemset was perfect. We want more contests like this.
Yes very true. All-Russian olympiad problems are good
Hi,MikeMirzayanov,can you tell me why I got disqualified? I didn't share code with anyone else.
Because you created fake account to participate bro. It's ugly, unethical, disrespectful to me and the community.
Because you (maybe a group of people, and I'm not sure who) used a fresh account to take part. It's ugly, unethical, disrespectful to me and the community.
I wonder how these two accounts can participate round 441 at the same time with different codes and different verdicts...
whats wrong with using a fresh account to take participate. i don't get it ??
Maybe it is because of this comment
It's a rule.
I want to know why I got disqualified,too.I didn't share code with anyone else,either.
My friend eselppa got disqualified in yesterday's contest too, he solved all problems by himself, he didn't cheat, I can prove it. The reason why this account's ID is very similar with mine is that he wants to play a joke to me. That's not my account.
But he used fresh account to take part. It's ugly, unethical, disrespectful to me and the community.
Didn't you also use a fresh account to take part when you first participated. It's ugly, unethical, disrespectful to me and the community.
Exactly correct.
I found a new problem ... How many "It's ugly, unethical, disrespectful to me and the community." in the replies of this comment. since the answer may be very large print it module 10^9+7.
UPD : You also have to consider the occurrences in the replies after this reply.
Stop making jokes about cheating, it's ugly, unethical, disrespectful to me and the community.
Good god how did this become a memeful copy-pasta so fast dude. I mean it's ugly, unethical, disrespectful to m-
Why I can't submit now?? The contest is over and the system testing has finished ...
Refer this http://codeforces.me/blog/entry/56391?#comment-400964
Now you can submit~
hello in your contest in b problem you gave test cases that there is two contiguous leap years but its impossible in real (one of them is test case 13) please correct it
Leap years are ones with 29 days in February not 28.
my bad :(
Look at all the people who failed problem B. They all did same mistake as you. It's because of the problem statement, January, 28 or 29 days in February (depending on whether the year is leap or not) , which gives an idea that correspondly leap has 28 days and not leap has 29 days.
Когда не сдал D
Hello, I found a very weird bug in my code for problem E. It works fine for many test cases except for the case when n = 2 and the 2 numbers are distinct. I checked on my local machine and it gives the error.
Checking on gdb, I find that the pointer
majtremains the same asmait, even though I'm doingmajt--;which should make itma.end()if we are removing the first number (Note that this works for other test cases, i.e. n!=2, even for n=1). I'm unable to figure out why. Any help would be appreciated. Thank you.Code ID: 33351982
Well,the time is best for Chinese!We always had to stay up late for the CF round :(
666!
Relatable here, GMT+7 :)
Why are submissions not being judged?? I submitted 4 hours ago and it still writes "in queue" as status. :/
Why crash?
http://codeforces.me/contest/899/submission/33344155
You are erasing from set at the same time you are iterating over it. So when you delete an element the inner structure changes. You should create a temporal set and erase from it
в условии написано "в феврале 28 или 29 дней (в зависимости от того, является год високосным, или нет)" значит из условия понятно, что 28 дней високосный, а 29 не високосный, как бы соответствие между ними но на самом деле все совершенно наоборот
Wrong answer on test 7 on problem F. Anyone have any idea? I am unable to find my bug. I have tested several cases but couldn't find anything.
Here is my submission 33357864
[Deleted] I post it on the wrong topic.Sorry.
What's problem with this E code? 33382017
Hi,MikeMirzayanov,can you tell me why I got disqualified? I didn't share code with anyone else.Please give me a reason.
Because you, czr, used fresh account to take part. It's ugly, unethical, disrespectful to me and the community.
Oh, you're really ugly, unethical, disrespectful to me and the community. As far as I'm concerned,you,it's your third fresh account! You should be banned by MikeMirzayanov in no time. And I can't imagine a more ugly and unethical behaviour than using a fresh account to point out that I used a fresh account!
What's more,I do not use a fresh account and it's the first time I participated in a CF Contest!
I've been stuck for ages... anyone know what test #33 was on div2E? http://codeforces.me/contest/899/submission/33345602
My answer is 1 + the correct answer. :(