Привет!
Я белочка Лисска. Я буду главным действующим героем сегодняшнего соревнования. Авторами соревнования являются snuke, hogloid, DEGwer, и rng_58. Я хочу поблагодарить Gerald за помощь в подготовке соревнования, Delinur за перевод условий, и MikeMirzayanov за платформу Codeforces. Распределение баллов по задачам будет стандартным: 500-1000-1500-2000-2500, в обоих дивизионах.
Я столкнусь с множеством трудностей, связанных с камнями, орешками и последовательностями... Пожалуйста, помогите мне!
Так как 19:30 MSK очень позднее время для нас (речь идет о времени в Японии), раунд будет перенесен на 17:00 MSK. Вы можете посмотреть время начала соревнования для Вашего часового пояса на timeanddate.com: http://timeanddate.com/worldclock/fixedtime.html?iso=20130120T22&p1=248&ah=2
UPD: Опубликованы все другие детали соревнования.
Это перевод оригинального поста автора с английского языка. Комментарии на английском приветствуются.
Top 5 участников в div1:
- 1: Petr
- 2: AleX
- 3: scott_wu
- 4: Zhukov_Dmitry
- 5: al13n
В div2:
- 1: kesongyu
- 2: Moor
- 3: Qwaz
- 4: tsunayoshi
- 5: step5
Поздравляю!
Также наши поздравления участникам al13n и Komaki, которые решили задачу E в первом дивизионе.
Авторы задач:
- D2 A: rng_58
- D2 B: snuke
- D1 A/D2 C: DEGwer
- D1 B/D2 D: DEGwer
- D1 C/D2 E: hogloid
- D1 D: rng_58
- D1 E: snuke
Разбор будет опубликован завтра (возможно, частично сегодня).
Ого, анонс 162 раунда появился даже раньше, чем анонс 161го раунда!
Это не анонс
Так скажите пожалуйста, в чём отличие этого поста от анонса?
Авторы заранее предупредили о переносе времени начала контеста.
Если я не так понял, прошу извинить.
We will announce the details of the contest later.
Таки это анонс Codeforces Round #162.
If you could do it for 3:00 PM MSK, would be better I think :)
How powerful the problem setter group it is ... I guess the problem set will be extremely hard ...
I smell a lot of math.
WOW...I guess it would be a VERY hard contest...And I'm really looking forward to rng_58's problems :) so I'll take part for sure :).
Looking at the problem writers, the problems must be very interesting. I definitely will participate :)
too early announcement!!
I think it was because of the change in schedule.
It is not announcement. Announcement will be later.
После этого я, читая пост, уже в душе надеялся, что последней строки не будет.
Не исключено, что русский текст он все-таки сам писал)
Слова "речь идет" употреблены довольно необычно — не думаю, что много русских так построили бы фразу, а вместо "для вашего часового пояса" надо все-таки "в вашем часовом поясе".
А я кажется догадываюсь кто это писал :-)
This contest will be very hard...but it will be very good(I want to participate in Div1,but I will not be able to participate because my rating became less than 1700...).
div2 Round #161 will take place before div1 #162 try to become candidate master then you will be able to participate in div1 in round #162
It's good idea,Thanks.
I cant able to slove more than a problem in contest... Anyone help me plz
do you often practice out of contests times?
his submission history shows he practice a lot. http://mirror.codeforces.com/submissions/hariprasath
A man obsessed with being on top
http://mirror.codeforces.com/problemset/standings
He solves problems very VERY fast!
And he has 1st place in Round-146 Div-1
We are talking about hariprasath not rng_58
wow...He solve problems E in just 2 minutes .... It is so godlike...
I remember removing a few people from the top of the standings of one contest that I have manager access to. They start a virtual contest and submit other participants' solutions immediately. I still can't understand why do they do it…
I don't think so.
his submission history shows that he copy/paste solutions a lot
solved 2 problems in a c0ntest!!! thanks to kingofnumbers
Congratulations :)
Practice is the only key to improve...Try to solve the problems after the contests and read the editorials if you face any problem. Also if editorials are not enough for you to understand then you can take help of the blogs.
Япония, Японией, но очень хорошо, что контест сдвинули. Он перекрывался с CodeChef Cook-Off (20.01 20-00), который традиционно проводится в предпоследнее воскресенье каждого месяца в одно и то же время.
Тут, по-моему мнению, надо всем время выбирать уважительно и аккуратно: не так много сайтов, где регулярно проводятся контесты с оригинальными задачами хороших авторов. Раз, два, три...
Вероятно, это было одной из причин.
and what about money?:D
are they gonna split it?:D
Было бы хорошо, если все контесты начинались в 17:00 по Москве. В крайнем случае в 18:00. А то для нас в глубокой Сибири контест обычно начинается в пол первого ночи, потом ты его 2 часа решаешь, и потом еще 2 часа не можешь заснуть анализируя свои ошибки ...
Я думаю, тем, кто живёт по московскому времени и работает полный рабочий день, такое предложение не понравится.
Тогда уж можно было бы предложить проводить разные раундов в разное время, чтобы всем попытаться угодить
привыкай. я уже привык вставать в 2:30 ночи
looking forward to a topcoder admin's problem. :) I won't miss it.
admin? you sure?
which one?
I think he meant rng_58 . Though I am not sure admin would be the right word.
Надеюсь задачи будут интересными, а раунд пройдет без багов!
This will be the contest with the best problem set and the best plot :) . good luck & have fun !
Хочется, чтобы Белочка Лисска почаще составляла контесты! Всем удачных взломов и повышения рейтинга!
А вот теперь этот комментарий актуален.
And one hour after the end of the contest, January cook-off. This will be an intense, and of course, an awesome day...
Where is the picture of squirrel? I can't see it:(
UPD. Done. As I understand from hogloid's profile picture he is the squirrel we need to help to ^_^
I guess that there are many kinds of animals in the statement because they are Japanese writers. I like wolves!! So I wish the problem set would contain problem about wolf!!
good luck everybody!!! Have very good solutions :)
Необычный анонс
salamalekum vsem jelaiu vsem uda4i nadeius etot tur ne jeral'd sostavel ato kapec potom ewo sam budet pesat' vawe krasava budet etot JEROL'D
It seems that over 700 people will participate this contest (because of its good timing?). It will be the div. 1 contest with the most people participating recently (or up to now?)...
because the contest begin at 9:00 pm in china...
And today is Sunday, and time of session in uni.
it seem that the writers are very "meng" looking forward to
it's called moe~~~ so cute :)
? what does "meng" mean? its mean is like moe?
"meng" is the pronunciation of the Chinese character "萌", while "moe" is written as "萌え" in Japanese.
thanks,I got it ^_^
502 bad gateway !
could not catch the registration... what a pity!
Шарик снова с нами на раунд
poor statement of problem c in div 2..:(
What's wrong with the statement? Yes, it might be hard to imagine it, but try drawing it — that should make it clearer! Edit: Besides, apparently more than 900 people didn't have a problem with it.
Very slow.Unable to hack. disappointed.
Hello, Div2 !
:D
How to solve D?
I drew a 2D matrix and looked at all unreachable cells (you can either go to (x+1,y)/(x,y+1) or to (x+1,y+1) only). Then you have pretty beautiful answer.
Very nice problems, thank you!
Of A, B, C, D (haven't had time to try E) I especially liked D.
why i always receive a message from this online system that 'Can't process your hack, try again' when everytime i try to upload a file to hack. Anyone could help me about this question?
I couldn't make any hack today , whenever I try to drag the hack screen it select the text and it's undraggable, whenever I scroll down , the screen scrolls down with me , in the previous contests the hack screen was draggable i don't know why it's undraggable today , did anyone else face the same problem ?
I did in this way: 1) put cursor at lowest visible textbox 2) press tab 3) press enter
Thank you, I'll try this next time :) but don't you think that this bug should be fixed ?
I think so, but I meet this bug last 4-5 rounds :)
Very cool D! I didn't solve it (I know my bug), but it is real cool!
TAT... Just one minute or two, I could have finished my D... Being troubled with C for TOO long... TAT... Perhaps because I have not written any code for a long time...
tat?
I think "TAT" means crying..
AWESOME PROBLEMS . Too bad i got hacked twice, but ... Nice, nice problems, though . Congrats !
I get Invalid input for problem B hacking with 100000 1 2 ... 100000 input, but 99999 1 2 ... 99999 was OK once, on the second try it gives Invalid input too. It's weird.
It is really shameful to taking care of special cases in wrong way. eg. for Div 2 B , in case of only 1 tree , answer should be height + 1 , but I output height. :(
Hi,
Can I have some help in solving C? I keep getting WA on pretest 8 and I'm not sure why.
My algorithm is that we use the following DP recurrence
Let f(i) = best value we can get if we choose a subsequence with last ball being the i^th ball.
Then f(i) = max(f(j) + A * value[i] if color[j] == color[i], f(j) + B * value[i] otherwise and if i is the first ball)
To speed up this recurrence, for each color I store the top value gotten so far, so that I can perform the "same ball" part in constant time. I also store the top two distinct colours with best f value, so that I can do the "different ball" part in constant time. In total it is O(QN). But it seems that I have some bug somewhere :(. Please help me out:
Source Code: http://pastebin.com/fp9Uip1P
You got a correct idea but implemented some ... eh... unnecessary thing? (and it's wrong)
Try this case:
Can you take a look at my solution and tell me what am I doing wrong. I've been staring at my code for some time now and can't find the error. 2974130
The problems are interesting as usual. (Especially problem D, but I think the pretest is evil, thus we can get points easily by blind hack)
It's also interesting that all problems in DIV-I have a constraints at least N>=10^5.
By the way, why Liss is looking at grapes(but not nuts) in the picture?
Which is quite understandable considering for TopCoder limit are rather small ;)
Yes, I agree.
And before the contest I guessed that there might be some constructive problems (e.g.: http://www.codeforces.com/problemset/problem/198/D): they can't be used in TopCoder either.
Really loved the tasks, short statements and interesting tasks allowing many hacks and cool solutions, without much math required, awesome competition :)
nice problems. even the writer are Japaneses, the problems are not too mathy.
I like the problems. thanks writers. :)
I hadn't a time to solve E, but I've just noticed that hi, xi ≤ 10 (after half-hour thinking). IMHO, you'd better state this very important constraints in description, and not in the 'input' section next time.
Spent half of the contest solving C when ball order doesn't matter...
Да уж. Взломы — дело сильно рискованное, когда взлом рассчитан на TLE. Увидел у чувака решение С, где он вводит через cin миллион чисел, забивает их в массив пар, потом этот миллион пар сортирует STL-евским sort'ом, и выводит миллион чисел через cout. Дал ему тест на миллион буков 'r'. чтоб изначально массив пар был отсортирован по убыванию, результат — 1968 мс. Чуть стол не опрокинул от злости..
Ух ты. Может быть, в начале решения была строчка
sync_with_stdio(false)?Нет, так и должно быть — я специально вывел на CF-овских серверах миллион чисел с cout и endl, 0,8c (тоже хотел взломать любителя cin/cout).
Из-за чего же оно тогда упало если не из-за cin cout http://mirror.codeforces.com/contest/265/submission/2968162
У меня пока других гипотез нет. Если причина действительно в cin cout, то это жёстко.
Возможно, на вижаке cout тормозит еще больше, я тестил для gnu. Скорее всего причина TL в этом.
Переделал на printf и всё зашло http://www.codeforces.ru/contest/264/submission/2973117
С одной стороны сам дурак, что сразу не подумал про printf
А с другой стороны как-то несерьёзно, что TL зависит от оператора вывода и компилятора.
Вообще эта задача клон http://acm.sgu.ru/problem.php?contest=0&problem=397 с одного из четвертьфиналов.
Very slow system testing:(
O(n) solution for C div2 fall with TL (C#)
WTF???????
http://mirror.codeforces.com/contest/265/submission/2965647
I suppose that .Length is not O(1) and is O(N), hence your solution is O(N^2) due to that fact only.
You're wrong, length is a class string property, and work in O(1)..
Yes, indeed. Well that was only an assumption.
The only other thing I can suppose is that the slowest thing of it all is outputting 10^6 numbers. Maybe Console.Writeline does a lot of overhead (specifically on newlines), which slows it down. Indeed, when I changed the output in your code to:
it ran a lot faster on maximum test case.
Please compare these two solutions. http://mirror.codeforces.com/contest/197/submission/2295950 http://mirror.codeforces.com/contest/197/submission/2295955
So what do you want me to do? What I used above is a small buffer to avoid 10^6 calls of Write/Writeline with newlines at some reasonable cost of string operations. Note that I haven't made one big resulting string (as in your two solutions), as it would give TLE anyway.
Yes.. Sorry. It isn't a good example. But.. This's really unbelievable. Please, look at these links. http://mirror.codeforces.com/contest/265/submission/2973455 http://mirror.codeforces.com/contest/265/submission/2973385
Actually, it's pretty believable. The time of accepted solution is exactly 2000ms, and since the same program can run slightly different time every run, it can easily either pass or fail when it's at the borderline.
It seems to me that tests and limits for C should be more accurate. The result should not depend on checker pass.
I've just wrote Console.Write(res[i] + "\n");
instead of
Console.WriteLine(res[i]);
and got AC in 1406 ms...
I think, that contestmakers should much carefully testing authors solutions for different languages, and write in condition about features of input and output .... (i.e. it would be better to use printf instead of cout and so on)
I've lost a lot of rating, and contest made me feel very disappointed(((((
норм контест был
Offtopic: am I the only one who can't click on the link above in cgy4ever's comment? Firefox 18.0.1, Windows 7 x64 En.
UPD: it's fixed now.
I can open it
I can open it too. Can you open it by clicking on it?
I could open it with no different from opening other comments.
The problem D is really interesting...but I am too stupid to figure it out... I just feel like that I lack of cleverness to solve such kind of problem which needs idea (crying)...
Anyway it's a good contest, maybe you could reduce the amount of big test in problems to reduce the running time.
Excessive modesty from a red user.
I don't think I deserve that rank and rating... I am just that type of programmer who just solve a lot of problems so if I see a similar problem I can solve it quickly. But if I meet a problem which is not that standard, I just, well, kind of feel like that I'm indeed a noob .
You can see from my profiles that whenever I got a nice rank, the contest's problems are standard to some degree, if the contest require some deep thoughts about something, I always fail.
Anyway I know it's bad to think that negatively, I'll try to solve more problems of that kind to practice my brain :).
When you meet a new problem and start thinking that you're a noob, your creative thinking goes down as a consequence. It's a closed circle.
not always :)
i solve C by chance :)))
i just saw the examples and i found a model =))
What is the limit of characters in a hacking attempt ??
I try to hack the C div2 problem with a string of 10 ^ 5 'l' and 10 ^ 5 'r', ie "llll ... rrr ...." wanting to do a TLE but the result I get to send a string of size 10 ^ 4, and an attempt to hack wrong.
You can always upload a generator.
I code a separate program that wrote this string of size 10 ^ 6 simply copy and paste the output and send my hack. But I do not understand where it came from the string of size 16,000
The generator i've used today:
int main(){ for(int i=0;i<1000000;i++) { cout<<'l'; } puts(""); return 0; }
Just upload the source file.
Как решалась E div 2 / C div 1?
In problem C O(n) is giving TLE.
It's not O(n), couse "insert" in vector working O(n). So you insert O(n) times in O(n) cycle = O(n^2). Sorry for my english
ok i get it
No you're wrong man.
inserting in a vector is O(1) amortized, which means N number of insertion takes O(N).
Insertions??? To any place, using
res.insert(res.begin()+pos,i+2);??? Maybe you meanpush_back-s are O(1) amortized?..If you really mean insert-s are O(1) amortized, please explain how can it be so.
To your comment does not prevent people understand the principles of the STL, I will explain more precisely. Inserts the item at the end of the vector = O (1) (amortized). What happens under the hood when we insert in the middle or beginning of the vector? Suppose that the insertion occurs at position n. Then the elements from the position before the end of n is copied and transferred to the one to the right. Total O (n).
I have found many participants have this error ~~~~~ for (int i = 0; i < s.size(); ++i) ~~~~~ and I think the correct is ~~~~~ int len = s.size(); for (int i = 0; i < len; ++i) ~~~~~ you can find the reason.(forgive my poor English).
У человека на D( div2 ) , B( div1 ) : http://mirror.codeforces.com/contest/265/submission/2968498 прошло решение за квадрат.. Мда. На это и рассчитывали ?
In D( div2 ) submission : http://mirror.codeforces.com/contest/265/submission/2968498 with complexity O( n^2 ) was accepted. Is it normal ?
Edit: Wrong solution was accepted. Tests are bad.
Edit: у человека прошло не правильное решение. Тесты плохие.
Вы не правы. У него решение O(100*n)
Ну как квадрат. Некоторый хак вида "а давайте предположим, что расстояние между двумя последовательными числами в ответе будет небольшим". Если вспомнить, что сами элементы последовательности до 10^5, то даже можно понять, почему это должно работать.
edit: дальнейшее неверно Интуитивно умею объяснять как-то так. Пусть действительно интервал между двумя последовательными числами в ответе большой. Тогда почему мы не можем взять какие-то числа в этом интервале, ведь при большом N они расположены достаточно плотно в числовом ряде, а значит наверняка какое-нибудь из них будет иметь общий делитель и с предыдущим числом, и со следующим. Казалось бы, чтобы строго это доказать, достаточно просматривать последние
чисел.
Я не очень понял комментарий. Я понял тесты ужасно плохие, если даже не сделали 101 подряд идущих простых чисел..
Upd. mrNobody ниже привел конкретный пример, даже со 101 числом решение работать не будет
Ответ на этот тест 1 и указанное выше решение замечательно на нем отработает.
Видимо, имеется в виду что-то вроде 2 p1 p2 ... p100 100000, где pi — простые, не делящие 100000. Тогда ответ больше единицы, но, действительно, есть интервал в 100 простых между числами в ответе. Тогда мое соображение не работает, да. А вот
вместо 
уже должно быть достаточно.
Мда. Минусуют те, кто не умеют читать, или стадный рефлекс :\
Странное интуитивное объяснение.
Давайте возьмем первый тысячу простых чисел, а потом допишем к ним число, равное 2 * (какое-то большое простое). Тогда правильный ответ будет состоять из двух чисел (первого и последнего), но это решение его не найдет.
Да, вы правы, уже написал выше.
у меня свалилась С при сложности O(n). так и запланировано, что она валится из-за СТЛьного списка или cin/cout ?
Задача С (DIV 2) валилась из-за использования cout вместо printf. Это я еще могу понять, хотя все-таки это слишком. Но более того, при использовании cout она валится при компиляторе Miscrosoft Visual C++ 2010 и заходит при использовании GNU C++. Это издевательство или нет?
Это еще один повод дописать в шаблон собственные быстро работающие функции ввода и вывода.
все претензии к Microsoft
А у меня прошло и с cin, cout и с MS C++. 2963402
Так ты красный, у тебя должно проходить
Вообще у меня например точно такое же решение, изначально думал сдать квадрат и сделать несколько взломов, но ради интереса проверил на нескольких больших тестах и понял что это решение работает правильно. Сам до конца был уверен что решение упадёт, но составители тестов удивили.
I can't understand what is wrong with my algorithm in question C div 2 each time we push the value of "k" to a vector and calculate the new "k" and "d" and this runs forever..and finally we will sort the vector.but my problem has been hacked!!Can everyone help me with this? 2967715
|s|<=10^6 and for this you need tu calculate 1/2^(10^6) and there precision will lost.
why 1/2^(10^6)??? the order is linear and ..... sorry I think i haven't gotten what u mean :(
Oh, I've gotten!what a bad mistake!:(( So, in this case, what is the algorithm to solve this??
1/(2^(10^6)) isn't in float or double
What's wrong with system testing ? It took a single contest time. I just want to try my solution but I have to wait the systest that very long.
My first contest in the first division and I solved two problems. Looks pretty nice to me :).
Hi All,
I want to know how the solutions are hacked during the contest because I think the solutions of other candidates are not visible till the end of the contest.
You need to lock your submission on the overview page before you can see and hack other solutions. By locking them you won't be able to resubmit again, and your submission must pass pretests for you to be able to lock it.
Thanks a lot eduardische :)
A great revenge :)
Separately, thx to DEGwer for the div.2 C problem — very interesting.
Лично Мне понравилось всё только тестировалось долго(
Why ivan.metelsky's A got TLE?
Задача С ужасная: идеи никакой не нужно и как-то несерьёзно, что TL зависит от оператора вывода и компилятора.
Почему же, идея в том, что нельзя было вычислять середины отрезков и складывать в массив пары <координата, номер камня>, потому что длина строки — миллион. И тл там больше зависит от работы контейнеров stl, по-моему.
нет, один и тот же код на gnu c++ заходит а на ms c++ tlится. это ненормально, по-моему.
Как раз скорее разница в контейнерах у них. На одной из олимпиад у нашей команды не зашло решение на gcc, но проходило (как впоследствии выяснилось) на msvc. Просто нужно понять — компиляторы разные. И нужно знать их особенности.
ItsLastDay выше всё сказал абсолютно правильно. Было бы странно, если бы любой код под обеими компиляторами работал одинаково, не так ли? Например, знаете ли вы, что в g++ по умолчанию вектор при реаллокации увеличивается в два раза, а в msvc++ — в полтора?
да елки палки! была уже статья про использование stl, статистика и все такое. Там наглядно показано, что stl- это хорошо, ничего там не тормозит. А если кто не использует reserve/resize — так это их проблемы. а задача реально безидейная, а AC зависит от выбора компиля. Сам на это наткнулся.
А что за статья? Про вектор на сколько я помню было в комментах много обсуждений, что хорошо, а что нет. И что их все-таки лучше не юзать, когда есть возможность.
AC зависит от выбора методов ввода/вывода, уж сколько раз твердили миру, что cin/cout == тормоза, а endl — еще дополнительные тормоза, т.к. он флашит поток. Может, для кого-то будет уроком.
P.S. Твое решение с
'\n'вместоendl: 1078 мс (2974799) и с быстрым вводом-выводом: 437 мс (2974853)И это по твоему идея данной задачи?))))) Я кончено понимаю, что накосячил, выбрав endl, cout и т.п.... Просто если опустить все эти мелочи по сути, то задача простецкая. А оптимайз высосан из пальца. ИМХО
P.S. по поводу топика погорячился. Там рассказывалось про stl'евские пары.
Для A абсолютно нормальная задача. А то, что кто-то не знает о скорости ввода/вывода — ну что ж, вот оно, самое время узнать
Это была С))
Тут дело скорее в компиляторе, а не в скорости ввода/вывода в C++ в целом. На GNU C++ нужно было постараться, чтобы получить TL по этой задаче просто из-за того, что неправильный способ вывода выбрал.
По крайней мере моя посылка с cin/cout, endl и без выключения синхронизации с stdio уверенно заходит.
Не очень понятна точка зрения. Обжечься на таком же моменте с более сложной задачей тебе было бы менее обидно? o_O
Ладно, предлагаю на этом закончить спор. В конце концов каждый останется при своем. А по задаче — на то воля автора.
I have experienced the same problem -TLE in my java solution. We should use StringBuilder instead of println all numbers individually
In Div2 C i implemented a binary tree, and for the solution simply printed the inorder. This gave TLE . I'm not able to understand why
Probably because the task was made so a solution using most binary trees (which are generally efficient asymptotically, but slow in real time) would get TLE. The idea itself was incredibly simple (2 stacks), so the time limit was probably out of reach with a binary tree structure.
if(i == strlen(s)) — probably, strlen is computing on every step, which results in quadratic time.
Yes, that was the issue :-/ Feel so stupid. :|
Someone explain me please, how to solve the problem "Good Sequences" (D div2 and B div1)?
Let's compute d[x] — the length of the longest sequence with the last element (you don't need it's actual value) divisible by x.
Suppose you already have some sequences, and you have array d as the information about them. And what you want is to know what sequences can be extended if you add number r at the end of them. Those sequences must end on some value, which is divisible by some (> 1) divisor of r. So to update the answer you just iterate over all divisors of r (that can be done in sqrt(r) time).
Actually, you can ignore any non-prime divisors of r, however, that is not necessary.
In fact it can be done in O(nlogn) time using a preprocessing with the sieve of Eratosthenes.
Well, in fact, one can even put all needed primes into his/her source code. ;-)
UPD. ...and this will make his/her solution a bit faster disregarding the same asymptotic complexity.
But it doesn't change the complexity. In fact sieve works in O(nloglogn). But you must always check divisiors of r (and it takes O(logr) pessimistically). That's why the whole complexity is O(nlogn).
The sieve of Erathostenes can be optimized to O(r). Checking of prime divisors takes O(number of primes <= sqrt(r))=O(sqrt(r)/log(r)). (If r is a large prime or a multiple of 2 primes close to sqrt(r), for example.) But there are at most lg(r) distinct prime divisors (actually, even less — for the given constraint r <= 100000, it's at most 7 as opposed to ceil(lg(100000))=17). So that'd give a total complexity of at least O(n sqrt(r)/log(r)).
Sorry for stupid question, but can author/admin publish test #5 of Div.1 C?
Or, can somebody tell what is incorrect in 2974379? (Unfortunately, it's rather cumbersome (russ. громоздкое) :( )
There is int overflow in 3 places in your code.
values[i]*aandvalues[i]*baren't necessarily fit into int.а что неправильно в этом решении задачи Д 2-ого дива? http://mirror.codeforces.com/contest/265/submission/2972639
You can try to write a naive solution and use it to find some small test case on which your solution fails.
Could anyone help me? Something strange has happened.
My solution on A got TLE at the contest, but when I submitted the EXACT SAME code after the contest, it got accepted with the time of 717ms! (TLE:2964261 / AC:2974157) What happened?
Compilers are different. This solution gets TLE on MS C++ and AC on GNU
I didn't notice that. Thank you very much.
Blue again :) ! I really liked the problems :) ! And the plot was very cool too ! Thanks a lot for this great contest :)!
Можете помочь с WA 35 (Div1B/Div2D) 2975185
Ошибка здесь, нужно заменить
jнаcur/j.Большое спасибо!
Anyone knows why scala is so slow on codeforces? It's supposed to be a fast language.
I wrote editorial slides about the problems Div1 A and Div1 B(Div2 C and Div2 D). (But in Japanese)
http://www.slideshare.net/DEGwer/escape-from-stones-16092976 http://www.slideshare.net/DEGwer/good-sequences
I will write editorial in English soon.
Div 2 E,Can Someone explain why we need to put 2 overall max values + 1 color max values to change the state for eg. 2966487 why can't it be done in 1 overall max + 1 color max...
You need max in the same color and max in other color. So, if overall max is in this color you need another (second) max.
Объясните, пожалуйста, в чём ошибка в логике решения D(div2).
В конце ищу максимум, среди длин последовательностей и вывожу. Вот сам код(http://mirror.codeforces.com/contest/265/submission/2979570), ошибка возникает на 35-ом тесте:
Хотелось бы не услышать решение, а сказать, где моя идея неверно работает. Спасибо каждому, кто поможет.
проверь инициализацию массива del и чему равно a[0] — ты его читаеш.
Спасибо, отловил 1 баг. К слову, я не понимаю, почему она у меня не зарантаймилась, ведь я обращался к несуществуещему элементу массива. Баг был в том, что я забыл учитывать, что число, после деления на все простые делители( которые встречаются в это числе, до корня), может остаться не единичкой. Еще раз спасибо!
почитай про проверку выхода за границу массива ( в современных компиляторах паскаля это обычно отдельный флаг компиляции — видимо и у тебя локально и в настройках этого сервера этот флаг отключён).
да. слона я и не приметил 2*p число не попадало в цепочку p. для развличения и ... см мою последнию отсылку по этой задаче( на дорешнивании). кодегольфинг .
Когда ты раскладываешь число на простые делители, ты не учитываешь, что в конце, после всех делений, оно будет состоять из одного большого простого числа, большего чем корень исходного. Пример — 2 * 49999.
Да, спасибо! Именно в этом и был баг, я уже нашел его, но всё равно Благодарю!=)
Nice squirrel!!
In problem B (Div 2), with this test case:
3
1 10 1
The problem statement says that finding the minimal time to eat all nuts so the answer should be 16 (first tree -> third tree -> second tree), but the answer of tutorial is 24 (first -> second -> third). Or I don't understand this problem correctly ? Sorry for my bad English. Thanks!