Привет, Codeforces! Это снова я=)
19 декабря 2016 года в 05:05 MSK состоится раунд Codeforces #387 для участников из второго дивизиона. Участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.
Этот раунд проводится по задачам второго дня муниципального этапа Всероссийской олимпиады школьников по информатике 2016/2017 года г. Саратова. Задачи были подготовлены силами Центра олимпиадной подготовки программистов Саратовского ГУ.
Хотелось бы сказать большое спасибо Николаю Калинину (KAN) за помощь в подготовке задач, Татьяне Семеновой (Tatiana_S) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также Владимиру Петрову (vovuh), Алексею Рипинену (Perforator), Михаилу Левшунову (Levshunovma), Михаилу Пикляеву (awoo), Алексею Слуцкому (pyloolex), Ивану Андросову (BledDest), Олегу Смирнову (Oleg_Smirnov) И Роману Кирееву (RoKi) за прорешивание задач и написание разборов.
Участникам будет предложено шесть задач и два часа на их решение. Разбалловка будет объявлена позднее.
UPD Разбалловка 500-1000-1500-2000-2000-2500
UPD2 Разбор
UPD3 Поздравляем победителей
Now this is what I call unusual time :D
Сон для слабаков!
5:30AM here...
It's cool :D...I'll try to join the contest...
You are lucky, It's 4:00 AM here :D
But I'm gonna stay awake till the contest starts :)
PN. Of course it's just an excuse, I think I'll watch some movies and when the contest starts, I'll sleep :)
Why at this time?
Bocause some people have day at that time.
What people? ;)
Half of the world
What is the number of people from the selected regions are registered on codeforces? I am not trolling or something — I am really curious.
It's hard to tell, Russia and China alone has over 10k users combined, but that also accounts for the western part of the country. (Western China should have much less competitive programmers AFAIK, but I have no idea about Russia)
Deleted
That's the spirit!
Deleted
Well u already have positive rating
Good luck and have fun:D
Просто интересно, для кого в такое время это проводят? Для охранников?
А что, сейчас контесты плотно идут, почему бы не дать шанс поучаствовать тем, для кого это время удобнее в силу географии. И охранникам, опять же.
Зато теперь все, кто может спросить "Is it rated?" спят.
Может быть авторы готовили контест для TopCoder и перепутали платформы?
iam gonna wait whole night for this contest !!! lets hope this contest bring positive rating change to all of us... good luck everyone :)
Its 05:11 AM here in India.
I randomly opened codeforces to check editorials and I am surprised by this highly unusual timing.
hope to get + ratings. :D
Contest==> 7:35 am to 9:35 am (IST)
Exam==> 10:00 am to 12:00 pm (IST)
But gotta do it, coz cant miss a codeforces round!
me too bro , I hope to increase my rating and and get full marks .
10am to 12am ? That's a quite long exam!
I think that this is the time, you Europeans and Asians, in which you'll know what people in America suffer. Regular codeforces rounds are at 10:35 here in Mexico, and I always have to skip classes to take them. But not today. Today is at the perfect timing of 20:05
So，good time，wish you good luck！
Thanks! Good luck to you too!!!
Amen
Утро начинается не с кофе :)
Never awake early for college first time only for CF.
8:30 PM, on a Sunday night? This has to be the most convenient time for a contest ever for NA people. Can we do this at least once every two months?
Completely support that motion
I can't believe that I have just left my pillow and blanket to participate in this Round I haven't done that before, even to watch GOT
Я встал в 4 утра. Но у меня отключили электричество... Пошел плакать((
This round timing reminds me of TopCoder SRMs timing.
Most TopCoder SRMs were hold at time like this and I had to wake up after the mid-night to take it.
But I think it deserves.
This reminds me of Google Code Jam Round 1A, actually.
i hope the round will deserve stay awaking for 4 am
Hopefully I can gain ~300 ratings from these two rounds so that I could rush a purple before the year ends.
Just 110 more to go =]
Congratulation！ U achieve it
Thanks! I think this is my first time that I don't fail any system tests, usually I look cool pre-system test then suck hard.
PURPLE HERE I COMEEEE
Edit: Woahh, 2000+ rating? That was unexpected!
congratulation!
It's 18:35 here. But I think it's a little early?
Sorry, it takes some mistakes...I thought it was #386
Can anyone explain how to do D? Is it dp (I was using a 3D dp table but couldn't implement it properly)?
No need of DP, you can do it with a min heap. Store the difference(number of summer days) between two consecutive winter intervals and process them from lowest to highest.
Ah that's a lot simpler than I thought it would be. And it makes sense when I think about it.
No, greedy works. Split the array into segments of negative values. Sort the distances between consecutive all-negative segments in increasing order and just keep using winter tires to join them.
the given test case in D , third one answer shouldn't be 2. If he wants minimum tire changes then he must club summer days with winter , if possible . According to that ans can be reduced to 2.
But then he would have used more than k days which he's allowed for winter tires.
I believe greedy works: on all the negative days you have to use winter tires. Pick the smallest interval (non-empty) that is bounded by two consecutive winter days, and fill use winter tires over that interval. Of course you have to account for the corner cases and whatnot.
Mine was a greedy one. I just kept cancelling any swapping between the two days with negative temperatures and the distance between them is the smallest until I run out of Winter tears. But I am still not sure that this solution is correct. :D
UPDATE : mine is incorrect :D
Greedy works just as other comments have stated, remember to always consider the final segment of non-negative temperature AT THE VERY LAST. Now I thought it a bit more I just missed a hacking opportunity on someone who sorted the final segment with the others.
Nice Contest.
Almost no hacking in this contest. There were literally no hacks in my room :o
Almost no hacking in this contest. There were literally no hacks in my room :o
I'm just gonna hope that means the pretests were decent.
I also think its because the solutions to the test cases were explained clearly. Also most tricky cases seemed to be given there too.
My idea around D was something like this:
Let's assign Winter Tyres
Wto all negative temperatures and Summer TyresSto others. Let initial answer be the worst case of exchanges required.Now, if we convert a segment which is of the form:
WSSS...SWtoWWWW...WWthen we reduce 2 exchanges. So, we try to cover the smallest segment first and greedily try to reduce exchanges this way.My implementation gave segfault on Pretest 3. Dunno if this would work — can someone point out where this could go wrong?
this was my idea too and got ac after contest. just remember to add first exchange and last exchange(which if happens, both will be 1).
If you have the last few days covered by S, consider replacing it with W to save one switch. Since you only save one, which is less than the normal two, check this case at the very end.
TFW you know that problem F is a problem about binary search and combinations but you suck hard at combinations... WITH 90 MINS LEFT.
void recursion(struct me, int remainingTime){
if(remaingingTime) remainingTime -= 0.1;}
I thought I was stuck forever.
Can you give an outline of your approach?
Use binary search to find the answer, and count the combinations of non-interesting numbers smaller than var(mid).
I didn't manage to find the combination formula though.
Use a vector of decimal based numbers will help during processing.
Edit: Whoops I was wrong. Seeing the tutorial reminds me that using dp to count the combinations is a common technique which I learnt in other round's tutorial...
How to approach E? I made a recursive function but could find no way to optimize it.
Use a stack to keep track the amount of children comments already posted for a comment, thus managing the depth of each comment.
a recursion solution may be helpful http://codeforces.me/contest/747/submission/23126041
Greedy... greedy everywhere
Bye expert! Just I was some hours blue
Just compete tomorrow and get it back!
I hope there will not be another contests at this time again.
I think it is a cool time during semester break. It's morning in eastern Asia so I could join the contest with a fresh brain instead of a tired one on the usual time.
The amount of people available on this time slot is really low though...
I agree with you about participating with a fresh brain but it's not a semester break for everyone. I'm working on semester projects now and it's 10 days away from the beginning of the semester exams.
I don't know if it's a good time for many members or not. but I didn't see anybody upset from the usual time.
What time is it now in your country?
It's 6:30 AM now.
C failed systest
opens the code after 10 secs
Such quick system testing !!!
What is problem D test 31? Any ideas?
I think it's some thing like this :
Considering segment [4, 5] gives optimal answer even though it's length is greater than segment [8, 8].
Wohooo! First place in my room for the first time! ...and I got WA on problem A because of uninitialised variables, how embarrassing :P
A reversed case for me. I saw someone's code could possibility cause RE since it could check out-of-bounds values, but I didn't have the courage to hack that guy.
He coded something like this:
int d[4], z = 0;
while(d[z] == 0)
why my source is runtime error in Problem E? http://codeforces.me/contest/747/submission/23126016
An unusual timing for the contest, the number of problems, and system checking was so fast! I like this contest
Last ACC in the Round :D
wow nice one! hope you become purple =))
I wish too :D
Is here anybody who solved D with binary search? :D
you know it was a greedy contest when nearly 400 solutions fail system test for D.
wasted whole time on D in search for a O(n) dp solution. :(
It's so hard to set a question which denies O(nlogn) while accepting O(n) though.
haleyk100198 you did very great today.
How did you solved D and E so fast?
For problem D I got a little bit lucky to notice the greedy approach, so I only have to spend some time on refining the code to handle the corner cases.
For problem E, managing a file tree is a quite common practice problem. (I am surprised that it showed up as a regular round problem E)Whenever I see such a problem I just go straight for stack, and there's no other tricks needed so I got it almost instantly.
Good morning! can anyone explain D for me? is it DP? i wanted to do this with 3x dp2D but i can't!
Check the comments above, there is a populated comment above which should guide you how to solve it with greedy.
So excited about being a Candidate Master!!!
although i solved 2 questions ,_ better than every time_, my rating points decreased ! could anyone explain to me the rating process and why i decreased please ?
here
I think your rating dropped because there were less number of participants.
This should explain how the rating system works: http://codeforces.me/blog/entry/102
Note that at this date, the division line is drawn at 1900, and you start with a rating around 1500.
Can anyone help me why 23126693 got WA?
You made a mistake to consider the final segment of non-negative days with other segments.
For example:
10 8
0 -1 0 0 -1 0 0 0 -1 0
Your code considers to use the winter tire on segments : [2, 5] and [9, 10] (1-based), as it recognises the last non-negative segment [10] has the best greedy value, but the correct answer should be [2, 9] as using winter tire on [6, 8] further reduces the result.
thank you for helping!
try this case:
Answer should be 2 instead of 3.
In problem 747E - Comments, my code receive TLE in maintest 9. However, when I resubmit the same code, it get TLE in test 29.
Here is my code in the contest: 23123300.
And here is my resubmitted code after the contest: 23128262.
You can use compare button to check whether they are same.
I so worry that may people could fail system test because it (not me because I still fail with test 29)
I don't think this should be a concern as your code was very close to TLE on test case 9 in both submissions. It is known that CF running time has a delta of around 30ms, which should not cause problems to most submissions. (As always, you run a risk of submitting non-optimal solutions)
Thank you very much.
http://codeforces.me/contest/747/submission/23124311
Can someone help me find out the mistake i made in problem C .
You should prioritise using the unoccupied machines with smaller ids, instead of the ones who were released earlier.
I think your mistake is that you do this (servs[i].f=(t+(d-1));). If only x (x<k) servers are available, you print -1 but don't reset the ending time of those x servers.
I woke up early for the round 386, waited for this round and will wake up early tomorrow again for next round, hopefully there are more often 'daily' rounds
why for this input:
10 5
1 1 1
2 1 3
3 2 3
4 1 1
5 2 1
answer is : 1 1 5 4 5, but not 1 1 5 4 7 ?
at second 1, there're 10 unoccupied servers and we need to occupy 1 sever for 1 second , sum -> 1;
at second 2, there're 10 unoccupied servers and we need to occupy 1 server for 3 seconds(sec. 2,3,4), sum -> 1;
at second 3, there're 9 unoccupied servers and we need to occupy 2 server for 3 seconds(sec. 3,4,5), sum -> 2 + 3 -> 5;
at second 4, there're 7 unoccupied servers and we need to occupy 1 server for 1 second, sum -> 4;
at second 5, there're 8 unoccupied servers and we need to occupy 2 servers for 1 second, sum 3 + 4 ??
Notice that you should use server 1 and 4 for the final task.
For problem E, I traversed the string once and stored the strings at the index of its level in a vector and later displayed the contents of vector level wise. The total memory taken by the vector will then be equal to the memory taken by the string.
But I am receiving a runtime error on system test 26.
http://codeforces.me/contest/747/submission/23129959
Is there something fundamental I'm missing out? Thanks for any help in advance.
I am not sure about this, but line 105 seems to cause out of bounds problems.
Its due to out of bounds.
Use this while condition instead- while(i<n && s[i]!=',').
Here is your AC code with the modification-23130499
Yes it is. Thankyou very much!
Hello, I have a small doubt regarding problem E. My submission 23125639. The code for converting string to integer is
for(int i=0; i<lol.size(); i++) cnt[(j-1)/2]+=(lol[i]-'0')*(int)pow(10, lol.size()-i-1);This is giving me wrong answer on test 18. But when I replace this with the inbuilt function, atoi(), the code is getting accepted. I'm unable to understand why. Help would be appreciatedThe power function returns a double type value which on conversion to an integer might cause some precision issues. Use a custom power function instead.
For powers of 10, I don't think there is any problem with precision. If there is an error, it'll occur in the decimal places and it'll be ignored. Is there any case where a this conversion won't work? Thank you for your reply
pow(int, int) actually calls pow(float,float) (or pow(double,double)). There are two problems:
1)float can represent correctly (with no error) only integers with less than 6 digits.
2)int(0.99) is 0 and pow() gives us only estimated value. It might give you 9999.99999 when you ask for pow(10,4). And it will be rounded as 9999.
I forgot that pow can return a number slightly lesser than the number. Thank you for the clarification.
Besides the precision problems, I think you should also learn the stoi (and stoll, stod etc.) functions, that helps a lot with converting string to numerical values. That saves a lot of time for coding a function that does the same thing.
Thank you for the advice
thx a lot for these consecutive contests (#387,#386,#385,#384)...it helps our ACM team for ICPC-Tehran Region
Doesn't the problem B statement says coordinates to be lie between -1000 and 1000. But the output of the judge is considering the coordinates outside this range.
I assume that you are talking about 749B instead of 748B.
The range of x, y coordinates is only applied on the input, you can output any legit integers in the output.
Hey, can anyone tell how to solve D using DP? It has a DP tag, and I am practicing DP questions, so I would be more than grateful to know about that! :D