Всем привет!
В ближайший четверг 30 мая в 19:30 MSK пройдет Codeforces Round #186 (Div. 2), автором которого являюсь я. Это мой первый раунд на Codeforces и я надеюсь что все получат удовольствие от решения задач на нём.
Спасибо Геральду Агапову (Gerald) за огромную помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский. Также, хочется поблагодарить Ваню Здомского (ballon), за то что он протестировал раунд.
Разбалловка сегодня такая: 500-1000-1500-2500-2500
Good luck & have fun! :)
I hope that the contest will be rated.
This is not your problem!
That's why you have to respect this simple rule : "You may edit your comment only for fixing grammar mistakes or small changes. Do not change the main idea of your comment."
Fast announcement.
hope this round be successful
Hope all.
Let's get ready for fun!
Александрийцы, вперёд! Я надеюсь, что у Романа Furko получится нечем не хуже, чем у Сергея Нагина (Sereja). Я очень рад за вас ребята!
НИчем не хуже и запятая перед "ребята".
Grammar nazi?
У нас сообщество филологов и лонгвистов? Главное, суть, а меня, как видно, поняли.
После "главное" нужна не запятая, а тире.
"грамотно говорить надо только специалистам в области языка" — очень популярная отговорка для тех, кто не умеет этого делать. В таком случае можно предложить Вашему работодателю выдавать Вам зарплату не точно, а примерно — он ведь не математик.
Про "логвистов" умолчу — это, надо полагать, опечатка.
Будем надеяться, что этот контест не будет третим Китайским контестом, как два предыдущих!
Сомневаюсь, что человек с именем Роман Фурко китаец.
Я имел ввиду не его национальность, а сам контест)
Обидно, когда минусуют и не знаешь как это остановить.
ага, еще обиднее когда пишешь новый комментарий, и его минусуют больше.
Так не пишите такие коментарии!
Судя по логике этой ветки данный коммент насобирает минусов!
А этот — плюсов!
Хотя скорей всего — огребу минусов за все три коммента :)
Lets just hope this contest goes fine and rated. :)
Wish this contest will be rated. BTW thanks for early announcement. :)
Oh MY god!!!I have taken part in three CF round...But I am unrated now(Because all of those three round have something wrong...)= =...SO I don't want to miss this one ....But ..At 23:30 on Thursday, I will on the train to Chengdu to take part in a invitation match.....WTF....Who can help me!!!!!
let me play for you. :D
only joking....
This is life.
Yes...life is cruel...
What kind of help do you expect?
I need a laptop when I am on the train.... and a wifi....Although I usually write code on the cellphone by c4droid and submit by chrome....But...as you know, it's not convenient...
So...please the judge system good luck and don't have fun ....please this round can be rated....I want to be rated!!
Hope this round & all participators can all be successful!
I hope everything will be ok this round.
For Furko its his first codeforces round and i hope that it will be very easy or very hard :)))
Надоели уже div2-раунды! Давайте нам нормальный раунд для обоих дивизионов!
Вот если взять пару задач B и C из предыдущего китайского раунда и добавить в этот в качестве div1 D и E, думаю, получился бы сбалансированный проблемсет.
Переходи к нам (div 2), будешь чаще соревноваться -)
Ты бы еще егэ порешал, вот веселуха!
Есть вопрос. Кто может участвовать в данном соревновании? Есть какие то ограничения?
Тык.
Нет никаких ограничений! Лишь одна помеха- разные часовые пояса.
Спасибо
Упс, понял, извиняюсь.
THIS IS MY FIRST CONTEST IN CODEFORCES ....WISH ME GOOD LUCK T-T
Good luck.
P.S: Your Captain Obvious
Thinks for this round.I'm so glad it's coming soon.
hopefully this round will be successful! good luck everybody! :)
This is going be heavy loaded contest. 2177 and still counts.
Not so "heavy" loaded. April fools day contest has 3200 registered user, and #175 has just a little more than 3000.
Don't forget it's just Div2 contest. I think many Div1 coders will not participate in it.
175 is also a div2-only contest :D.
Ok. I'm not saying, that contest is going to be the most busiest :)
After hard Chinese problems, I think easier European.
Gl && hF
hv?
good luck have fun.
Вопрос по-поводу системы оценки.
Если на контесте я первый раз отправил решение — AC. И второй раз отправил — AC.
И заметил, что в таблице по задаче появился +1, и соответственно снялись балы.
На системном тестировании их вернут? :(
Нет, потому что учитывается только последняя попытка, прошедшая претесты. Сами посудите: например, вы отправили решение, оно прошло претесты. Потом вы поняли, что решение лажовое, исправили и переотправили. Почему вам должны возвращать баллы?
Я имею в виду, что если моя первая попытка окажется правильной на системном тестировании.
Нет :) Почему это должны сделать? Согласитесь, это будет нечестно.
Первая попытка просто не будет тестироваться на системных тестах.
Спасибо. Я этого не знал.
Привык, что на ejudge засчитывается первая правильная.
This is the most unlucky hacking attempt, isn't it? :(
hmm... i'm pretty sure that you writed this contest from this account http://mirror.codeforces.com/profile/kingofnumbers2
But I didn't cheat :)
I only used one account in this contest
Anyway, creating 2nd account is prohibited by rules.
I think, this one is worse:
my submission 3800641 came pretty close to TLEing too.....thankfully it didnt exceed 2 seconds! :)
I think your IO is very very slow, because my solution get sum from 0 to n every iteration, but it's pass for 400ms. Try to use
ios_base::sync_with_stdio(false).what is the function of ios_base::sync_with_stdio(false) ?
This
wasted so much time trying to find out why my brute force solution didn't work for the second problem when a very easy dp implenetation I made in the end passed all the pretests... yet another bad contest for me :(
how solve problem D?
I was going to ask the same question!
dp[i][j] = minimum cost to repair j holes from the first i holes Complexity: O(N^3)
how do steps?
Try every i <= k < N, dp[k+1][new_j] = min(dp[k+1][new_j], dp[i][j] + minCost(i, k)). minCost(i, j) can be precalculated in O(N^3).
How to precalc minCost(i, j)?
You take all the intervals from the input and then do something similar to Floyd–Warshall.
The floyd-warshall part is not necessary.
Hey, do you have cerealguy's permission to use his photo? :)
I didn't know there was already a cereal guy here when I chose this pic.
You have my permission.
there are some minor differences, size of head and also bowl or even the table !
first of all, each cost[i,j]=INF.
for each l,r,c you get, cost[l,r]=min{ cost[l,r] , c }
then cost[i,j]= min{ cost[i,j] , cost[i-1,j] , cost[i,j+1] }
Uhn!Could you explain what is the meaning of the recursion formula and the 'minCost(i,k)'?
You have currently decided what to d with the first i holes. You repaired j from them. You try to repair every interval (i,k), i <= k < N. The cost to repair this interval is minCost(i, k) which is precalculated. You end up at dp[k+1][new_j] because you have already decided what to do with the first k+1 holes and you repaired some additional holes. Also, you can decide not to do anything at this hole (go to dp[i+1][j]).
dp[i][j] = minimum cost for fixing j holes out of first i holes.
dp[i][j] = min(seg.cost + dp[i-seg.size][j-seg.size]
where seg = {l,r,c} and all seg.r == j
I didn't submit as I was a minute late, but I believe it to be correct.
UPD: Nah, not correct logic, small modification required to it.
My idea is the same as yours but got wrong answer on pretest4.In fact,we won't fix a hole more than one time. try this test: 3 2 3 1 2 1 2 3 2
This is my idea but my code wasn't right for samples: First I define dp[i][j][k] = minimum const to fix at least k holes in j first holes using first i companies. while companies are sorted by their right points. And the update: dp[i][j][k] = min (dp[i — 1][j][k], dp[i — 1][j — (j — company[i].left + 1)][k — (j — company[i].left)] + company[i].cost)
I saw that the difference between second and third dimensions of dp is always the same, so I omitted third dimension. And so this dp is my solution: dp[i][j] = minimum cost to fix at least j — n + k holes in first j holes using first i companies while companies are sorted.
Is this solution right ? :-?
Как решать Д-шку ?
Очень походит на SRM 578 Div.2 — 1000 http://apps.topcoder.com/wiki/display/tc/SRM+578
I hope tests for problem C are good enough to fail Java solutions which use Arrays.sort().
Such test are included to pretests.
Yeah. I couldn't pass test 11 on Java. I finally pass them, when rewrite solution to C++
Thanks for trying to include that test, but my solution passed pretests just to time out on test 48 (Is that a hack input?).
I guess it is my fault to keep forgetting not to use Arrays.sort() on arrays of primitives
I add shaffle to my solution in Java and get TL too. Probably we need to read input data faster
I think it's 100% unfair. Quick-sort is the same for every language, Java probably have more overhead, but again — I think it's unfair.
Shaffle array before sort it in Java.
Ok. I got it, it looks like tests are written to kill exactly Java implementation of quicksort. Good job!
The default way of sorting things is not the same in every language. Modern compilers (GCC, Python, .NET starting from version 4.5, Java when sorting objects) tend to use
worst-case algorithms, mostly Introsort and Timsort. However, in Java, integer sorting still uses double-pivot quicksort which is O(n2) in the worst case.
So, is it way to fix it? Write your own sort?
Randomly swap some items of array. And after that u can use Arrays.sort()
You may want to know about
Collections.shuffleroutine.Yeah, according to javadoc —
Collections.shuffleruns in linear time. So it's a good solution. ThanksOr, box
int-s intoInteger-s and use an object sorting routine (Collections.sort?). It may be slower though in the general case.Funny stuff. I shaffle my List, but get TL again in practice.
submit in java 7
http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(int[])
The sorting algorithm used in Java for Arrays.sort(int[] arr) is tuned quicksort which offers very good average case performance.
Many contestants used Arrays.sort() today for problem C and have passed System tests. I think if the solution fails, the problem lies elsewhere.
My solution was using Arrays.sort() and failed pretests with TLE.
The same solution is passing after these changes: - Use FastScanner implementation by martinezgjuan (which uses BufferedReader + StringTokenizer). - Use Java 7 (not Java 6)
Now is passing with worst running time 951ms (no need to shuffle the array).
Java 7 also uses quicksort, it's just your luck that nobody has made anti-java-7-hack.
AFAIK java7 uses TimSort
У меня в конце произошла странность. На таймере в комнате еще минута оставалась, а в общем положении уже написало что соревнование завершено.
I am really curious about what the pretest 4 of problem D is.
Тот самый момент, когда ты — тот самый Лев Илья
that was a great contest after ... :)
May someone introduce the intended method for Problem E ?
anybody knows why system testing is taking very long time today??
Big number of testcases for problem C, I guess. Also, contest is merged for both divisions, so there is a lot of participants => solutions to judge
and a lot of submit in contest
Ask messi. He is best ;)
EDIT : I thought there are more FC Barca fans than others in CF and I'll get pluses. 8)
Problem D is really beautiful, solving it was tons of fun!!
Furko recpect and yvazhuxa
O(N3 + M) on problem D got me TLE :(
It's funny. My O(N^4) passed.
Sometimes the speedy inner loop is more important than the asymptote. I wrote carefully to eliminate 31/32 of the transitions in the dp without computing them.
Mine solution is even slower, but passed.
haidora1, I think that the cycles
if f[N].size ~ M , give you O(N3 + MN2) .
Thank you , I can see what's wrong now.
Thank you Mr.Furko I enjoyed the contset was good although I have a low rank ^_^
TLE-SOLUTION passed solution why the second solution passed and the first one get TLE
Wow, so many AC for problem C which pass with execution time of exactly 2000 ms, which is the TL for that task. Ofcourse on the other hand some codes definitely fail by only a few ms in this case. Now I wonder — is the TL set a little too low and hence might reject some codes with TLE even with the correct idea/implementation of solution OR is the TL a bit too high and that's why it lets some weaker codes pass that actually shouldn't?
The Time limit is enough, those codes probably used slow input methods
unrated?
Why lol?!!
когда появится обновление рейтинга?Furko — хороший контест.
So, what is the point for CodeForces to support several languages as they do if you will have problems that cannot even run within the time limits using that language, regardless of how efficient you do it. You may have the exact same code in Python and Java, but you get TLE in Python (The same happens sometimes with Java and C++). Then, why support Python? Why don't you just get serious and support languages in which problems can be done like in TopCoder? Or just increment the time limit for certain languages, whatever you feel more confortable with. That would be a lot easier for contestants! In my opinion, it is NOT fair to get a problem wrong when the algorithm is identical to others who got it right, being the code language the only differentiator.
Can't agree more. The same algorithm runs in time if coded in C++, but in python it gets TLE. This happened in problem C for many Contestants.
Python is easier to write correct code in than C++.
The syntax is simpler, the edge case and corners are less likely to cause you trouble, the array bounds are checked so that errors show up right away, debugging and tooling is better, Python has a repl so you aren't always compiling-testing-compiling-timing just to try an idea, and you don't have to worry about static type declarations. C++ is a pain with cruft from legacy implementations, the syntax is verbose and cryptic, the template system is full of hidden troubles waiting to bite during a contest, and even the compiler error messages are indecipherable.
But C++ runs about ten times faster than Python.
So there are advantages and disadvantages to both. You are allowed to switch languages between problems. You can even pick your algorithm and then choose your language for each problem based on speed and convenience.
Being able to choose wisely is part of competing here.
I have to disagree with you there. I know Python have a lot advantages over C++ in terms of readability, testing and debugging; that's the main reason I code in Python rather than C++, or even Java that I use as my second choice.
I believe it can be challenging enough to come up with an algorithm that works for a particular problem and also have a quite good and reasonable complexity. So, why would my solution be wrong when is as good as yours?
I can see how almost every C++ coder codes everything in C++, but you can say that you have to "choose wisely" your code language for a particular problem, when even the easiest problem you already code it in C++. So, when do you actually choose? I believe that is not the reason.
I think the main issue here is that it was not possible to get AC in Python with any solution. While I understand that you have to think about efficiency twice in python (sometimes naïve code gets accepted only in C++ while in other languages you have to think of smarter solutions), I still consider that the most important ability to learn in these competitions is algorithmic skill, not language syntaxes or quirks.
In my opinion, is better if, for these kind of problems, Codeforces won't accept Python to avoid the misleading information that is possible to solve the problem with Python.
In short, we (at least me) are not here to learn the syntax and tools of languages, we are here because we would like to solve algorithmically challenging problems.
I think the constraints were not very well checked for the problem C. My code in Java barely passed the tests (1880ms) by even using fast custom made I/O routines and with an O(n lg n) algorithm. Had I not used the fast I/O library my code would have easily failed. And Java is not even one of the slowest languages supported. So either time limits should be loosen up a bit and maybe also increase the input constraints so algorithmically worse solutions fail even in C++.
I don't think so. This for loop might be the reason why the code is slow. for(int i=1; i<=n; i=4*i){ for(int j=0; j<i;j++){ total+= nums.get(j); } }
There are ways to do the for loop in a single pass by noticing the math pattern. E.g. http://mirror.codeforces.com/contest/313/submission/3799994
Oh, then it could have been a bit faster. Thanks for the tip :)
Your pass is not that slow though :). 1 + 4 + 16 +... ~ 3 passes of the array.
When I see n <= 10^5 and I have a O(nlog(n)) or faster solution, Python is the first choise.
So… You have a job, your boss gives you a task and you implement it in Python. Everything is great, until customers start complaining that they have to wait minutes for your software to run. But you don't see it as a problem and tell your boss: "I know, it's Python, just tell them to wait more!" Does this sound realistic?
In my opinion, programs should be judged against real-life criteria, such as real running time and memory usage, not against arbitrarily chosen adjustments so that "different languages are equal". This is fair, and treating programs in different languages differently is not fair. If your language fails to be on par with others, then it is the language's fault, not Codeforces' fault.
It is about using the right tool for the job. C++ and Python have their advantages, and also have their disadvantages. C++ is fast, but hard to program in. Python is easy, but slow. You consider both options (which is more important — short code or fast code?) and choose the better tool in order to achieve a better result. If you knowingly chose the inferior tool, then it is your mistake and you will get penalized for that.
Now, here you might say that you had no idea your Python code would run so slow. But this is just a part of the learning process — you tried it and received negative feedback, and this will affect your future decisions (you will likely choose not to do the same thing again).
как ведется подсчет рейтинга?в первых 3 контестах у меня было решено 0,сейчас я решил одну задачу без штрафных баллов и почему-то минус в рейтинге,подскажите кто знает,как то не совсем логично получилось.
http://mirror.codeforces.com/blog/entry/102
My same code got Time limit exceeded in contest but Accepted in practise...
I wonder why???
TLE code : 3800440 AC code : 3803673
thats really mysterious....u should probably report this issue to the admin with the above details.
How to report?
sorry, i'm not sure of that.....but i suggest u send a message to MikeMirzayanov as he's the host of this site...
The same thing happened to my friend!
TLE: 3801046
AC: 3804156
So very wierd :|
Probably the way they measure the runtime of a code is not smart enough. Report it so they can do something about it, if possible. Not only your particular case but in general.
TLE code : 3799383 AC code : 3804162
It is really funny, IceTube has become purple and Goldensea is blue ! and I think he can't compete in Div 1
I had no idea about the difference in runtime between read using scanf/printf and cin/cout in C++. I always use scanf/printf in codechef and spoj but I was confident here in codeforces. I got TLE in problem C and I change cin/cout by printf/scanf and I got AC in 1 sec. Great, I will use scanf/printf here too.
Try resubmitting the exact same code that gets you TLE again. It could get AC now. A lot of participants have had this problem today. If so, I think you should report this to the authority.
Thanks man, personally, I will stop using cout/cin in everywhere.
The fact is, if you notice execution time, it gets clear why this happened.
take a look here deinier: http://mirror.codeforces.com/blog/entry/925
Thanks for your help man, I read this great post. lol, using (_ios_base::sync_with_stdio(false);_) it was faster than using printf/scanf. Thanks a lot. Here is my submission.
Sometimes, writing a function to read is faster than printf/scanf.
Спасибо за интересные задачи и хороший контест. Рад был порешать.
It seems like many participants' solution of problem C got TLE during the contest but the exact same code gets AC after the contest! This is really unfair for the people who've faced this.
Any quick explanation on how to solve Problem E?
Greedily, i in set A should add m-i-1 in set B. If the amount of i are more than m-i-1 's, we should add m-i-2. Before that wo should do i+1 add m-i-2. So use a stack to solve it. Complexity O(m+n). The O(n) is printing answer.
I'm sorry that I don't know how to write clearly. Please read my code if you interested. 3803851
What is meet-in-the-middle algorithm ?
I have only used this algo once, with some help from a friend. So I might not be able to explain efficiently. Still giving it a go.
Here's a demo of the algo -
You have a set of integers consisting of no more than 34 elements and want to find the number of subsets such that the sum of the integers in a subset is an integer N (N is a known value).
A brute solution would be to try all 2^34 ways, which is not efficient.
So what we do is we split the set in two equal subsets (meet in the middle algo), try to form all possible subsets for each set and record the results (the number of results is at most 2^17 for each set), then for each element in one set, run binary searches to find upper limit and lower limit for compatible results in the other set.
I don't know if this explanation is good enough. Maybe you can take a look at this. http://www.infoarena.ro/blog/meet-in-the-middle
Why my code got WA on testcases 11 ?3805151
use long long to store the answer. The maximum is near 2*10^6*10^9 ~ 10^15
Read clearly, he used.
I used, thank you all the same.
Can someone give me an idea for Problem C??
I was actually trying to simulate, but I think it is unnecessary... can someon eplease help?
yes, actually you don't need to simulate the assignment in your code
the idea is to select biggest 4^n numbers then biggest 4^n-1 then 4^n-2 until 4^0
Great contest
Really waiting for editorial, specially for brilliant problems D and E. GL & HF!
Here is editorial in Russian.
Thanks, but where and when can I have it in English?
TLE : 3798859 ACC : 3806006 what should i do about it?
3806042 why am i getting runtime error? Its working perfectly on my console
In C89 you have to return 0 from
main(). Also, you should not cast awayconst.Thanks a lot.It got accepted after using return 0 :)
hopefully there will be a new round this sunday for both div 1 and 2.
Have nice grades....Need more practice.
3811425 Ilya and matrix Hi, can someone refer to above submission and tell me why it is giving TLE error. I mean i have written in JAVA and used the buffered reader. I tested the same on my laptop (a core2duo machine) for a test file with data of size 1048576 and those many numbers and it completes in 500millisecs. but i always get TLE. is my reading method faulty? or the algorithm. I only have one loop.
yeah got the problem. i was using Java6, changed to Java7 got accepted in seconds.
In C problem,why I used cmp function(write by my self) tle but didn't use can ac!!