Привет, Codeforces!
30 июня 2015 года в 18:00 MSK состоится очередной раунд Codeforces #311 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Обратите внимание на необычное время начала раунда!
Это мой четвертый Codeforces раунд, желаю всем быстрых и главное полных решений!
Хотелось бы сказать большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon и за помощь в придумывании задач, а также моим друзьям Илье Лось (IlyaLos) и Данилу Сагунову (danilka.pro) за прорешивание задач и вычитывание условий.
Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.
UPD Разбалловка задач стандартная 500-1000-1500-2000-2500. Всем удачи!
UPD2 Соревнование завершено! Всем спасибо!
UPD3 здесь вы можете найти разбор задач.
We like your problems a lot, hoping for some more nice problems
Hoping that the problems' difficulty will be contantly increasing(like they were in your last round #297) not something like first two problems are extremely easy and the third a lot harder.
Why this contest starts in the unusual time???
Внезапно задумался... Помнится, недавно был топик, где раскрывали истории никнеймов таргетов и не только. А вот о Delinur никто и не вспомнил. А ведь интересно же.
У нее просто рейтинг низкий, никто не обращает внимания на новичков((( ей нужно старатся и больше решать всяких задач по програмированию...
Толсто
...сказал человек с высоким рейтингом.
Will it be another dynamic scoring contest? I guess so.
Your guess was wrong.
Just one request , please make the problem statements clear and don't name the characters something like "**matryoshka**" . Its very annoying when you are not sure of the problem statement and on top of that the characters have such unpronounceable names.
you can ignore the character's name
Surely , but you will agree that it is annoying .
yes but sometimes they use some weird words or names to confuse you and actually they're not part of the problem and u should focus on the main idea .
Its your point of view , personally i believe that a good problem should give the participant a hard time in figuring out the solution not in figuring out what the problem actually wants from us.
i have taken part in 5 regional contests and 6 or more other onsite contests in the past 3 years and I've seen a lot of problems which had weird names or even they explain something that just a story for fun and they're not part of main problem so after u see them you just ignore them . you know , they're just part of the contest not important.
The story is not irrelevant as it gives us a real life problem. But one should keep it in mind to not let the story make the problem confusing. People has to read all of the statement and a big story with complicated characters and stuffs can mess up a contestant's head.
I don't agree. As a programmer you must be able to convert "real" problem (with legend, weird names and everything) to math/coding one. That's just IMHO, but as for me — legend is a good part of problem.
Matryoshka is a real thing... I think all the "weird" names are real, maybe they are just not common in your country.
Yout last round was awesome. Especially the problem Round 297 B with a weak pretests.
Yeah !
return of the unrated's
Hope to see harder and of course more balanced problems than your last contests :D
who the hell are you? :|
what did i do to you?
what made you do such a retarded thing?
guys in our language this guys handle name is a swear and his name is "arash mahmoodian"
strange thing though what a small universe it is when you can find someone with the same name and same organization
just ignore him :)
Very bad ( Why not simply sorry_silver_soul .
Actually, in Persian swear means more like "قسم". His name is a curse, a bad word (sexually). It mean f**k you in the ass.
Actually, one of the meanings of swear is curse :)
OK, guy. I'll try to do it!
nice at least you changed your name
don't make shitty account like this anymore
of course this was just a suggestion i don't give a damn or two about you
Surely div1 user
Привет учасники! Удачи сегодня на саревнованиях! Хочу рейтинг выше.
Participants Hello! Good luck today sarevnovaniyah! I want rating above. Sorry for bad english
I tebya don't Ponimat
ПАЦАНЫ и ДЕВЧАТА))), зайдите в тему пожалуста на минуту всего!!!! http://codeforces.net/blog/entry/18977
ВЫРУЧАЙТЕ, ахахаха!!)))) спасибо!!))))))))))
Хоть бы ты был троллем, а то я даже прям не знаю.
i am newly in this website,can anyone tell me how to practice before contest??
and don't forget to check your username in registrants list just before the contest , good luck !
nowdays i kind of doubt every unrated user
Me too, except for sorry_dreamoon first appearance.
Please try to minimize the description of problems statements. Although your problems are interesting, they are too long for non native English speakers
Wish u happy coding;)
I have a problem, I can't submit my solution today.
it's getting "Network error" when after I submit my solution.
any advice?
thanks.
Try to remove cache of your browser then try again
hello to all. i think for muslims that they're rozeh* , they cannot take contest well!! please delay the contest for 2 hours.
rozeh: it means that you don't eat and drink from morning(sunrise) to night(sunset). it's a necessary for muslims!
thanks to all.
hello to all. i think for muslims that they're rozeh* , they cannot take contest well!! please delay the contest for 2 hours.
rozeh: it means that you don't eat and drink from morning(sunrise) to night(sunset). it's a necessary for muslims!
thanks to all.
Not all muslims live in your timezone. This kind of generalization is stupid. I'm a muslim, and this time is better for me.
if the time delays it doesn't make any problem for you but that solve a problem for me!
You're wrong. It makes problem for me. My iftar gets in the middle of the contest. But I never whined like you because I know that this issue is relevant for small minority. Current time change benefits every muslim user from Turkey. Of course, you can say that number of users from Iran is greater than Turkey, but if we think that way, number of muslim users is less than others. They can't arrange a round according to minority. It's impossible to make everyone happy. If time is not suitable for you, you can always virtually participate.
No. if it delays for just 1:15 hour it doesn't make any problem for not muslims users!! but it solve a problem for most of the muslims!
You said it doesn't make any problem for you, and I simply explained why it makes a problem for me. And now you're saying "No. if it delays for just 1:15 hour it doesn't make any problem for not muslims users!!" I kindly want to remind you that I'm a muslim, and I already stated that in my first post. I already answered why it's a bad idea to want them to change time, that's why I'm gonna stop answering. I think you reply even before reading my answer.
Btw, how do you know that it doesn't make any difference for all other users? Do you know all of them? Do you know their schedules or their plans? Everybody has their problems, but it's just you who complains.
what are you saying?
i reply that comment for this part of you comment!
" Of course, you can say that number of users from Iran is greater than Turkey, but if we think that way, number of muslim users is less than others. They can't arrange a round according to minority" ;)
there are more that 200 million muslims in my time zone or near to me. but because you are near to europe musllims are not a lot!. note that all of Turkiye people are not muslim! i think understanding this that i spoke about all of muslims is more stupid!! i spoke about most of muslims!
You didn't say most of muslims. You said muslims. And that statement implies what I said.
i'm sorry because the argue but it's important never comment doesn't make any sense!
if my comment get 1000 likes there would n't be any time changing!
thank for thinking about my comments!
The last codeforces round was the first time I tried to hack people , but the problem was that I couldn't
highlight the code ( to copy-paste it in my computer) is this made by purpose ?
Congrats unrated ones! One of you will probably win this thing (
usual time or unusual time This is a Question!!!
previous contests held in 19:30 MSK (21:00 Tehran)
Standard scoring!! Awesome.
Have a nice contest,bless all!
May the God fold comments over 5 indent levels...
good luck and have fun guys :D
Well, I read some comments... and I was like WTF? Whats goin on here... ?? M never ever gonna read comments on CF #Round Invitation. (Period)
Ooops, it started 1.5 hours early than usual :)
Get Coder's calendar plugin maybe ? :D
I feel as if the author mistook the round as Div 1. Just saying
How to solve problem C?
I'm not sure if my approach is totally correct. My algorithm is somehow greedy, I try to make each possible leg length the maximum one. In order to do this, you need to remove all the legs with a greater length than the current one. Then, for this new configuration valid, you could only have 2 times the amount of the legs of the current length — 1, to satisfy the problem requirements. So greedily, you have to keep in this new configuration the legs that cost the most to be removed and are shorter than the current one and take out the remaining ones (pay for them to be removed).
First you choose your max value , after that you can see the next observations :
Let F = frecuency of the fixed max value then you can choose at most F — 1 of this lesser values , you choose the better F — 1.
If you sort like pairs , you can build a simple algorithm with an heap
Implementation: Link
Did anyone else write binary search for B? I used 500 iterations and I wonder if it will pass...
I tried using Binary Search too. I could not get it to pass correctly though :) will upsolve.
I ended up getting AC with 500 iterations :D
link to solution?
http://codeforces.net/contest/557/submission/11858843
*fixed link
Look here: http://codeforces.net/contest/557/submission/11868065
I was stuck counting quadrilaterals in D. Can anyone give me a hint?
One word hint: Bipartiteness
'□' Love it, Thanks!!
think in bicoloring
What was the solution for Div 2 C? I couldn't figure it out
I think it was greedy: search for all lengths L what is the cost to produce a stable table with L as the max length. Fixed L, you should remove all the legs with length>L; if now is stable compute the cost, otherwise start removing legs with length<L with less cost until you have a stable table. I think that can be implemented with a priority_queue.
My solution is as follows: Let's say we want to 'select' legs. You have to maximize the sum of energy of selected legs. For every length l, consider it is the maximum. We would have selected a certain amount of legs with length l, let's say x. Then we can select (x-1) legs (at most) that are shorter than l. Those (x-1) legs should be maximum in energy.
Because the d limit is quite small, you can look from 200 to 1, select no more than x legs that are shorter than l. So you just have to sort the legs by length and count.
There is only one div in this occation. So the specification is not needed. The primary reason I post here is so that I can read when someone explains how to solve the problem though.
Submitted a previous round's A problem by accident.. sigh. On the bright side, solutions are already up, wow!
Same thing happened to me... I was very surprised when the judge told me my solution had exceeded the memory limit.
Good contest with good scoring distribution , nice and understandable problems .
It is my first time to receive a message "thanks for hack" in a round. It feels very good!
@Cyber Thank you, too.
Thanks for an interesting problemset. But it would be even more interesting in case there were more possibilities for challenges :)
Upd. Oh, I was wrong, in fact there were quite a lot of solutions to hack (especially B's with wrong output format) :)
I've been training a lot and level C problems are starting to look as hard as Level B problems did for me about 2 months ago. Progress feels great! Thanks for the problems!
Really challenging round, thanks ;)
а на чем можно было взломать А?
По-моему, как и все задачи, только на криворукости или невнимательности конкретного участника.
UPD: А нет, я не прав, B и C попадали на тестах у большого числа участников.
Я взломал именно неправильное решение по В на тесте
3 18
1 1 1 1 1 5
ребята работали с max и min...
Да там у парня опечатка была — он жадно пытался увеличить количество дипломов первой степени до максимального количества дипломов второй степени.
for B isn't answer min(w , 3.0*n*min(arr[0],arr[n]/2.0)) on sorted array ? Or Is binary search the only way to go ?
Answered my own question, it is, mine got AC.
To all
coutlovers: Wrong answer is in coming! :(I forgot to use "setprecision" on B using cout. Nice!!!!
I am feeling very very sad. Just used cout instead of scanf and got wa on test 32 :(
very nice contest (specially problem D ) but I hate working with doubles :\
Anyone else fail B because of precision error?
Of course... me, you and a couple hundreds more.. used 1e-9 for binary search and printed exactly 6 digits.. got acc after round only after using 1e-11 and printed 8digits
but 1e-6 error should be accepted, isn't it?
If you used cout, your error on test 32 is 4.7*(1e-6), which is greater than 1e-6. Hence, the solution failed.
First i used this :
cout<<ans; (ans is of type long double) I got wrong answer.
Then i changed it to :
printf("%lf",(double)ans); Got AC.
Double and long double have precision upto 6 digits.So, printf gave AC. But , what is the problem with cout?
You have to use
cout << fixed << setprecision(6) << ans. See http://www.cplusplus.com/reference/iomanip/setprecision/EDIT: I think it's setprecision(6), in the actual contest I used setprecision(9) to be safe, and it got AC.
You can also use the following line before printing the answer using cout.
cout.precision(10); cout<<ans<<endl;
AC submission : http://codeforces.net/contest/557/submission/11854647
wrong answer on test 32 used setprecision got it accepted :(
can anyone please explain why using %0.9lf with printf gives TLE on pretext 8 while %0.7lf passes in 1/10th time.(second last line) passed solution with %0.7lf — 11862093. TLED solution with %0.9lf — 11861535
use printf instead of cout for better precision or use setprecision with cout
king_of_hackers? Probably.
king_of_memes? Yeah ;)
I am not able to figure out what could be wrong with my code for problem B. Could someone help me track the error in this submission?11859368
Add cout.precision(10);
Here is your AC code: 11868422
Hi, thanks for your prompt reply! Could you provide a bit insight as to why this was required, and why not using this gave me a wrong answer?
I got the reason. Cout apparently has lower precision by default. Didn't realize this during the contest. Thanks!
rather going for binary search apply little math and answer is just 2 line code
Have a look again man. I used it at first, but then removed it. The function is still there, but it is not being called anywhere.
Have a look at my submission http://codeforces.net/contest/557/submission/11867954
I think you did not want to look at the submission and go through the logic before commenting this.
Just to let you know, I have figured out the error, thanks to minimario. The error was not in the logic, but in the precision. I did not know that the precision of cout by default was less than 10, and so, didn't realize that it should be explicitly changed.
Giving a link to your own submission is the least helpful way when someone asks why his code doesn't work.
DIV2 ProbB — My solution came wrong just bcz I did not use set precision :( .If possible can anyone explain how set precision is helping in getting the problem accepted.
It is asked from the problem statement. It says that needs to be relative to 10^-6.
can anyone tell me why my submission getting TLE ..ON Nlog(N) time complexity in problem B my solution is #include<bits/stdc++.h> using namespace std; long double Ar[200005]; int main(){ long double n1,m,w,k,mn,mx,x; long long int n,i; cin>>n>>w; n1=n; for(i=0;i<(2*n);i++)cin>>Ar[i]; sort(Ar,Ar+(2*n)); mn=min(Ar[0],(Ar[n]/2)); x=w/(3*n1); x=min(x,mn); m=(3*n1*x); cout<<m; return 0; }
first of all,add your source in a pastebin,else none will read it like that. secondly,set precision. (cout.precision(10) for example)
Hi guys, can someone suggest where i might haved made a mistake in this submission http://codeforces.net/contest/557/submission/11868290 Thanks
Scanner is slow. It's better to parse the input, but you don't need to write it every time.
wrong answer 1st numbers differ — expected: '106798500.0000000', found: '106798000.0000000', error = '0.0000047'
Что? Это потому, что 47 — счастливое число из цифр 4 и 7?
Относительная погрешность.
Has anyone else notice that
ios_base::sync_with_stdio(0);cin.tie(0);is not working(almost) anymore in CF?I've seen cin,cout is slower in CF comparing to other judges. But this much? My B was a narrow escape.
using scanf
155 msusing cin
904 msIs this because of some recent changes in system or it was always like this and i never noticed?!
I had a similar problem, so I added
cout.tie(0);, and it runs a bit faster. But to my experience scanf/printf are much faster than cion/cout even after that.it's just iostream for double is very slow even after using ios_base::sync_with_stdio(0);cin.tie(0);.
see link : http://codeforces.net/blog/entry/5217
You are right. My code runs as expected after taking input as
intarray instead ofdouble. Thanks. Learned sth new :)I use only int and scanf is more than 50% faster: http://codeforces.net/contest/557/submission/11856815 http://codeforces.net/contest/557/submission/11871020
Any one can help to find out what is wrong with my program? I got a wrong answer a large input but I run the same input in my computer it is ok.
The problem seems to be overflow on something but I cannot find it out.
11854334
your ac solution , declare w as a double 11869049
Thanks very much! But I still don't get it why my version is wrong .... And I get another wrong answer with only declaring w as double
11869173
Ratings up
So I originally misread problem B, and missed the fact that all of the boys had to have the same amount, and all of the girls had to have the same amount in their cups. If we removed this restriction, what would be the solution to the problem then? Is it NP complete or is there some algo? Any insight would be appreciated.
Finally Division 1!!!
My solutions were skipped! Why!!!
This was because the exact solutions you submitted were already submitted by someone else. So either your luck is really bad(2 skipped problems), or you copied someone else's codes.
Not so bad luck! One of those solutions gave wrong answer....so whichever poor guy's solution matched is the unlucky one(probably, assuming he didn't change his code because the pretests were passed)
If someone's solution gets skipped, then this means their solutions matched before system testing as well. Why can't the system detect this and give skipped verdict instead of pretests passed? Even the biggest cheaters would tweak their copied codes a little so it doesn't get skipped. The only people who get affected are innocent (imo) because they had no idea their coding style is so obvious (
Do something about this Mike. On some other day, I'd be really sad if this happened.
I did not copy anyone's code. Next time I'll remember to set my ideone submissions to private.
getting tle on 2nd question for 8th test case .. can anyone please tell what should i change in my code to get accepted ..here is the solution link http://codeforces.net/contest/557/submission/11869859
improve i/o 11870141
add ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
could you also have a look at these solutions i just changed %.9lf to %.7lf in printf and got AC accepted with %0.7lf ----- 11862093 TLE with %0.9lf ----- 11861535 thanks.
use scanf instead of cin
11870249
thanks!
2nd problem is input intensive, so using cin stream slows down the code, and also std::vector is much slower than plain arrays, as vectors have to spend more time resizing...in such tasks you'll be better off using printf, scanf as well as bare boned data structures. u can also use ios_base::sync_with_stdio(false); in the beginning of your main function.
not bad, you just need to go faster :)
http://codeforces.net/contest/557/submission/11870535
Getting correct answer(2) on the first case on my computer but 0 on it on codeforces servers? This is the first time I'm submitting a solution in c++, so maybe I'm missing something.
Can someone, please, tell me what's wrong with my code for C? It gives the correct answer with all the small cases so I cannot debug it. At least some test case that won't pass with it.
I wrote a lot of comments to make it easy to understand: http://codeforces.net/contest/557/submission/11870567
The idea is basically the same as the author:
Thank you very much in advance!
I've used similar idea. But couldn't find bug in your code. See if this helps
Thank you. I cannot find a single case that doesn't work with my code. I'm running many random cases against Accepted codes without any luck :(
Finally, I found the problem with my code. It didn't have to do with the algorithm but with Java!
The problem was in the way that Java compares Integer objects:
Incorrect: if (legs[i].first != legs[i + 1].first) {
Correct: if (legs[i].first.intValue() != legs[i + 1].first.intValue())
Explanation: http://stackoverflow.com/a/1514919
AC code (almost the same): http://codeforces.net/contest/557/submission/11873179
Anyone? http://codeforces.net/blog/entry/18990
Did anyone get AC in B using binary search??
Me
That's my code.
Link
Then you are one of the lucky ones
Problems are really interesting but statements are quite hard to understand. I've fun solving them but I think it will be better if you make the statement simple (IMO).
Извените, но я все еще никак не могу понять почему в задачке "Артур и стол" в третьем тесте ответ 8 ? Заранее спасибо =))
Берём две ножки длины 2. Откручиваем две ножки длины 3 и одну длиной 1.
о, спасибо что ответили =) То, что нужно открутить две ножки длины 3 я поняла. А вот для чего откручиваем еще одну ножку длины 1. Если мы просто уберем две ножки длины 3. как раз из оставшихся 4-ех ножек остаются 2 ножки максимальной длины 2 . Вот чего я никак не могу опять =)))
Там есть требование "Стол с k ножками считается устойчивым, если ножек максимальной длины строго больше половины".