Привет, Codeforces.
Скоро, 27 июня в 17:00 MSK состоится очередной, 310-й раунд Codeforces, задачи для которого готовили я, Андрей Сергунин, и Егор Щербин (Lord_F).
Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.
Участникам будет предложено пять задач и два часа на их решение. Разбаловка будет объявлена позже.
Желаем всем удачи!
В раунде будет использована динамическая разбалловка.
UPD: По техническим причинам раунд перенесён на 10 минут.
UPD: Добавлена предварительная версия разбора.
UPD: Поздравляем победителей:
Div 1
Div 2
Фан-картинка к контесту, которую Андрей почему-то решил не прикреплять к анонсу:
Thanks for the schedule change!
Looks like my ranting served its purpose :)
Hey! Why the downvotes ?????????
I'm happy because we'll have another contest tomorrow and it's at a different time than usual. The other day I was complaining because contests are always 19:30 MST, so now I'm thanking for the schedule change.
I assumed the time was as usual and couldn't compete. I guess I'm going to have to check each time now.
Your curve is very inspiring :))
Yes, how do they do this !
Почему не на главной странице?
UPD: В то время пост не был на главной.
Consecutive Div1 + Div2 Contest :D
Good luck all, hope a good rating for all.
Мне показалось, или раунд сначала планировался на вечер пятницы?
Я не против переноса, просто я запланировал для себя участвовать в одном раунде на любом из сайтов один раз в неделю (Topcoder, Codeforces, Hackerrank и прочие), но в удобное для меня время. В понедельник я решал, какое соревнование посетить, выбрал это, но тогда была указана пятница. В итоге, я пропустил все остальные соревнования, а это вдруг перенесли на субботу, когда у меня нет никаких шансов на участие. Обидно.
Finally a contest on a day off from work! There isn't a better way to enjoy my free time! Great ratings for all!
I have been waiting for an early contest (10pm in my timezone) for so long, thank you very much XD
+1. It's my timezone too. As well as 24% of the world's population. Here, recent Codeforces rounds typically start at 00:30 and end at 2:30 am. I find that in the middle of the night I can write code reasonably well, but seeing the solution to a problem is very hard, even for problems I find easy in the daytime.
I'm not complaining, because I think it's exactly right that Codeforces should optimise contest timing for the western Russia community, as a first priority. 19:30 in Moscow seems good if it encourages having an early supper, which is healthy :) For some odd reason, however, TopCoder contests don't cater for Americans very well, because they also run most frequently in the middle of the night in my timezone. It might be because (a) there are some cultural differences, or (b) empirically this time maximises participation.
Not a great time for some muslim coders that keep post. Contest is intersecting with iftar time:( In Tajikistan we can enjoy only one hour of contest.
i'm agree with you
for me this time is just perfect, before three days because of the round #309 I had to delay my iftar time(eating time after fasting) by 1 hour and a half in order to participate in that round.
and also as clearly we can see most comments in this blog liked this time change so I think administrators really need to consider using various usual times instead of one usual time, that helped a lot of coders even if the times are not far from each other (like this one it's only 2 hours and a half different from the usual time)
Same here from Jordan, Ramadan Kareem :D
Same here in Egypt :D
Izi problem, izi life
Na2a получил за "Izi problem, izi life" +21, а Anuar -48.
Почему?!
UPD: Все ок)
прост)00)))
Прост я победитель по жизни)
Ава решает!
Great time for Korea! It used to be 01:30-03:30, but today it's 23:00-01:00. I(and many) always wanted this...
i wish all of you have great contest
Good for some, not good for others. This will always be the case.
But at least it's different than usual, which means a chance to participate for coders who usually can't take part in contests due to intersection with work/school/etc..
With varied schedules, if you can't take a particular context, you may be able to take the next one.
why downvotes ...
It clashes with Challenge24...
I think we all know where is must to participate. :)
مینداختی بعد افطار دیگه
time is not good
it will be my 6th contest as a Div — 1 contestant . All my previous five attempt was so pleasant that i kick out to Div — 2 everytime :p i hope this time i will survive :D
just solve first problem quickly(or at least not very late) and your rating will raise
Easier said than done (For new candidate masters!) :D
shakil_AUST your graph is really inspiring. :) Best of Luck
Well i hope if i able to come Div — 1 again that time i will try my best to survive Div — 1 :D thank you for supporting :D
It's a good time to start the competition.
It's a bad time for muslim users
01010100011010000110000101101110011010110010000001111001011011110111010100100000001100010011011000100000
don't want a maths contest this time :P
So any body know wich kind of problems AndreySergunin usually gives (graph , math , dp ... ) ??
Usually he doesn't give problems cuz it's his first round, btw. Let's wish AndreySergunin and Lord_F good luck!
Thank you mister sherlock . Btw Lewin prepared his first round last time but he was preapring problems in topcoder so peoples have previous idea about what he post .
U r welcome, Dr.Watson :) I can almost certainly say that they didn't prepare TC rounds either
Waiting for the contest.
First image has the best size :-|
I hope there aren't math problems.
:-|
Why?
All of computer engineer love math problem .
it is not because i dont like math, i just like data structures, sqrt decomposition , graph theory more.
Maths problems is sometimes interesting(brainstorm). But too many maths problems will make my brain feel tired.
i think that the best programming contest are those wich involve lots of math !
But you are mathlover D: D:
I with Kronecker made math-only contest, but Zlobober unfortunately rejected it.
Because most of people don't like maths problems, which seems boring in their eyes.
Math makes mathlover Tired.
During this contest, I am struggled with div1C. I tried to solve it with two segment trees... However, I have never played with segment trees for months... At last I failed... I think I should train my data structure skill.
Мне кажется что это не совсем точно отражает действительность. На самом деле будет предложено 7 задач, но по 5 задач для каждого дивизиона.
Почему-то я вспомнил это.
I wish I will have a better rating,Thank you very much.
nice time，Hope I can go to div1
bad time , Hope I can return to div2
is this a joke???
ooom myabe
nope!!! i believe it
You are crazy
Do you guys use information from the scoring?
No，I don't use it,I only sovle problem by their order
delayed by 10 mins :(
It's delayed for 10 mins ):
10 min delay again
Первому раунду, начавшемуся вовремя будет выдана ачивка.
scoring ??!
Dynamic
thanks
This Time Is Better For Contests ..
UPD: Due to technical reasons round is delayed by 10 minutes.
it seems that another chance for authors to delay score distribution :D
Even though there is nothing about score distribution in English version of the post, the Russian version of it says that the score distribution will be dynamic.
может кто нибудь обьяснить как изменяется вклад у участников, почему у меня -1?
а теперь +1 стало
When will the score distribution be announced? I believe it will be before the contest starts.
It's dynamic
Oh, thank you very much.
I wanted to participate but i couldn't because of the unusual timing, the registration closed two minutes before I checked :(
I've got nothing against dynamic scoring, but damn those penalties on 250pt problem are harsh..
what are system tests ?
The test cases that your program executes on after the coding phase is over.
Oh God! Save me from the wrath of system tests...
Any suggestions on how to solve Div. 2 D?
Changing of description of Div1A was too critical
But it was kinda obvious from the start because you can't put A into B if B is in something else in real life too.
By the same argument, it was obvious that you can't take A out of B if B is in something else, but this was explicitly stated in BOLD LETTERS in the statement for some reason.
Well, you're right. I didn't notice that.
My personal sorry for that place. Using the bold letters here and hoping for a participant's common sence was a huge mistake that led to a such situation that even Russian-speaking contests were confused how the matryoshkas work.
https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox
This is interesting! Aside from that, I know that you know what I meant by saying obvious. This is definitely not something that come to mind first (at least for me).
If I know how Matryoshka works, it could be obvious. Unfortunately, I wasn't. In point of view of you, I can understand what you mean saying 'obvious'.
For some reason, I thought it's like different size of cups or buckets, so I was really confused with the restriction. Now that I googled it, it's actually really obvious.
Don't think it's obvious.
When I was thinking about matryoshkas I didn't imagine closed ones, only bottom halves of them. If you're messing around with these toys in real life that way, you definitely can put A into B even if B is already in C, but it is kinda hard to pry out A from B if B is already in C. Pretty consistent with the first version of the problem, isn't?
Допустил мелкую ошибку в A из-за условия как будто на китайском языке и переслал задачу
@
Получил штраф как будто отправил ее через час
Участвуешь в раунде с динамическим подсчетом очков
@
Первые две задачи всегда 250 и 500
После таких задач понимаешь, что контесты на математику — просто манна небесная
The Codeforces system is so fair! I tried submitting E at 01:59 and I got no response from the server!
D: I submitted mine at 1:59:40, nearly broke my shoulder while running back to my laptop when I realized what a stupid mistake I made.
"nearly broke my shoulder while running back to my laptop" LOL
All that for WA 54 =(
Any suggestions on how to solve Div2 D / Div1 B?
EDIT: I sorted the bridges in ascending order. I did the same with distance between each adjacent island, keeping track of the minimum and maximum length allowed.
I think this will be the approach though i got runtime error while submitting
First store the max and min length required between each island . Sort according to min length . Start in reverse order that is take largest min length first . Find a suitable bridge using lower_bound .
Ah, ok. I simply iterated from the beginning of both arrays. If the length of the current bridge was not in between the current min and max, then I moved on to the next available bridge.
This looks like TLE, accorting to the 10^5 bounds.
I apologize. I didn't finish elaborating.
In my code, once I found a valid match, I would start looking for the next match considering only the bridges that came after the current one.
However, this idea fails with the test case given by Bluespeck.
My approach is somewhat different. I store all bridges in a set, because you can use a bridge only once, so with the set, you can easily erase the bridge from the set. I sorted all max (r_(i+1) — l_i) and min (l_(i + 1) — r_i) lengths by the maximum length. Then you try to fit the smallest bridge in the gap. If there is no bridge, or your lower_bound gives a bigger bridge, it's not possible.
I wonder if this is correct. You will find a "suitable" bridge — I assume the shortest bridge that is greater or equal than current min. How can you know that you shouldn't take a greater because it is too large to cover other islands?
I have a question. IF the problem is worth 250 points and you make 5 wrong submissions of it, at the end of the round, will you get negative score or still 30% of that problem's value (or whatever the minimum point value for the problem is)?
you get at least 30% of the problem points which is equal to 75 ,so if your penalties (time + wrong submissions) make the problem less than 75 you will take 75 points
Thanks. Howevr I think that wrong submission penalty should be dynamic. Especially with a dynamic scoring.
I thought very hard but couldn't find a way to solve div 2 D . How to solve it?
What's wrong with the Div2. D greedy solution? Sorting bridges and sorting island pairs (with their maximum value and minimum possible value) + binary search (some kind of lower_bound in bridges).
I had something similar, but there will be cases where this fails.
Here's my code. It may be too complex. It didn't pass the 6'th test. http://ideone.com/kFJqP5
It's like you sort the islands pairs looking at minimum possible bridge and then at maximum possible bridge it fits. Then, for each pair you search in the sorted bridges array for the shortest possible bridge.
what if the min/max pairs are like these: 2 6 2 9 4 5 and bridges are these: 4 6 9
Greedy solution is the right one, something is wrong with your "greediness".
Explain your greedy.
Not sure... I took a greedy solution too and got stuck on pretest 10.
Well, the thing is that you put the next bridge in the interval that isn't already used and ends first.
Could you explain your solution? I checked your profile and it says you didn't submit for that question.
the same here, this is my code
i think binary search don't help in this case, i pass pretests with set in which i store bridges lengths(and you can also do lower_bound in set in log time)
try it: 3 2 1 3 4 5 7 7 3 4
bridges must not intersect right ??
Seems there is no such limit
Yes 2 1, if I sort islands in ascending order and in other case I get a "No"
what is the answer for this case ??
I got:
Yes 2 1Yes.But in the code given by CrazzyBeer I get a "No"
Here is my approach , for each GAP , find the min and max value it can take. Let it be ai and bi. Now sort the GAPS with respect to the DIFFERENCE (bi-ai) , so lowest difference gets first. Now , sort the bridges too with smallest first.
Now , iterate over the GAPS , try to match it with the smallest bridge.
For the Example , the (min,max) for the gaps are (3,7) ,(1,3) and (2,5) . After sorting we get (1,3) ,(2,5) and (3,7) . Now , we first put smallest bridge 3 to (1,3) , then next one 4 to (2,5) and the third one 5 to (3,7). But I am stuck at case 10. 11805605
That one failed test 1? I think you mean http://mirror.codeforces.com/contest/556/submission/11805830
I also got stuck on test 10.
I stuck at test case 10 with this approach too. It would really appreciated if someone smarter guy or girl could give a short example, why this strategy is bad :-)
11805791
Consider two gaps, [1,3] (i.e. 3 is max, 1 is min value it can take) and [3,4].
You have two bridges of length 3 and 4.
The greedy sol'n above results in using the smaller bridge of length 3 for the second gap, and leaves no bridge left for the first gap, when you could have satisfied both gaps.
The difference in ai and bi is not a good metric; having smaller range of values doesn't imply it should be satisfied first.
Не делайте, пожалуйста, больше задачки про матрёшек! :(
Или пишите очень формально, потому что разобраться, что от меня хотят в условии, было просто невозможно
Матрешки это кадр. До оповещения не где в условие не было сказано, что вложенные матрешки в друг-друга нельзя вставлять
Я даже успел получить ВА6, потом после оповещания здал
Не ты один.
Как решать матрешки?
По сути тривиальная задача — находим группу, которая начинается с единицы, смотрим сколько за ней следует возрастающих чисел (типа 1 2 3 4 5). Этот кусок мы не будем разбирать. Оставшиеся в этой группе разбираем и собираем (т.е. 2 * (len — found_len))
Все остальное разбираем полностью и собираем полностью, это даст еще 2 * len — 1 секунд.
The statement for Div1.A/Div2.C can be more clear.
I think submission penalties for Div1 A should be cancelled for people who got WA on pretest 6 prior to the clarification.
Full disclosure: I am one of those people
not only submission penalties , extra time penalty because of resubmit should be removed too.
What is pretest 6 on Div1 A/ Div2 C? I did not see the clarification because I started at min 40.
I've read Div1.A task. Thought that its too easy for Div1. Read again. And again — trying to find something tricky. Spent 10 mins, surrender on that. Coded this simple solution for simple task and it passed pretests o_O.
I misread the statement of Div1-A twice and lost nearly 1 hour on that...
I lost a lotta time on that too... Maybe could've figured out the bug in my DIV1-B if they had a clearer statement from the start! :(
For me today was the day for WA on pretest 6 (8 WA on 6th pretest ) . Any tricky case for div1 B ?
3 2
1 2
3 3
5 5
1 2
Maybe something like this.This case hacked my friend's solution :)
I found out that my Div1D solution was right before AC, but I made a silly mistake :(
So, I hope lot's of TL in Div1D! kekekekeke
Back to div2.. see you guys ^_^
Huh, me too probably, only solved A :)
high five ;) :D
I'd rather say low five lol :D
Wait, wait, wait for me guys!
Don't worry, I won't leave you alone <3
it's not a big deal, we will have round #311 in 3 days, and we will all be back guys! ;)
...and I like blue color more than purple anyway.
yeah, I agree. :D that would be good if this color were removed and replaced by some other
Same here :p !! If only the first problem's clarification was made earlier!!! Well, who knows now? I will just try to improve myself and come back! :D
The contest was great !!!
Problem B div 2 is O(n^2) ?????
My solution have O(2*N)
can you explain?
can you explain your approach?
Just check for index 0 that how many steps counter clockwise you need to rotate to make its value 0. perform those number of steps in every other array index and check at last if it matches then "Yes" else "No". Complexity O(n).
No, my solution works for O(n)
You check if it's strictly ordered (like 0,1,2,3,4,5..n-1). If not — iterate through the array and do all the changes. I have done that exactly 2000 times.
O(n)
Great !
11790948 O (N log N) can be O(N)
My solution also run approximately O(N).
At first I calculate how many time I need to push the button, then I cheek for all i (in range).
Can somebody please explain why this solution gets TLE, it's linear — http://mirror.codeforces.com/contest/555/submission/11791988.
I tried scanf/printf and I wrote it in C too but the outcome was the same. Then I deleted everything and wrote it again and it passed but why it didn't pass at the beginning?
How did this pass 14 pretests?
lol thanks... I looked at the code more than 10 times and didn't notice that FACEPALM
По-моему, в условии задачи Div1 A остался ещё один косяк:
Отсюда можно сделать вывод, что даже если изначально цепочка была одна, то преступник всё-равно вначале её разобрал, а потом собрал обратно. Только из примера можно понять, что это не так...
I am going to learn SET
Я не знаю, как работают появляющиеся оповещения, но почему-то то и дело они не появляются, или, наоборот, появляются снова и снова после закрытия. Хотелось бы иметь какой-то элемент на странице, который бы бросался в глаза, если есть непрочитанные оповещения, и не убирался бы до того, как пользователь откроет вкладку "задачи".
Div2A: Time limit exceeded on pretest 12 Wasn't expecting time limit errors on A task... anyone else hit by that?
Me but i resolved it by another way and get pretest passed
Same thing, but still surprised to have an TLE on O(n^2) solution for n<10^5
Scoring system is dynamic. But points deduction is absolute(-50) .. and when the score keeps decreasing, -100 pushes the score like hundreds of places behind. Please take a look Mike
It will be the same as if the task have static 250, no? If so, nothing changed.
It kind of discourages hacking and not much value for speed is given either. Difference of +100 initally due to early submission time is now like +10 or +20. But 2 faults in hacking gives -100 difference direct.
In my case, I solved problem A in 30 mins, which has 171 points (after conversion to 250). I missed 2 hacks , which reduces score to 71 points and puts me at the fag end of the leaderboard
Imo, its pretty fair. You should hack only if sure it succeed.
Hacking is my mistake, okay. But still, if 2 hacks make my score less than someone whose submission time is ages(people who submitted near end have higher points) after me, I feel there is an imbalance somewhere.
Well you know, its balanced with task complexity — if you try to hack on e.g. task E it won't be the same.
Also If you succeed these two hacks you get more scores than some ppl who solved A+B. Is it fair from your point? Its the opposite side of this hacking thing. Just not your one this time :)
After this round, I think learning Russian is more important than English .
Which problem makes you think this way?
Contest time on early night truly affects my performance (at least for me)
i mean affects in positive by the way
Спасибо авторам за интересный раунд.
Somebody explain me problem C in simple langugage
Problem statement or solution?
problem statement . what exactly do we have to do. I am having really hard time with words like contained and nested .
just imagine the dolls and how can you remove one, or put a doll inside another.
first, you need a minimum of
k-1seconds to reassemble the chain from initial configuration.this is clear with a case like this:
4 4 1 1 1 2 1 3 1 4
here you only need to put 1->2, 2->3, 3->4
then you need to test all chains, if you find a chain of size 'S' and has elements '1, 2, 3, 4, .. ,S'
then this chain is consistent and there is no need to reassemble it.
other wise you will need to disassemble all elements from the point of inconsistency.
e.g.: a chain with: 1, 2, 4, 5
you need to extract element 2 by removing 5 then 4
hope this help's
Can 2 chains be attached together ? suppose 1->2 and other 3->4 can these 2 be combined in a single step?
No, read the correction statement you have break 3,4 and then combine 1->2,3,4
ok! thank you
Теперь ждем обновления рейтинга.... долго-долго ждем....
Good time! Wish more contests like this.
for(auto& v: adj[u]) if(v!=p)(WA 51) intofor(auto& v: adj2[u]) if(v!=p)(AC)Copy paste why...
how can adj[u] changes to adj2[u] if copy paste?
Yeah, I copy pasted two dfses, but I only changed one instead of both lists after I copy pasted. I was afraid I was going to run out of time if I didn't copy paste, but looks like I should've taken the extra 5 seconds to check it over.
For reference:
WA: 11804870
AC: 11805918
for(auto it:M)WAfor(auto &it:M)AC:)
I ended up debugging my B during the contest. Found bug after the contest.
Bug : Have to do sort(diff, diff + m) rather than sort(diff, diff + n). :'(
please god don't let them take as long as the system test to publish the editorial
Behold the bug in thy prayer! Repeat after me and be wise:
Please gcd let not my integers overflow today.
You have to normalize the coordonates on C div1 because QlogQ gets AC but QlogN doesn't, very very smart.
I've got AC with O(Qlog2Q) in upsolving. So I think O(QlogN) can pass.
Div 1 B.I saw people using similar approach like mine,and solved this problem using set.But I've time limit,can anyone offer optimizations or tell me the reason why my solution fails while other's don't? code
The contest ended 1.5 hour ago. He solved all the problems 0.5 hour before the end.
He visited 3 hours ago.
Am I the only one confused??
"Last visit" doesn't mean he has beel left this site 3 hours ago, this is mean he last time entered site 3 hours ago.
He just solved all problems and left.
Oh, I see... too many gods coding here...
probably it's the time when the person last logged in.
Yes, it seems like.
Nein. You're wrong :P
Nein, no one named 'wrong' here.
lol
That feature does not work at all :) I told MikeMirzayanov about it long time ago, but I think they have other things to do :)
Sometimes it shows time from moment when you entered site, not when you left it; sometimes if you entered for a short period of time only — it does not update at all. Sometimes value randomly updates to older — you see "3 hours ago" there, press f5 and it becomes "9 hours ago".
Personally I like the last one. The next weekend will be earlier, right?
Hi, Java fans.
Trying to solve div1B using TreeSet I found out that I can't use the structure if there are duplicate keys.
Here you can find why.
"For example, if one adds two keys a and b such that (!a.equals(b) && a.compareTo(b) == 0) to a sorted set that does not use an explicit comparator, the second add operation returns false (and the size of the sorted set does not increase) because a and b are equivalent from the sorted set's perspective".
How to solve the problem then? Well, one could use TreeMap<Long, LinkedSet> instead.
http://mirror.codeforces.com/contest/555/submission/11800486
http://mirror.codeforces.com/contest/555/submission/11805972
Didn't like the MemoryLimitExceeded in Problem Div1C. It was too easy to get MLE if you focused in solving it on time. Good problems but either memory limit should be higher or N limited to 100,000 instead of 200,000 :(
Я после объявления окончательных результатов был 783-м, но сейчас я уже поднялся до 768-го места. Как это возможно? Тут проходит еще проверка на читеров или что-то еще?
If the input would have been sorted in Div. 1 D I would have 100% solved for the first time. With unsorted input I was late for 2 minutes.
I really wonder what 'technical reasons' are in Codeforces Round 307 (Div. 2), Codeforces Round 307 (Div. 2), Codeforces Round 305 (Div. 1), and others.
Finally.
P.S. I changed my avatar to red. One should always have a target. Hope I become red, as my avatar this year.
Contest : 310
Rank : 310 :)
Ramadan has brought you great gift sir :)
Hi all,
In Div 2 C/Div 1 A, I have submitted this solution which got WA: Solution1 And after the contest I checked the test case on which it was failing(Test case 8) and tried it on my ubuntu machine it gave me 33(which is the correct answer but it gave Wrong Answer on Codeforces). Then I submitted another solution: CorrectSolution it got accepted. In this I just have cleared the boolean array "khali". Can please anybody tell me why my same solution gave 33 on ubuntu machine and 27 on Codeforces on test case 8? This is the test case->
the same here in test case 2 !!!
i have compiled it at visual studio , jetbrains , ideaone . correct answer except at codeforces
Try clearing some array that you have initialized. I am not getting that why linux machine result(having the same gcc compiler) differs from codeforces compiler result?
i am not in linux , i am on windows still WA
From Stack Overflow- " There is no automatic initialization in C++. Your new bool will be "initialized" to whatever was in memory at that moment, which is more likely to be true (since any non-zero value is true), but there is no guarantee either way. You might get lucky and use a compiler that plays nice with you and will always assign a false value to a new bool, but that would be compiler dependent and not based on any language standard. You should always initialize your variables."
Same happened with me:P
What a luck..!! That all of my n sized boolean array took 0 value(false value) by default even though I didn't initialized it and I wasted around 45 minutes + 2 Wrong submissions..
Можно ли узнать, почему мои попытки были проигнорированы?
ПОТОМУ ЧТО СИДИШЬ ДОМА ЗА КУДАХШТРУДЕЛЕМ КАК СЫЧ, ВЫШЕЛ БЫ ХОТЬ НА УЛИЦУ ПРОГУЛЯТЬСЯ, СЕРВЕР УЖЕ ПЕРЕГРЕЛСЯ!
Got screwed over by the MinGW C++ compiler:
It turns out this code gives different results for GCC and MinGW. :( Shouldn't have coded that in the first place, but I was sleepy so I didn't notice it.
Instead of n=n--; n-- would have sufficed. It actually decrements the content of the register in which n is stored, so we would have our desired result. The line you wrote performs unexpectedly in different situations
Разбора не будет?
Can somebody tell me why my code for Div1B http://mirror.codeforces.com/contest/555/submission/11803847 TLEs ?
I sort every pair of islands by their maximum distance ascendingly (Sorting the indices actually) and then I insert the bridges in a set and looper over the pair of islands, and find the minimum possible bridge that fits then erase it it found. Complexity should be O(N lgN)
Know your libraries.
std::lower_boundis O(n) for a set, not O(log n).You probably wanted
b.lower_bound()instead.Thanks, Now it's accepted, I definitely have to take note of this!
lower_bound(set.begin(), set.end(), x)works inO(N).set.lower_bound(x)works inO(logN)The Tutorial link in problems of this round opens Codeforces Round 309's Editorial.Is Round 310's Editorial published?
Nope, it's not published yet.
Don't you think posting 1 to 5 ranked coders is motivating? :D
When The editorial of round 310 will be available ?
Editorial: http://mirror.codeforces.com/blog/entry/18919
Can anybody help me with the logic of Div 2 problem D? Plz elaborate in detail.
I don't think the editorial is coming up any time soon, so here goes. Given that we have to connect two islands with co-ordinates (a,b) (c,d) with some bridge of length l such that l<=(d-a) and l>=(c-b), since all islands lie on a straight line.
Now we are going to implement a greedy solution, ie we sort all islands by their smaller distance(c-b) and try to assign the smallest bridge possible to the bridge.
This solution will however fail in cases where although the smaller distance between the islands (c-b) is the minimum among all islands, but the larger distance is greater than the rest of the islands. You can think of it in terms of flexibility of an island defined as the range of accepting lengths of bridges from [c-b,d-a].
Consider 3 islands as :
1 5 (I1)
6 7 (I2)
8 9 (I3)
Bridges are of length : 3,5
Our initial greedy algorithm will assign bridge of length 3 to connect I1 and I2 and then would be unable to connect I2 and I3, but clearly switching the bridges gives us a solution.
Therefore, we sort all islands by their larger distance(d-a) and then try to assign a bridge to it that is as close as possible to (c-b), ie we give highest priority to island with lowest flexibility and try to assign a bridge to it that just connects the island.
code
Can anybody help me with my runtime error for Div.2 D at test case 11 (11810093). Every test case passed until the big one with 100000 islands and bridges.
This time sorry_dreamoon-(qwerty787788) has beaten Haghani :)
looks like the editorial is going to take forever !!
please any body, what is wrong with my approach for problem Div2 D.
Firstly sorting w.r.t minimum possible length of bridge is wrong. Simple test case: 3 2 1 4 5 6 8 9 3 5
wtf!! debug your code yourself.
Nice contest!
in general,my friend and I have a very tired contest......As I said -> DeaphetS he is the most hansome boy in our school .
Can someone please explain me why my all 3 submitted solutions were skipped in yesterday's contest 11804905 ,11800557 and 11788258 ?
Solutions usually get skipped when they are found to be similar to someone's code. Did you ideone?
I didn't find the tutorial for this contest, somebody give me the link .
Here is this: http://mirror.codeforces.com/blog/entry/18919
this link redirects to editorials of the previous round (309).*edit* now the link works perfectly fine .thanks a lot.
Что такое "Попытка игнорирована"?
Ты спалился)
Div 1D is very intuitive and easy! Comparatively div2D was tricky imo.
It maybe your illusion......
that's what I thought, but after looking at someone's accepted code, it was the same as my logic. complexity= n*logn*logl in worst case.
Finaly solve problem Div.2 D (11818401): Let represent an island as pair ii = (li, ri). You have to sort all island pairs (ii, ii + 1) after their maximum distance
in ascending order. The bridges can be save in a set. Than we start at the beginning of the sorted island pairs and perform for the minimum distance dmini = li + 1 - ri the operation lower_bound(dmini) on the set. We have to check if the resulting bridge fulfill the requirements and erase the bridge from set otherwise print "No" and exit. We repeat the procedure for each island pair. Note that we have to put a little work on the datastructure since the output requires the indicies of the bridges.
Can anyone share the link to the editorial ,I really didn't find it, in fact in contest material there is a link to the wrong editorial (codeforces round 309) thanks
where can I find the editorial ? (the contest material is linked to the wrong page)
http://mirror.codeforces.com/blog/entry/18919
http://mirror.codeforces.com/blog/entry/18923
Official editorial is almost ready.
in div2C, shouldn't the final formula be 2n - k - 2l + 1
Fixed
thanks !!
*Deleted
Can anyone explain Haghani's solution of problem DIV 2E/1C ? Its so simple and elegant but i don't get how it works.
This Problem and Case of Matryoshkas (Div2) are exactly same problems.
I'm sorry for necroposting and pedantry, but the first picture in the note for problem D (Div. 1) isn't consistent with the sample test -- the coordinates there are 0, 5, 8, while in the sample test they are 0, 3, 5. It confused me (while upsolving), and can confuse someone else. Supposing that the picture was made in MetaPost, it's a matter of several minutes for the authors to correct this.
Yeah, thank you for reminding of that. Actually, only coordinates are wrong while the overall illustration is kinda correct. But you're right and it should've been corrected. Your supposition is wrong and it might take some time to fix it.