Всем привет! Codeforces Round #FF(255) начнется совсем скоро! Раунд будет проходить в обоих дивизионах, приглашаем всех принять участие!
Главным героем задач этого раунда снова становится DZY! Вы все уже знаете, что DZY интересуется очень многими вещами. В этот раз у DZY есть много интересных задач. Задачи будут проще, чем в прошлый раз, тем не менее ваша помощь потребуется. В награду за помощь DZY подарит вам рейтинг.
Спасибо Gerald, который помогал нам в подготовке раунда. Также спасибо MikeMirzayanov, благодаря которому существуют существует Codeforces.
Задачи раунда готовили: jcvb, jiry_2 и я. Это наш первый раунд Codeforces :)
Ждем вас на контесте, DZY очень нужна ваша помощь!
Желаем удачи и удовольствия от решения задач! :)
UPD
Разбалловка для первого дивизиона: 500-1500-1500-2000-2500.
Разбалловка для второго дивизиона: 500-1000-1500-2500-2500.
What round 255? You mean Codeforces Round #FF (Div. 1), Codeforces Round #FF (Div. 2), no? :D
Yep:)
According to russian traditions, you need to say "Yept" instead of "Yep"
easier than the problems in last round — sounds great! BTW, in last round every problem was solved by >=10 contestants, hard to believe that this time problems will be even easier. But if they do — it will be nice:)
Surely it will be :) Wish you high rating ~
You were not serious about easier problems, right?)
Thanks for interesting contest. I personally think that problems were a little bit too hard. First 3 problems are enough to get into top-5, and nobody solved E... You expected such results? Could you please tell us what was your prediction of AC range for every problem before contest?
We've compared each problem in our round with the round #254. And we think our problem is easier.T^T
Hope this time problems could be more interesting than the last ones :).
We will try our best.
if i remember correctly, in the last round most of the problems were about you.
maybe now it is time for some revenge. ;) we will see.
hope not to be in your room :D like TC srm :|
Having skilled challenger in your room gives some advantage on CF. It increases chances of your wrong solution being cracked during round so you'll have an opportunity to fix it and get some points (instead of flat 0 without that challenge).
well, i am certainly not a "skilled challenger". :P
i actually had to resubmit my 250 (which explains my low score of ~100) because i found bug in my code after i submitted.
as it turned out, 4 others in my room also failed on the same case as my first submission.
P.S. ofcourse, your point about having a good challenger in your room is true. :)
LOL, but i changed nothing for you. your solution would have Failed System Test anyway.
but ofcourse it changed something for me, i got +50 points for making it Challenge Succeeded. :)
but you should not have challenged the problem of a guy who wished you luck before the contest :P
In that case. Best of luck everybody.
LOL, nothing personal, as u know. :)
in fact, i don't even look at the handle when i open code of participants in my room.
Chinese(Hangzhou Xuejun High School) round again!
Looking forward to Raccoon Round :D
you give me A Pretty Good Idea on setting a Contest！ Racoon Round may come soon~
Опять китайський раунд? все, я ливаю...
FF :) С юбилеем!
Early annovzbbsbsnxnnsnd...
Seem that, DZY himself is the problem setter this time.
Is it easy??
It's obvious that the problems will be much more difficult than you've expected.
So cute profile picture :3
If you meet MinakoKojima herself some day,you will find she is much more cute than the profile picture.>_<
What do you mean? Lol, I don't understand xD Anyway, now I have to meet her :D
Last time I didn't really enjoy DZY problems... Wish this time better than last time...
Why Codeforces Round #FF(255) but not Codeforces Round #255 ?
because 255 is a very big and special number... It's the biggest number char(C++) or byte(Pascal) can hold! (UPD: thanks vas.and.tor, who points out my mistake that unsigned short contains 0..2^16-1... Fixed.)
I guess it's "unsigned char" in C++. Biggest "unsigned short" can be around 32767.
maybe this is why.
I like he also brings us many interesting problems and I like more which are easier than the problems in last round
This is the first contest dzy493941464 hold. Hope him success in this contest
Thx :)
I think Div 1 E will be 3000...
That awkward moment when you don't even realize how hard Div 1 E is...
Many people know that feel, bro.
Ha ha. That's why I never read div 1 E..
NO 3000 but also NO 1000
Crap. It's DZY again. I'm scared.
You should also mention about the unusual time of this round so that no one might miss it.
It seems that the "Event Time Announcer" is wrongly showing this: Event Time in Moscow, Russia
5:00While it's going to start in17:00(Likely a mistake --> 17 = 5 p.m) So its start time doesn't really differ from the last one ;)i think what m17 means is that most CF rounds start at 1930 MSK, but this one starts at 1700 MSK.
easy problems are not good, because the rating matters how fast you solve the problems :/
Easier problems are good, because it matters how many problems you solve and not just how fast you can solve them.
First of all sequence of problems should be without large gaps in dufficulty, so a bit stronger contestant may easier overcome weaker one by number of problems and not just by time — we are competing in solving first of all, not in typing speed, right? Otherwise there is no difference — "500 guys solved 3 problems, 20 guys solved 4+" and "500 guys solved 1 problem, 20 guys solved 2+" are almost same scenarios for me.
As I mentioned in russian topic after last round, that round was pretty good — every problem was solved by 10+ users, nobody solved all 5 problems, number of AC is decreasing from A to E...
And I compared that round with "standard 1/5/50/500 round" (talking about number of users with first 5/4/3/2 problems solved). In my personal opinion rounds like previous one are way more interesting than "standard 1/5/50/500".
a math round?
It's only a normal CF round. :) Wish you high rating ~
Hello, ladies and gentlemen! It's DZY's show time! :)
I will get Violet
As it is Ramadan, is it possible to shift the contest at least 30min ? Current Contest starting time is same as the iftar time here in Bangladesh.
But great time in Iran! After the contest and system testings we have about 40 minutes to solve the unsolved problems and guess what after that! Iftar time! :)
And it's similar for Russia! (But just for their international time! As you know, Russia is really long country and I think the difference between it's leftmost city and rightmost city is something about 9 hours! Russians correct me please).
Russian timezones: from +3 UTC to +12 UTC exclude +5 UTC
In Morocco, we are 7 hours away from Iftar x) That luck though
what is that iftar thing?
http://lmgtfy.com/?q=iftar
I wanted to know a Muslim CF contestant's answer
why is Codeforces Round "#FF" ? 0xFF = 255, maybe the Round #FF is the next of Round #254 ?
That sounds Great! I hope it can be successful.
Kime gerek sen
orz Mao Zhuli
I can't participate to this contest because of the flight to IOI place.
What does fuking FF mean?
FF is 255 in hex (base 16)
fast finish
it's a recursive acronym. It means Fucking Ff
I think the next contest will be "Codeforces Round #100" as: FF + 1 = 100 (base 16)
hmm, really odd email i received from Codeforces.
firstly, there's no
#before FF, which is usually always seen in all CF rounds.secondly, "Codeforces Round #254"? seriously?
PS: take this as constructive criticism so that next time these mistakes can be avoided.
That means I'm not the only one. At least not the only one to notice :D
Maybe an automatic mailing system got confused: "Which name is round FF supposed to have? Oh well, I'll just use the latest one."
The round number is greater than 254. Codeforces rounds always have had number not greater than 254!
Oh my god... this is last round...
Next contest don't will... overflow byte..
No problem. Contests will start again from Round #0!
Hello from Taiwan.
thanks for our last chance to practice before IOI. Good luck and have fun everyone.
be careful! you will be demotivated if you failed a round just several days before competition. It may bring negative effect to the competition.. haha (at least I experienced this once.)
I already succeeded last topcoder round :D , I hope that I also succeed in this CF round.
Ah OK then, at least you already motivated by something :)
Anyway goodluck for IOI! :) It's very sad that I can't participate in IOI anymore :'(
Please prepare a readable and thorough editorial. Thank you :)
I hate when it says 'The solution is obvious' Waiiiiiiiit Nooo that is why I am here x)
For me, entering this round means not watching the World Cup Final. it's difficult trade-off...
No conflict between this Round and WCF ??!!! maybe you have no time for both
yes, I have at most 4 hours to sleep, if I do both.
Who cares about sleeping if World Cup final is just once in 4 years?
Soccer Maniacs wouldn't attend this round :v
Score distribution is a bit strange for me. 500 from Div1 used to be equal to 1500 from Div2, I guess, 1000-to2000, and so on. Today task C from div2 costs 2000, but task A in div1 (which used to be the same with Cdiv2) costs only 500. But, according to the logic of previous rounds score distribution, it must be 1000.
I understand, that authors know better, which one is correct, but isn't it a mistake?
UPD: Changed to 1500
I think This time task A Div1 Equal task B Div2
My Guess is
Div1 Div2
A = B
B = C
C = D
D = E
so the difference between two rounds will be A Div2 & E Div1
maybe I'm wrong let us see
1500 (B div2)? Все очень плохо
After do contest I will watch FIFA World Cup between Argentina and Germany
div2 B shows 1000 in the contest.
I...don't understand why Div 2 Problem A begins with "DZY has a hash table..." Do the problem writers actually expect Div 2 contestants know what a hash table is? (Div 2 contestants that can solve Problem D/E are okay, but how about beginning contestants that can barely solve Problem A?)
Personally, this is approximately how I'd phrase it:
DZY has p buckets, one of which is colored red. Each bucket can hold one ball. For the i-th ball, DZY starts with facing the red bucket and turns clockwise for xi buckets before putting the ball into the bucket in front of him. However, sometimes DZY cannot put a ball because the bucket he's facing already holds a ball. Output the number of the first ball that DZY cannot put.
There are alternative solutions for this problem without hashtable,We can do Vector Add numbers and Vector Add module for every number and every time , you must check , Are this number contains in this vector or not :) Hope it help
I know there is a solution without hash table. (When I finished reading, I already got the solution using simple arrays.) However, the problem here lies on the wording. It feels like you need to know what hash table is (even if you eventually don't use it) just to understand the problem. My view is that problem wording should be as simple as possible, even if the solution can be terribly complicated.
Here's a hopefully comparable analogy:
You are given points on the plane, forming a polygon. It is guaranteed that the polygon has a dihedral group of order 8. (Test case has no picture of the polygon whatsoever.)
You will most likely say "WTF" on the last sentence. Compare:
You are given points on the plane, forming a polygon. It is guaranteed that the polygon will be symmetric like a square: when you rotate the figure by 90, 180, or 270 degrees, the polygon remains the same, and when you reflect the figure along some line, the polygon also remains the same. (Test case has a picture of the polygon, explaining the symmetries.)
that's just a bluff :P
we can see high number of accepted submission for that :)
In hash table, if you put more time one number than it is not collision, but in this problem it was colision :(
Неужели в C div. 1 решение корневой декомпозицией по запросам было нежелательным? :(
У меня на претестах работает 2.4. Но вообще, на самом деле, несколько дольше, надеюсь, не фатально дольше.
Можете код скинуть? У меня как-то не получилось запихать, даже с заменой long long на int и убиранием взятия по модулю везде, где только можно
7084475 как-то так. но, я думаю, можно в табличке найти менее говнокодистые реализации.
Обидно, надо было, видимо, соптимизить взятие по модулю, а я и не подумал
У Вас похоже квадрат. Цикл
вроде sqrt(m) раз выполнится?
sqrt(m) * n * sqrt(m) = O(n^2)
У меня такая же ошибка была.
А у меня (7089602) что не так? Таки тоже где-то ассимптотику запорол? :)
Мда, действительно, спасибо
Неужели оно было желательным? oO Я его конечно напоследок засабмитил, но искренне надеюсь, что у жюри есть нормальное решение — иначе зачем n, m до 300000 давали?
Чтоб квадрат не заходил :)
Есть решение за O(m·logn) деревом отрезков.
Можете описать, пожалуйста?
Почти также как и прибавление одного и того же числа на отрезке. Только здесь прибавляем на отрезке последовательность Фибоначчи, порожденную числами a0, a1. Соответственно, в каждой вершине храним сумму на этом отрезке и параметры (то есть два числа a0 и a1) последовательности Фибоначчи, которая была прибавлена на этом отрезке.
Для обновления суммы нужно уметь быстро считать сумму первых k чисел Фибоначчи, порожденных числами a0, a1.
Для проталкивания ленивых изменений вниз по дереву нужно вычислить параметры последовательности Фибоначчи для правого поддерева, для левого параметры те же.
Еще можно заметить, что 5 — квадратичный вычет по модулю в задаче и по формуле Бине все сводится к прибавлению геометрической прогрессии на отрезке.
Прикольно :)
Правильно говорить не "можно заметить", а "несложно заметить" :)
Или даже общеизвестно, что...
Общеизвестно, что 109 + 9 весьма необычный модуль для задач в СП. Наверное, нужно было применять БПФ.
Да ладно, с недавнего времени это любимый модуль Petr'a; а если прочесть отзывы о том SRM, то станет ясно, что не только Petr'a))
Когда вы проталкиваете изменения вниз(скажем последовательность порожденная a0, a1), в вершину где уже какие-то a2, a3 записаны, что с ними происходит? Как их добавить?
ну почленно a0+a2, a1 +a3
Блин, точно, спасибо... Я вместо 2 чисел рассматривал одно — номер числа Фибоначчи, начиная с которого прибавлять, ну и не понял что с ними делать...
double post
Полцарства тому, кто скажет, что здесь не так: 7085342
простой народ не может посмотреть этого чуда
Я на это чудо в 30 строк полтора часа смотрел и разводил руками Т_Т
Это решение на В, если что.
Посмотри сколько серых минусов по задаче, и поймешь что ты не один такой. И ведь не понятно, баг в коде или в идее.
Там вообще работает жадность, что нужно брать строку/столбец с максимальной суммой на данный момент?
Тест:
Я перебирал, сколько ходов будут по строках и сколько — по столбцах, а уже внутри — жадность.
Не думаю.
3 3 2 100
3 6 3
7 1 1
3 3 6
Если сразу жадно взять первый столбец с суммой 13, все строки будут испорчены, и останется только брать второй или третий столбец с суммой 10. Лучшее тут — взять первую и третью строки с суммами по 12.
Это решение оказалось правильным по модулю того, что TreeSet не хранит дубликаты, как подсказали ниже.
TreeSet дубликаты не сохраняет
спасибо...
In problem A (Div1), are we allowed to change the numbers to zero? E.g. what is the answer for sequence (1 1 2 3) — 3 or 4?
4 — why shouldn't 0 be an integer?
Then I can't find an error in my solution 7083807 which got hacked =\
I think n=1
Oh no(
i asked this http://codeforces.me/contest/447, see below "Questions about problems"
The answer is 4.
and you also can change to negative number ...
Yes, even you can change it to negative integers.
According to the statement, you may change an integer to any other integer. Meaning that 1 may be changed for 0, -1000000000000, +1000000000000, 20 and -30 (even though some of this numbers are out of the the 10^9 value for array values given in the statement).
Кто-нибудь сдал в D(div1) n^3 log k ?
упс, это вообще-то дофига получается:(
Кто-нибудь сдал
вообще-то дофига получается
Часто одно другому не мешает:)
У меня n3log(1 / eps) + m3logk, где m — количество ловушек. так-то успеваю 17 раз матрицу 500 на 500 в квадрат возвести. logk — 30.
Наверное, все-таки не m^3
я вместо m написал k.
I tried hacking BhulJa div2 C which should have given garbage value for N=1 but it returned correct answer I don't know why .
Hi, Can anyone please explain your approach of Div1 B / Div2 D ?
Thanks.
The mathematical proofs are maybe a little bit long but pretty intuitive. Obs.: 1) It doesn't matter in which order you do the operations. 2) You can let 0<=l<=k be the number of line operations (and take the best variant at the end). 3) For a fixed l, use 2 priority queues to calculate the results for l and k-l elements picked both for rows and columns. 4) Combine the result for l (on rows) with the result for k-l (on columns) with a little bit of maths. 5) Don't forget about long long.
Is this equivalent to the greed solution? In my solution, at each step, I would select the best row or column (the one with greatest sum) using two PQ. I don't know if greedy works (couldn't prove it), but it really feels like it should work. No idea why WA. :(
I got WA on pretest 4 doing the same thing!
It doesn't work.
2 3 6 1 1 1 1 1 1 1
Sometimes you don't want to select the best row in order not to start getting negative sums.
It doesn't work. Consider 1 3 10 1 1 1 1
i'm just guessing here, but did u consider that every row's sum reduces by p during every column operation (and vice-versa)?
Yes JuanMata. It looks like Greedy is a bad idea. (Greedy is almost always a bad idea. I will try to remember that next time) :(
Actually there is a huge greedy part in the solution. You just have to be sure when you are using greedy algorithm, you should have proof or something (maybe not very rigorous).
The greedy part here is that if you look at choosing rows and columns separately, when it's about rows, it's always right to choose the largest row. Same hold for columns. Than it's easy to solve this 2 problems separately and merge them. You're gonna need to brute force how many rows you choose.
Forgot proof of a greedy strategy. Choosing largest row is optimal, because: (1) The order of rows chosen doesn't affect the final score; (2) Assume in the optimal solution the largest row was not chosen. Then, swap the largest row with any other chosen row. Obviously the score will increase, hence contradicting the optimality of a solution.
You can also prove that you can choose just rows at first and then choose only columns. I guess the details are already posted (at least in the editorial), so I won't go further into details.
No, its not equivalent. You solve the problem for only rows and only columns separately, and then choose how many rows and how many columns to use based on these results. The key observation is that each row operation reduces the results of each following column operation by p, and vice versa, so the total score is ScoreRows+ScoreColumns-NumRowOperations*NumColumnOperations*p, regardless of the order in which you do the row and column operations — this is because for each pair of RowOperation and ColumnOperation whichever comes first reduces the result of the other one by p, and there is a total of NumRowOperations*NumColumnOperations pairs.
Can someone help me to understand why my solution for div 2 problem E is too slow to pass test 9?
I use segment tree + lazy updates.
Thanks.
Что-то у вас не так со сложностью. Неужели нормальных несложных задач нету? Две С, да и то одна из них, как D. Да и А была скорее В. Итого, выкинуть самую сложную задачу и добавить одну, которая была бы проще всех остальных — было бы самое то.
А автор еще говорил, что будет проще, чем прошлый раунд... Вероятно, это было сказано сугубо в рекламных целях:)
Возможно, я не прав и моё решения скоро полетит, но мне кажется, что div. 1 A по уровню около div. 2 B
UPD: Не полетело.
Ага, мне тоже так показалось, что я специально 3 раза условие перечитал, и все время думал что пишу что-то то не то. А вот про B — напротив, не показалось. Проходит ли там жадность (если нет, то как ее вообще решать)?
http://codeforces.me/blog/entry/13004#comment-177525
Спасибо, не заметил...
А вот мне жутко не понравилась А, а вот В — наоборот, показалась едва ли не простейшей В...
UPD. Вот А и не зашло, в отличие от B...
In Problem C, DZY Loves Sequences, I made a minor mistake of initialising a variable to 0 instead of 1. So naturally, it gave WA. But after correcting the mistake and trying to re-submit, it says that
The exact code has already been submitted, and I could not submit it. How is it possible?P.S. I had saved the file.
I am being hacked at 17:57:37, The Codeforces send me the Announcement at 18:59:25, and I am very surprised about this (so bad)
Sorry if this is a stupid question, but how long does it usually take before the ratings are updated?
It's not stupid! I've been asking this question from myself since i've been taking contests! It never has a fixed time. It usually takes half an hour before the system testing part and half an hour (or even more) after that for rating updates :)
Это неловкое чувство, когда на одном тесте поломал половину сабмитов в комнате, а в конце контеста решил проверить работает ли моя прога на этом тесте и выясняется что НЕТ!
my idea for C div 2 is split the sequence if it's not an increasing subsequence, and join with the neighbour if possible (change 1 number from sequence left or right, and made strictly increasing seq)
here is my submission http://codeforces.me/contest/447/submission/7087449
any other ideas or my idea wrong ?
You can merge three consecutive segments(increasing sequences) also if the middle segment contains only one element and the first element of the right segment > last element of first segment + 1 .
hmm, cant think of test case for something like that while contest
anyway, thx for the answer
edit : my solution just lack +1 to the output if the max sequence isn't obtained from 2 sequence :)
Задачи будут проще, чем в прошлый раз, тем не менее ваша помощь потребуется.
Задачи будут проще
проще
после китайских контестов я себя чувствую таким ДНОМ..
can anybody explain me how to solve div-2 D . thnx
I encounter a strange issue during the contest. my ID became duplicate and every time I refresh my submission page its contents were different !
and when I locked my problem C ! (notice to contest time running!)
and some seconds later :
I deleted all my codeforces' cookies during the contest but still nothing were changed!
what was the problem MikeMirzayanov?
I'll investigate it. Thank you. I'll exclude you from the rating. It seems somehow you were registered twice (race condition?).
Yes, You're right. I have registered twice because I didn't see myself in registered users. Interesting racing condition!
why is system testing unusually slow today?
I will never believe in Chinese authors' word about easiness of the contest, specially of dzy493941464 :(
Who's idea to make C and B same points. Oh, well done really, Solvers of B is 6 times more then C :
64 * 6 ~ 343
why most of div2 C submissions failed system tests ?
can anyone give me the tricky test case which most contestants couldn't pass ?
I'm not exactly sure whether this is covered by pretests or not, but does your program work for
10 1 2 3 10 4 5 6 10? (Answer is 5; take indices 5 to 9 and change the middle 10 to something low. (Or indices 1 to 5.) You cannot change the middle 10 to 3.5 to take indices 2 to 8.)I'll guess just some cases:
n=1
the optimal subsequence takes 0 changes to make
the changed element is the leftmost/rightmost
I missed the second point. :(
Just added : if(!ans)ans=n;
Became AC
some forgot to check whether two segments of strictly increasing order are able to be merged or not, for example:
6 1 2 3 3 4 5
the two segments are [1, 2, 3] and [3, 4, 5]
these cannot be combined to form one strictly increasing sequence.
Try: 2 1 1 Answer should be 2
thanks all , I found the test case that my code didn't solve correctly
5
1 2 10 4 5
the correct answer is 5
DZY definitely starts to please me.
three people scored 1134 points, and they took the (joint) 254th position.
this unfortunately means that nobody could take the 255th position in the 255th CF round. :(
What a very sad thing, you made me cry -_-
I hope you can recover from this horrible shock soon.
Let's see the good part of things — in the div2 contest we have: 255, 256 and 4 x 2048 placers.
I got tle on test case 9 in div2-Q5. I used segment tree. was that too tight for the time bounds?
this is my code, possibly someone could suggest an alternative -> direct link
I have not tried the problem but maybe you could get the fibbonacci number using matrix exponentiation !
Maybe problem with tree array size or recursion? When i downloaded your code and run it on simply test like this: http://morse.swirski.name/pastes/l6hriqm93kn5wx5gvxckznn0ibd5zvh program crashed in build_tree() function.
When i change tree[] size i don't have this problem. But i'm not sure, cause it was on Windows 7 x64.
P.S. Sorry for my english.
if the solution did crash in build tree function, then it would had not run in that case. I checked the log and it seems that the tree was built perfectly but the program ran out of time while processing the M queries.
Wait... your update is logarithmic? You stop recursion only when low==high (in leaf). So update is too slow in my opinion (You must visit every leaf in (l, r) ).
Why DIV2 problem C's test 41: 6 7 2 3 1 4 5 answer is 4?
change 3 to 0
thank you.
Oh, I see.
Correct segment for ex.: [3->0 1 4 5]
After change, it can be "7 2 0 1 4 5". So the answer is 4.
Nice contest :D
Excuse me. But why my rating hasn't updated? I found that everyone's rating has been calculated but mine hasn't done.
Oh, sorry. Only Div.2 competitor's rating has been updated.
You can view country wise standings here. Send your hugs or bugs here.
Div1C http://www.spoj.com/problems/ANIL_PRO/ or http://www.hackerearth.com/problem/algorithm/fibonacci-updates/
Yes, I really appreciate an opportunity to test my solution for WA/TL on spoj during CF round, but I don't think it is a good idea to give such problems on CF rounds.
I am sure it wasn't on purpose. It's impossible to know all problems from all contests/online judges. And it seems that it is not so easy to google the statement of this problem.
I am not sure that it is easy — did not tried to google this one, already seen it on SPOJ before)
But now I tried to search for fibonacci updates array query problem and some other similar requests and both of these problems are at first page)
I wouldn't be so sure. Just keywords from the problem statement, plus where to look (I always add "online judge" when I'm looking for a problem without specific source competition).
Yes, you are right. I tried another search queries and failed to find this problem, but it is definitely not so hard to do this and authors should have do that.
Did anyone try to solve Div2 C using two pointers?
Is the contest unrated for Div.1??? The rating of Div.2 was updated, but Div.1 not.
It went well and there was no announcement, of course it's rated. It just takes a long time for some mysterious reason.
LOL, it's like this was a Div-2 only contest. :D
seriously, i guess it's just a small system issue. i'm sure ratings will get updated soon. :)
What asymptotics should be in Div2-D? I had O(pk) (I hope) and got TL. Now I wonder is it too bad or just Python?
Should be O(k logn + k logm)
Solution from editorial works in O(k * log(n) + k * log(m)); however, it is possible to do it in O(k * (n + m)) and fit into TL easily (7093794).
Upd. This solution is wrong (i described problem here). But you still can pass system tests with it)) Changing long into long long to fix overflow issues will make it correct, but with long long it does not fit into TL.
Is long long that much slower than int? Is Codeforces on 32bit machines?
Yes, it is ~2 times slower.
You may change
long si[12000],sj[120000]; into long long si[12000],sj[120000]; in my solution and it will work >2s.
i'm hoping that the ratings of Div-1 will be updated before the World Cup final starts.
i'm hoping that the ratings of Div-1 will not be updated
Why DIV2 C test 27 1 1 2 3 4 answer is 5 (not 4)?
change first 1 to a 0.
answer is (0 1 2 3 4) (i.e. make the change a1 = 0).
DZY очень нужна ваша помощь!Поможем, нам не сложно))
Раунд окончен. Поздравляем победителей.
Див. 1:
1. vepifanov
2. subscriber
3. RAVEman
Див. 2:
1. llllllllllll
2. geniucos
А див. 1 правильно рейтинг пересчитали? а то у меня до контеста было 1701, я занял 457 место из 701 и рейтинг упал на 2))
Can someone tell me why this submission is giving Runtime Error?
Something isn't right here...
Aah..OK.I failed to notice this during contest :(
its very bad contest
Хмм... Как быстро найдёте разницу? :)
7094727 7094719
Поставь 3 корня вместо двух, будет еще быстрее:)
И выбрось %MOD (замени на вычитание), тогда вообще в 2 секунды можно вжать.
CodeForces обижается на
PPRE=(PPRE+ppre[i])%MODRound Stats
In question C. DZY Loves Sequences
Shouldn't the answer of (testcase #27) 5 1 1 2 3 4 be 4? Value of ai can never be less than 1.
Read the problem statement carefully ... It says change one number to any integer you want.
I don't see why we need all the complicated logic in the editorial for Fibonacci problem. We can simply precompute the first 300000 values linearly and store them in an array.