Очередной сезон крупнейшей российской олимпиады Russian Code Cup стартует в субботу. Впереди новые интересные и нетривиальные задания, бескомпромиссная борьба и самые крутые призы.
Но мы подготовили вам еще один сюрприз: 17 апреля у каждого из вас есть возможность оценить свои силы. В 19:30 по московскому времени на площадке http://codeforces.ru состоится тренировочный раунд олимпиады со свежей порцией задач от создателей RCC.
RCC 2014 Warmup – это тест, который даст возможность попробовать свои силы и понять, к чему готовиться в раундах чемпионата. А для «бывалых» участников это идеальная возможность потренироваться и разогреться перед первыми сражениями RCC 2014!
Автором большинства задач этого раунда является Aksenov239 — постоянный автор задач RCC. Конечно же ему помогали и другие члены жюри RCC-2014. Раунд пройдет как в div-1, так и в div-2, так что все найдут себе задачи по силам.
Ждем вас в четверг в 19:30 на площадке http://codeforces.ru
UPD: Итак, разбалловка раунда: Div1: 500-1000-1500-2500-2500, Div2: 500-1000-1500-2000-2500. Всем удачи!
Последняя ссылка на codeforces неверная из-за восклицательного знака.
Круто! А раунд будут рейтинговым?
Да
Это стандартный раунд codeforces или по правилам ACM?
Codeforces
will the round be rated?
Yes, it will be.
"Though Russian Code Cup is open only for those who speak Russian" will the problem be translated in English??... Can the one that can't speak Russian take part in it?
The Russian Code Cup itself is in Russian, it will not be translated.
RCC Warmup round will be like ordinary CodeForces round (just "sponsored" by Russian Code Cup), so it will have statements in both Russian and English. Sorry if there is any confusion.
OIC~ thanks for solve my confusion~
Я правильно понял, что это будет обычный CFR, только называться он будет по-другому?
Да.
Вопрос про сам RCC. Верно ли, что участники до 18 лет могут участвовать, но в финал пройдут 50 сильнейших участников отборочного раунда среди тех, которым исполнилось на самом деле исполнилось 18?
18 на момент регистрации. А так — да.
are the problem's difficulties as usual rounds?
Hard to say. No special attempts to make problems easier or harder were made, however you can never tell ;).
tnx for helping :)
...
на Codeforces будет только Warmup раунд. RCC будет на своем сайте
will the round be rated for every codeforces members or only for Russian participants??
i think for every one
I agree with you
dibil solidarity
hey dibil !!!
what does the dibil mean ?
Strange idea. This would probably only increase the amount of fake "Russian" accounts.
CF rounds are always rated for anyone in the division for which the round is.
This round will be like usual CodeForces round. If it will have statements in both languages, I think it will be rated for everyone.
Great start!
Good Luck everyone! Hope that the website wont be down again during the contest.
delay for ten minutes?
yea!
Good luck and Have fun~!
While we are at it, shouldn't it be "Codeforces is temporarily unavailable" instead of "Codeforces is temporary unavailable"?
Немного не в тему: с большим трудом нашла на сайте RCC информацию о точном времени раундов. Может быть, стоит поместить ее на более видное место?
Those hacks in B! I did a bitmask dp with complexity O(N * 2^M) as did many, I believe. Is there some very tricky case or is the time limit strict?
I think this is trick here: You won't need to ask more than 20 friends to help you.
Ah, this wasn't my mistake. I wasn't properly computing my new dp values. I fixed it now — 6396342 :D
I hacked 2 people who did not sort friends by the number of required monitors
I missed this trick , Learned a nice trick (i am almost a newbie :p)
Yeah right... Newbie(!) -_-
For Div1 problem B, it was very tricky that INF=1e18 isn't enough. I resubmitted because of this, and made 4 successful hacks.
i think you mean div 1 B not C . you can make INF = the worst Case better than certain value :)
I think the problems were harder than usual.
а как решалась A div 2?
на чем ломали?
Я не стал придумывать что-то особенное и сделал просто перебором количества раундов первого и второго типа. 6385830
Can't Div.2 Problem A give some explanation about sample tests?! Total inapprehension.
Yeah, I was confused with the problem in the beginning!
I agree, I'm totally confused with Div2 problem A and problem B description.
statement was horrible... :/
Не, ну это максимально подло: заводить в B маленькую константу inf, а в середине кода возводить ее в квадрат. -50 4 людям в комнате за полминуты
sorry, my mistake, yeputons find differ between tasks.
It's interesting how many people have seen this problem before.
I misread, please ignore.
Неужели так трудно было в B уточнить, можно ли покупать два элемента с одинаковыми масками? Добавить хотя бы один сэмпл, где это видно? Или не игнорировать мои вопросы, а нормально пояснить (мне, допустим, из клара так и не стало ясно, что именно имеется в виду)?
Между прочим, будет весьма неприятно, если Геральд координировал задачи в этот раз, так как задачу, практически идентичную А, я предлагал раньше, мы её заменили другой, и эту задачу я хотел оставить на потом.
Даже если можно, это невыгодно, разве нет?
Ой, я хотел сказать, элементы с пересекающимися масками.
Кто-то поток сдал в B div1?
Какой поток, к ней элементано сводится Weighted Set Cover Problem, она NP-трудна.
Problems were very interesting...!!! Thanks for this Round.
Can anybode tell me, how could it get TL?!
cout. Write ios_base::sync_with_stdio(0) or use printf.
I've solved over 100 problems using cout, but solutions work with such restrictions. And endl also hadn't create problems.
I used ios_base::sync_with_stdio(0) and still got TLE : http://mirror.codeforces.com/contest/418/submission/6387665
Too many arithmetics at each iteration :) I think — division costs so much.
Use this:
Also, on MSVC
ios_base::sync_with_stdio(false);doesn't actually do anything.(y) hmm... just changing endl to '\n' passes in 530 ms. Flushing problems — slows the output!
10^6 numbers : large output, same with me : should have used printf.
I think it's beaucase you use endl.
For Div1 A: Outputting 10^6 numbers using cout with ios_base::sync_with_stdio(0) caused TLE :/ (also there was no large output warning).
strange I have used cout and endl and my solution passed.
998 ms!!! also using '\n' in place of endl halves time because flushing happens only once.
Wow, so are time limit failures on problem A (div 1) something you were aiming for? While it's obviously good to remember that iostream is slow, you probably should have used different input bounds for that problem (or different time limit). There was enough room for hacking in that problem anyway, so TL-trick seems to be an overkill. Besides, in one of the previous D2 contests CF used to mention that "I/O size is too big for iostream, so don't use it".
Just my opinion (of a person that got burned on this).
Ya, CF gives large input/output warning in such scenarios : so I didn't bother using cout with ios_base::sync_with_stdio(0) (and got TLE!) which seems to be as fast as printf in many scenarios : it must be only 1.2-1.5 times slower than printf anyways.
Why no explanations to the sample cases? Some of the wording was more than a little confusing (not that I'm complaining with my hacks), and I suspect some people failed because of it.
Also Div2C/Div1A really should have the "large printing" warning — there's no point to having people who solved the problem TLE because printing is too computationally expensive. That makes it not a programming problem anymore but just semantics about syntax, which (at least in my opinion) does not a good problem make.
Also it seems like it is almost impossible to pass with Java — only one person managed it with Java 6 and not many more with later versions. Just a very bad problem.
So, you've made a real application, and have sold it to a customer. The customer soon responds back: "On big inputs your program is too slow, while your competitors' solutions don't have a problem... Can you fix your program?"
And you reply: "No, my program is fine, increase your time limits instead and ignore better solutions."
Does this sound plausible? If you choose to write in language X, you have to know and accept its advantages and disadvantages. It is your choice to use this language, and so you can't complain if its disadvantages bite you back.
I'm not sure which solution of mine accidentally became Java, but I was unaware that I still use this language for Codeforces. Thank you for correcting me. I will be sure to take Java's disadvantages into account when coding in C++.
The issue with this problem stems not from the fact that a slow solution is not passing. The issue is that, despite the fact that the contestant is really solving the problem, different methods of printing result in wildly different verdicts. Besides the precedent of specifying not to use cin when this is a possibility, this is just a terrible problem from an algorithmic standpoint. What is the purpose of a problem that is all about choosing the correct printing method? Perhaps it's good as a homework problem, but it has no place whatsoever in a contest. Especially since some languages just can't do it (and Java is not exactly an obscure language...) under typical circumstances.
Anyway, there is a profound difference between industry coding and recreational coding. Pick any nontrivial problem, and pick a random solution. Is this code you want to see in production? Of course not. With some exceptions, the formatting will likely be difficult, there is likely to be silly hacks to get around issues rather than writing clean code (as there should be with time constraints), but most importantly you probably need to take a long time to figure out what the code is doing. When was the last time you saw a solution with proper documentation, abundance of comments, and written for readability, accessibility, and evolvability? So the objection "this code wouldn't be good in industry" is a stupid one — no contest code would be good in industry (if it is, you're probably not doing contests right!).
I'm not sure whether you work in the coding industry, but when was the last time you considered runtime as a serious factor? Besides not doing something insanely stupid like making a code O(N^8), there just isn't a great need to. Sure, several algorithms are useful, but implementing complicated things to avoid a logarithmic factor is silly. And anyway, code should not be elegant or clever — it should be readable and understandable. If you see
in somebody's code, even though this is some pretty damn cool code that person should be out of a job quickly. It's not worth the headache that someone else is going to have when trying to edit this code a few years down the road.
I suppose we'll agree to disagree, but I think a good contest problem is one that provokes thought, has a nice solution, and gives that "aha!" moment when you solve it (perhaps because of my math background where an inelegant problem is considered a huge disappointment, not a good exercise). This particular problem satisfies exactly 0 of these criteria. Ok, maybe you have to think a moment to realize you can just connect a vertex to the k nearest clockwise ones, and maybe another moment to prove it if you're so inclined. But there's nothing interesting about the problem, and it's not one of those problems that you recognize a week later as "oh, I remember that problem! That was a nice one" (assuming you remember it at all, which this problem doesn't give much reason too). It's just not a good contest problem. A good homework exercise in the speed differences between output, but not a good contest problem.
Did not want to edit such a long post. I want to clarify that I don't mean anything against the authors of the problems. Writing good contest problems is very hard, and ensuring they are more or less new (or at least not recently used) is just as hard (for example this problem from a month ago is extremely similar to this C). Anyone who goes through this self-inflicted pain is to be commended regardless of the end result. Bad problems happen, and when they do all we can do is give as constructive criticism as we can and move on.
I had an interesting situation yesterday. I solved this problem in my favourite language — PERL. I sent submition and it passed pretests. Later I thought that Perl may be too slow to AC, and it was easy to translate Perl code to Pascal. So I did. And then I skipped my Perl submision, and sent Pascal's. At final tests I have TLE. But later I tried to send my Perl's program and it passed through 342 ms (6392774). So sad I was! But I was surprised, that Perl can do this!! My Pascal submision used up to 1000 * 499 iterations each having 2 "write", but later I joined to 1 "write" and passed in 826 ms. Why Perl hadn't TLE? I used array to push here my results, and later I asked to print whole array. Another succesfull variant was to make empty string, and add to it ("push back") answers, and later — ask to print this line (or so called "multiline") — 6395984 857 ms.
В div. 1 B предполагалось O(n * 2m)?..
Да. По крайней мере, у меня такая сложность.
Да: сортируем людей по числу мониторов, которые они требуют. Далее вычисляем в этом порядке динамику best[t][mask]: какую минимальную сумму можно потратить, решив задачи из mask с помощью первых t людей. Когда best[t][(1 << m) — 1] != inf, обновляем ответ числом best[t][(1 << m) — 1] + b * k[t].
Блин, div.1 звери. Как-то совсем много народу порешало...
P.S. A упала из-за кривой проверки на -1, B упала из-за отсутствия сорта. Победитель по жизни я, лол.
Почему сортим в возрастающем порядке по мониторам? Мне кажется наоборот, чтобы избежать ситуации, когда мы не взяли чувака с большими требованиями по мониторам и маленькой ценой, а потом нам пришлось взять мониторов больше...
По сути, мы перебираем количество мониторов, которые придётся поставить. Для каждого количества мониторов мы получаем, какую минимальную сумму придётся заплатить людям, которым хватит такого количества мониторов. Когда мы доходим до человека с большими требованиями по мониторам (это будет ближе к концу) мы обновляем минимум с учётом его цены и задач, которые он умеет решать.
Кстати, первое измерение в таком дп не нужно, всё можно обновлять в одном массиве (потому что два раза одного и того же чела не выгодно брать, и такое обновление не произойдёт).
Div.2: Why not 1000-1000-500-2000-2500 ? I joined to contest when less than an hour left, and solved only C. Statistics said to me to try to do so.
For D-Div1 I thought of 2 segment trees that you hold while you are decending in a rooted tree. Of course , I have to find the LCA in log(N) and the point that is at the middle distance between two nodes ( also log(N) ). It's quite complicated because is a lot to implement.
What would be a simpler way to solve D ?
Worst English statements Ever!
When can we see our new rates? When is the system test going to end? Anybody knows?
В задаче B подразумевалось N*2^M? Если да, то как-то не очень, при ТЛ 1 сек...
Почему? ~10^8 операций в секунду — то зайдет спокойно.
Я тестил в запуске — если вообще все переменные long long и делать в vector, то не пройдёт. Если long long только те, что нужны и делать на массивах — вроде, едва, но влезает...
Я просто оставлю это здесь.
Пузырек, это ты?
Выбором же.
Ну если лень
structзаводить...смотря на каком компиляторе)
6386589 — а что не так с TL?)
Действительно :)
998 мс XD
Div.2C I used cout instead of printf, and it turned out to be TLE. So sad!
I used cout, but got AC. http://mirror.codeforces.com/contest/417/submission/6387198
cout<<endl;
and
cout<<"\n";
perform differently.
In particular, the former flushes which is why it is slower.
cout << endl; flushes every time.
What a weird contest it was. So many WAs on A and B (Div 2).
Hundreds of solutions failed because of one fucking endl.
And hopefully hundreds of authors learned to use
'\n'or"\n"instead ofendlnext time.Or to use
cin.tie(0);, I believe.Fortunately I passed Pro.C(Div.2) by a fluke with 997ms using
endl.6390244
I don't understand why my solution passed 1000 499 and failed on 999 499. http://mirror.codeforces.com/contest/418/submission/6386127
On 1000 499 your program took 966 ms. Not surprising that another similar case would take over a second, it's just random variance.
But it should be strictly less, shouldn't it? The latter case will have less iterations. If this is random variance, then this problem was a mistake on the part of problem setters.
Suppose that with probability 95% the
999case will execute in time from 949 to 1049 milliseconds, and the1000case — in time from 950 to 1050 milliseconds. Still this doesn't forbid the first case from executing in 1040 ms and failing, and the second case in 980 ms and succeeding.I don't know. But maybe division by 999 is slower than by 1000?
The problem http://vn.spoj.com/problems/VMQTREE/ was similar to the Div. 1 D problem today, except the 50000-limit and the multiple-tests. Sorry, because I don't have the English statement.
We haven't known that.
Can you explain why in problem E you used pashka solution as reference one, but only set TL about 16% over its runtime? What wrong solution you tried to fail with such tiny margin?
Sorry for late answer.
Because there is normal solution, which is passing in the half tl, and for this one we haven't normal proof about asymptotics. Because of that we have added special test at which pashka's solution isn't working well. This is the same test at which you have failed. But it have passed because of the buben-constant and I wanted to make my solution to pass half tl.
And it was so pity, that your solution haven't passed, because this contest could have been the "best" contest.
But you had not answered second part of my question — what solution had you tried to fail? Also you either want approach to pass — and that means setting tl at least 2x of the approach runtime — or you want it to fail — and that means setting tl several times under this approach. You did neither here
I wanted that the solution, that you have sent, could pass only with some buben-optimization. I can fail pashka solution too, if I manage against some constant. Really, pashka's solution don't pass. I don't know, why you know background information.
Well, I can prove my solution's runtime. It is worse than yours by factor sqrt of log. But now lets look at c++. Do you think my solution rewritten in c++ would not pass?
Probably it can, you can check it. I don't think, that it can be much faster because of memory.
And sqrt(logn) gives you x4 slower solution. And it's big difference.
I think, that this is my fault that tl isn't so clear, but as a result the solution with wrong asymptotics haven't passed. I think, you can agree with my last statement, that wrong asymptotics shouldn't pass. And here you have written solution on your own risk.
I do not believe anyone within one's mind would try to differentiate solutions with factor of 4 because just so much depends on implementation. I do not believe you wanted to and I do not believe you are sincere when you say that you are glad you did. I do believe whole contest has poorly set time limits
Maybe you are right, maybe I'm wrong. But we haven't asymptotics for this solution. That's why we aren't consider this solution to easily pass tl.
My sincere apologize, but your solution has wrong asymptotics, and really I can't see the problem. If somebody have solved this problem with the same solution, we could have considered to change tl.
Because I believe given existence of solution with runtime of 3 s one need to either set tl at least 6 s or at most 1.5 s (and while we are at it I do not like tls of less than 2 s at all — if you do not want to clog judge queue use multitest)
I was tester of that problem. I'm so sad that I forgot about this match and skipped it :(
Too weak pretests. TopCoder level weakness, except there we at least see those tests.
Обрубать решение по C(div2)/A(div1) использующее потоки, мне кажется не особо правильным.
использовал cin/cout. Зашло: 6393221
Поменял в cout выводе, endl на "\n" и получил accepted.
Еще лучше
ну это то логично. Надо знать специфику языка , на котором пишешь. endl сбрасывает буфер, от этого он жутко медленный
причем у одних заходит, у других нет, хотя код практически идентичный
I can't believe I got 3 'Failed System Test'! My experience in contest: Always use printf :(
dont you think its unfair? For Problem C Div 2* half of the people who get pretest passed got time limit for not using something like printf!!!! please for next times mention that we should use! (sorry for bad English)
I think you are talking about Problem C Div 2 and not Div 1
Задача А(див1) была хорошая, интересная, но разве ее главной фишкой было повалить решения на выводе ответа?
Так или иначе, спасибо, узнал много нового про <<endl )
6386203 vs 6394768. 26 тест на cout — TLE, 1000ms, на printf — AC, 108ms. printf в 10 раз быстрее..
Я просто оставлю это здесь: http://mirror.codeforces.com/contest/418/submission/6397234
printf() быстрее iostream в некоторых случаях.
Is there anyone else, who got AC on Div1 C using random :P? http://mirror.codeforces.com/contest/418/submission/6394595 (corrected link) So bad, that I couldn't make it during a contest, because my solution got TLE on case 2 1 ; / (but not on 1 2 :P).
I used random in Div1 C to generate two rows of length n and m.
But if you got that it suffices to generate two rows of that length you have already solved 90% of problem :P. So it doesn't count :D. I tried to find solution of form
aaaaaaab
cccccccd
eeeeeeef
... and fortunately solution of that form always exists :P (at least for n, m <= 100 :D)
Yeah I checked that too during the contest but was not able to continue XD. how do you use that fact?
Just generate some rows of that form which fit, start from any initial position and change one randomly chosen row from actual candidate to solution into another randomly chosen one from all generated rows till you got a solution. Also you can look at my code.
Can you explain a bit your idea , please ?
I took 4 random numbers in range from 1 to 100 and put them like this:
202 ms
Wow, solution without any deeper thoughts and it works :D! Great!
but why does that work?! i tried to prove but couldn't, please explain a little more.
Actually it does not work :D. "50 68" is a counterexample. Even if solution exists my computer says that it will get TLE :P.
Oops =)
However, such a solution does not exist for this test and some others:
But if change the upper limit to 120, it will be for any input.
In fact, we can just iterate over these 4 numbers. With the limit of 120 it gets AC in 15 ms
I iterate over all 4 numbers and got Accepted
First I think testcases are too weak but I don't now is that fair or not.
Second why if the limit is 120 this solution is valid for any input ?
cout<<"Thanks"<<endl;
I don't know if solution of that form exists for any input, but I'm pretty sure that setting limit to some constant won't be sufficient for arbitrarily large input. And why 120 works for n,m<=100? Because you can simply check it for all valid inputs :P. I doubt that there is a nice proof of that fact.
just cout<<endl nd cout<<"\n" being the reason for AC nd Tle is not justified. Not at all.
TLE in Div 2 problem C with cout , AC after the contest with printf -_-
UPD : sorry , i clicked russian by mistake
Название контеста warmup подобрано неспроста — оно характеризует состояние многих участников после написания этого контеста :)
Give this comment '+' if you want the contest be unrated. Give this comment '-' if you want the contest be rated.
Спасибо, конечно. Раньше не обращал внимания на сброс буфера из-за endl и последствия этого. Теперь буду знать.
Но все же, что это такое?
С какой радости? Там после 41 этот тест еще несколько раз встречается, или больше нету?
Ох лол.
ну т.е. при горстке везения, могло пройти и с endl получается
Даешь анрейтед!
TLE in Div 2 problem C with cout , AC after the contest with printf -_-
Me too :(
cout's normal behavior is to sync with C's stdout stream. Put this as main()'s first instruction:
ios_base::sync_with_stdio(false);You should expect a major io improvement.B div 2 had a very vague problem statement.Half of my friends interpreted it differently and most of them failed.In my room too only 2 solutions passed for B.
при системном тестировании выдал тл. после раунда переотправил то же самое решение и полное решение. как это? http://mirror.codeforces.com/contest/417/submission/6395189 http://mirror.codeforces.com/contest/417/submission/6389180
во время систестов нагрузка больше => решение которое еле влезает в 1с (982 мс) на дорешивании вряд ли влезет в 1с на систестах.
p.s. flush всех неплохо потроллил на контесте :)
Время выполнения программы зависит от состояния кешей процессора и памяти перед её запуском, от прерывания программы другими процессами и/или перевода программы на другой процессор (хотя Codeforces наверняка это минимизирует), и от других факторов. Так что время на разных запусках может немного различаться.
печаль...
А как посмотреть протокол по взлому? Во вкладке "взломы" написано — "Нет данных".
I don't know it was good or a bad contest/ typical or harder set but I must say, the feelings is different this time. Couldn't understand A (replica of april fool contest! what is given and what they demand!!! ). Learned an excellent DP from problem D. it was a nice trick to sort the input. And about E, i will definitely like to learn to solve this problem. by the way I found a solution for N*N and if it were a square matrix then it would be at most C in div 2. :p . Overall , I enjoyed this contest.
6389193 на локальной машине тест 2 0 1 1 1 даёт ответ YES, на сервере же NO
gcc версия 4.8.2 20140206 (prerelease) (GCC)
Если вместо
base a[n];написатьstatic base a[100005];, то ничего не меняется?нет
Если функция-компаратор для
qsort()для каких-то двух элементов возвращает 0, то тогда их взаимное положение в отсортированном массиве не определено. В этом тесте как раз оба k равны.А на java вообще реально A в Div 1 сдать было? http://mirror.codeforces.com/contest/418/submission/6387067
Ух ты — а в Java видимо с точностью на оборот, чем в Си: println быстрее printf работает. Пруф: http://mirror.codeforces.com/contest/418/submission/6387067 http://mirror.codeforces.com/contest/418/submission/6395913
In problem C of div 1, we only want to find two matrices: A[m..1], B[1..n] and the result will be A x B and matrices A, B such that sum of square of all its elements are also a square. But we know that: 169 can be express as sum of k square number with 1 <= k <= 155, so the given problem can be solved straight forward. This is my code:
http://mirror.codeforces.com/contest/417/submission/6395366
Для чего в D(div2) требуется сортировка по мониторам?
Div1 A / Div2 C can be used to compare time taken by different print statements.
Time taken on my solution —
1. Using cout and endl 998ms :)
2. Using cout and "\n" 265ms
3. Using cout and '\n' 202ms
4. Using printf 296ms (strange?)
Can anyone explain why 3 is faster than 2?
Because
printf("%d", x);has to parse the format string each time, andcout << x;already knows at compile time what should it print,coutin theory should be faster thanprintf. And it seems that in this case it is not only in theory, but also in practice.I think 3 is faster because interpretation of one sign takes less operations, than interpretation of string, contains one sign.
My solution for Problem C got TLE on Test Case 40(solution id: 6392630) during system testing and after the contest I submitted the same code, it passed Test Case 40(solution id: 6395155). After some time, I submitted it again and it got TLE on test case 34 (solution id:6395832) which it had passed on previous two submissions. Don't know what's wrong??
C div 2.
cout<<endl; — TL >1000ms
cout<<"\n"; — AC — 500ms
Объясните, пожалуйста, что не так с этим генератором http://pastebin.com/kHiDe0qg для B Div 1 ? Говорит, некорректный взлом: FAIL Expected EOLN (stdin) [validator validator.exe returns exit code 3] Уже раз двадцать код пересмотрел и так и не понял в чем проблема.
Пробел в конце строки?
printf("%d ", j+1);выводит один лишний пробел в конце строки.Без пробела тоже отсылал. http://pastebin.com/MaV2PF2k
А теперь отсутствует перевод строки в конце теста.
Возможно, в этом дело?
Стоит убрать
if. Последняя строка ничем не отличается от остальных, она также должна завершаться переводом строки.can anybody plz explain how to do div2 problem D.
thnx for help .
plz explain how to solve problem D of div 2 .
The number of problems were only 20, so we can ask what is the min cost for a given subset of problems. To do so, sort the persons offering services in decreasing order of monitors demanded and for each one of them run a subset-sum type loop update for each subset 0 ... 1<<m -1. This ensures that subsequent updates to a set from a subset has fewer monitors and hence does not include the cost of monitors, only the extra cost x. Include the base case of monitors cost + x for subsets covered by single persons and you are done. Time Complexity : O(n * 2^m)
Sad situation in problem C div2. This shouldn't happen again. -_-
However, other than that, it was a great contest.
was it only me or did anyone else have difficulty understanding the very first question? I thought the no of problems was 2 for this case
1 10
7 2
1
because 1 problem for main round and another problem for additional round.
for this
2 2
2 1
2
no need of problems, all the past finals winners will proceed.
So, my assumption was there can be three cases 0, 1 or 2. Can anyone explain what the question is really asking? I appreciate it.
think like this:
the number of winners from rounds is at least equal
n*m-k, andif he decide to have
imain rounds andjadditional rounds, then total problems isc*i+d*jand total winners from rounds isn*i+j, andthe question asks you to print the smallest value of
(c*i+d*j)that satisfiesn*i+j>=n*m-k:)Это был бой не на жизнь, а на смерть...
Почему не сделать тайм на Див2 Д 2 секунды? На джаве дп по маске и номеру друга не заходит, на ++ заходит. Решение со сложностью из разбора.. обидно как-то (или я не умею писать на джаве?)
Я когда даю раунд, пишу решение на джаве, и даю тайм лимит так, чтобы заходило, как-ни-как, популярный язык...
А так, спасибо за раунд — отличный!
Все решения написаны на Java.
Значит, не оптимально я пишу дп по маске... Спасибо, буду разбираться, извините за осуждение, просто огорчился.
tourist had so much luck in this contest :P! Egor on 2nd place got TLE on E, because TL was very tight and flashmt on also 2nd place got TLE on A, because of endl's instead of \n and they will easily win if it weren't for those unlucky TLEs!
Horrible problem statement. Could not understand A and B of Div2.
Problem A,B and C is too week in data
The problems is nice,I find many bugs in my code,although I have passed the pretest
Getting WA in case 11 in DIV2 number B problem :( :( Can any one provide me a small test case for which i will get WA? Here is my code.6398585
А это нормально, что в Div1-B заходит следующее решение: динамика, состояние описывается двумя параметрами: маска решённых задач и количество мониторов, которые имеем. А меморизация происходит через map<pii, LL> ?
Could someone explain to me the Div2 C problem ?
Я, наверное, один такой, у кого возникли проблемы с пониманием условий в этом раунде.
Задача B\Div2
"... каждое отправленное решение A характеризуется двумя числами: x — числом различных решений, отправленных до первого решения, идентичного решению A, и k — идентификатором участника, который является автором решения."
Мне не было понятно в течение раунда, характеризует ли x число отправленных решений всеми участниками или только одним, под номером k. Такая формулировка мне кажется более ясна:
"... каждое отправленное решение A характеризуется двумя числами: k — идентификатор участника, который является автором решения и x — число различных решений, отправленных участником k до первого решения, идентичного решению A"
Задача D\Div2. Стоило, наверное, отдельно прописать, что каждый друг может решать уже решенную задачу. А то в итоге непонятно, стоит ли использовать xor или or.
Пишу сейчас виртуально этот контест для Div. 1 и стабильно получаю "Отказ тестирования" по В. В чём проблема?