### rng_58's blog

By rng_58, 6 years ago, ,

Hello!

I'm Squirrel Liss. I became the hero of today's contest. The writers of the contest are snuke, hogloid, DEGwer, and rng_58. I'd like to thank Gerald for helping preparation, Delinur for translation, and MikeMirzayanov for the Codeforces system. The point values will be standard: 500-1000-1500-2000-2500 for both divisions.

Since 07:30 PM MSK is late here, the contest will be moved to 05:00 PM MSK. Please check the schedule in your time zone in timeanddate.com: http://timeanddate.com/worldclock/fixedtime.html?iso=20130120T22&p1=248&ah=2

UPD: Announced the detail of the contest.

The top five contestants in div1 were:

And in div2:

Congratulations!

Also congratulations al13n and Komaki for solving div1 E problem.

The authors were

•
• +446
•

 » 6 years ago, # | ← Rev. 2 →   +13 If you could do it for 3:00 PM MSK, would be better I think :)
 » 6 years ago, # |   +31 How powerful the problem setter group it is ... I guess the problem set will be extremely hard ...
 » 6 years ago, # |   +34 I smell a lot of math.
 » 6 years ago, # |   +76 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 :).
 » 6 years ago, # |   +21 Looking at the problem writers, the problems must be very interesting. I definitely will participate :)
 » 6 years ago, # |   -37 too early announcement!!
•  » » 6 years ago, # ^ |   +22 I think it was because of the change in schedule.
•  » » 6 years ago, # ^ |   0 It is not announcement. Announcement will be later.
 » 6 years ago, # |   +7 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...).
•  » » 6 years ago, # ^ |   +15 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
•  » » » 6 years ago, # ^ |   +7 It's good idea,Thanks.
 » 6 years ago, # |   -36 I cant able to slove more than a problem in contest... Anyone help me plz
•  » » 6 years ago, # ^ |   +7 do you often practice out of contests times?
•  » » » 6 years ago, # ^ |   +1 his submission history shows he practice a lot. http://codeforces.com/submissions/hariprasath
•  » » » » 6 years ago, # ^ |   0 A man obsessed with being on tophttp://codeforces.com/problemset/standings
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 He solves problems very VERY fast! And he has 1st place in Round-146 Div-1
•  » » » » » 6 years ago, # ^ |   -9 We are talking about hariprasath not rng_58
•  » » » » » 6 years ago, # ^ |   +26 wow...He solve problems E in just 2 minutes .... It is so godlike...
•  » » » » » » 6 years ago, # ^ |   +45 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…
•  » » » » 6 years ago, # ^ |   +12 I don't think so.his submission history shows that he copy/paste solutions a lot
•  » » » » » 6 years ago, # ^ |   -30 Actually hARRAY is my original hadle... Check that out and give advice dudes!
•  » » » » » 6 years ago, # ^ |   -26 Without knowing rules and rating i started this account :(
•  » » » » » 6 years ago, # ^ |   -8 solved 2 problems in a c0ntest!!! thanks to kingofnumbers
•  » » » » » » 6 years ago, # ^ |   0 Congratulations :)
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   -70 and what about money?:Dare they gonna split it?:D
 » 6 years ago, # |   +23 looking forward to a topcoder admin's problem. :) I won't miss it.
•  » » 6 years ago, # ^ |   -20 admin? you sure?which one?
•  » » » 6 years ago, # ^ |   +10 I think he meant rng_58 . Though I am not sure admin would be the right word.
 » 6 years ago, # |   -10 i am not able to register..can u please help be understanding why is this so..
•  » » 6 years ago, # ^ |   0 There are 8 more hours(from now) until registration is made possible.
 » 6 years ago, # |   -29 Комментарий удален администрацией по причине несоблюдения правил сайта.
 » 6 years ago, # |   +7 This will be the contest with the best problem set and the best plot :) . good luck & have fun !
 » 6 years ago, # |   0 Хочется, чтобы Белочка Лисска почаще составляла контесты! Всем удачных взломов и повышения рейтинга!
 » 6 years ago, # |   +20 And one hour after the end of the contest, January cook-off. This will be an intense, and of course, an awesome day...
 » 6 years ago, # | ← Rev. 2 →   +5 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 ^_^
 » 6 years ago, # |   -7 Люди удачи!!!!
 » 6 years ago, # | ← Rev. 2 →   +7 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!!
 » 6 years ago, # |   +2 good luck everybody!!! Have very good solutions :)
 » 6 years ago, # |   -34 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
 » 6 years ago, # | ← Rev. 2 →   -42 хорошо сказал он не красиво поступает этот GERALD
 » 6 years ago, # |   +40 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?)...
•  » » 6 years ago, # ^ |   +23 because the contest begin at 9:00 pm in china...
•  » » » 6 years ago, # ^ |   +12 And today is Sunday, and time of session in uni.
 » 6 years ago, # |   +31 it seem that the writers are very "meng" looking forward to
•  » » 6 years ago, # ^ |   +37 it's called moe~~~ so cute :)
•  » » » 6 years ago, # ^ |   0 ? what does "meng" mean? its mean is like moe?
•  » » » » 6 years ago, # ^ |   0 "meng" is the pronunciation of the Chinese character "萌", while "moe" is written as "萌え" in Japanese.
•  » » » » » 6 years ago, # ^ |   0 thanks,I got it ^_^
 » 6 years ago, # |   -7 502 bad gateway !
 » 6 years ago, # |   +9 could not catch the registration... what a pity!
 » 6 years ago, # |   +4 Шарик снова с нами на раунд
 » 6 years ago, # | ← Rev. 3 →   +1 poor statement of problem c in div 2..:(
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 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.
 » 6 years ago, # |   0 Half the time the room is down.
 » 6 years ago, # | ← Rev. 2 →   +4 Very slow.Unable to hack. disappointed.
 » 6 years ago, # |   0 I hv a bad feeling that 80% of solutions for div2 A will fail :D
 » 6 years ago, # |   +6 Hello, Div2 !
•  » » 6 years ago, # ^ |   +3 :D
 » 6 years ago, # |   0 How to solve D?
•  » » 6 years ago, # ^ |   +23 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.
 » 6 years ago, # |   +77 Very nice problems, thank you!Of A, B, C, D (haven't had time to try E) I especially liked D.
 » 6 years ago, # |   +4 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?
 » 6 years ago, # |   +19 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 ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 I did in this way: 1) put cursor at lowest visible textbox 2) press tab 3) press enter
•  » » » 6 years ago, # ^ |   0 Thank you, I'll try this next time :) but don't you think that this bug should be fixed ?
•  » » » » 6 years ago, # ^ |   +4 I think so, but I meet this bug last 4-5 rounds :)
 » 6 years ago, # |   +12 Very cool D! I didn't solve it (I know my bug), but it is real cool!
•  » » 6 years ago, # ^ |   +3 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...
•  » » » 6 years ago, # ^ |   -8 tat?
•  » » » » 6 years ago, # ^ |   0 I think "TAT" means crying..
 » 6 years ago, # |   +8 AWESOME PROBLEMS . Too bad i got hacked twice, but ... Nice, nice problems, though . Congrats !
 » 6 years ago, # |   0 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.
 » 6 years ago, # |   0 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. :(
 » 6 years ago, # |   +11 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 recurrenceLet 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
•  » » 6 years ago, # ^ |   +14 You got a correct idea but implemented some ... eh... unnecessary thing? (and it's wrong)Try this case: 1 1 -2 1 0 -5 
•  » » » 6 years ago, # ^ |   0 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
 » 6 years ago, # |   +31 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?
•  » » 6 years ago, # ^ |   +19 It's also interesting that all problems in DIV-I have a constraints at least N>=10^5. Which is quite understandable considering for TopCoder limit are rather small ;)
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +6 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.
 » 6 years ago, # |   +2 Really loved the tasks, short statements and interesting tasks allowing many hacks and cool solutions, without much math required, awesome competition :)
 » 6 years ago, # |   +16 nice problems. even the writer are Japaneses, the problems are not too mathy.I like the problems. thanks writers. :)
 » 6 years ago, # | ← Rev. 2 →   +30 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.
 » 6 years ago, # |   -7 Spent half of the contest solving C when ball order doesn't matter...
 » 6 years ago, # |   +27 Very slow system testing:(
 » 6 years ago, # |   0 O(n) solution for C div2 fall with TL (C#)WTF???????http://codeforces.ru/contest/265/submission/2965647
•  » » 6 years ago, # ^ |   0 I suppose that .Length is not O(1) and is O(N), hence your solution is O(N^2) due to that fact only.
•  » » » 6 years ago, # ^ |   +9 You're wrong, length is a class string property, and work in O(1)..
•  » » » » 6 years ago, # ^ |   +3 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: string ans = ""; for (int i = 0; i < s.Length; i++) { ans += res[i].ToString() + "\n"; if ((i % 100) == 0) { Console.Write(ans); ans = ""; } } Console.Write(ans); it ran a lot faster on maximum test case.
•  » » » » » 6 years ago, # ^ |   -8 Please compare these two solutions. http://codeforces.ru/contest/197/submission/2295950 http://codeforces.ru/contest/197/submission/2295955
•  » » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Yes.. Sorry. It isn't a good example. But.. This's really unbelievable. Please, look at these links. http://codeforces.ru/contest/265/submission/2973455 http://codeforces.ru/contest/265/submission/2973385
•  » » » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » » » » 6 years ago, # ^ |   0 It seems to me that tests and limits for C should be more accurate. The result should not depend on checker pass.
•  » » » » » 6 years ago, # ^ |   0 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(((((
 » 6 years ago, # | ← Rev. 3 →   +2 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.
•  » » 6 years ago, # ^ |   0 I can open it
•  » » » 6 years ago, # ^ |   0 I can open it too. Can you open it by clicking on it?
•  » » » » 6 years ago, # ^ |   0 I could open it with no different from opening other comments.
 » 6 years ago, # | ← Rev. 2 →   +52 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.
•  » » 6 years ago, # ^ |   +4 Excessive modesty from a red user.
•  » » » 6 years ago, # ^ |   +46 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 :).
•  » » » » 6 years ago, # ^ |   +4 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.
•  » » » » » 6 years ago, # ^ |   0 not always :)
 » 6 years ago, # |   +3 i solve C by chance :)))i just saw the examples and i found a model =))
 » 6 years ago, # |   +8 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.
•  » » 6 years ago, # ^ |   0 You can always upload a generator.
•  » » » 6 years ago, # ^ |   0 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
•  » » » » 6 years ago, # ^ | ← Rev. 4 →   0 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.
 » 6 years ago, # |   0 In problem C O(n) is giving TLE.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 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
•  » » » 6 years ago, # ^ |   0 ok i get it
•  » » » 6 years ago, # ^ |   -13 No you're wrong man.inserting in a vector is O(1) amortized, which means N number of insertion takes O(N).
•  » » » » 6 years ago, # ^ |   +3 Insertions??? To any place, using res.insert(res.begin()+pos,i+2);??? Maybe you mean push_back-s are O(1) amortized?..If you really mean insert-s are O(1) amortized, please explain how can it be so.
•  » » » » 6 years ago, # ^ |   0 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).
•  » » 6 years ago, # ^ |   0 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).
 » 6 years ago, # |   0 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
•  » » 6 years ago, # ^ |   +2 |s|<=10^6 and for this you need tu calculate 1/2^(10^6) and there precision will lost.
•  » » » 6 years ago, # ^ |   0 why 1/2^(10^6)??? the order is linear and ..... sorry I think i haven't gotten what u mean :(
•  » » » » 6 years ago, # ^ |   0 Oh, I've gotten!what a bad mistake!:(( So, in this case, what is the algorithm to solve this??
•  » » » » 6 years ago, # ^ |   0 1/(2^(10^6)) isn't in float or double
 » 6 years ago, # |   +5 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.
 » 6 years ago, # | ← Rev. 2 →   +3 My first contest in the first division and I solved two problems. Looks pretty nice to me :).
 » 6 years ago, # |   +8 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.
•  » » 6 years ago, # ^ |   +2 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.
•  » » » 6 years ago, # ^ |   +16 Thanks a lot eduardische :)
 » 6 years ago, # |   +62 A great revenge :) Separately, thx to DEGwer for the div.2 C problem — very interesting.
 » 6 years ago, # |   +3 Лично Мне понравилось всё только тестировалось долго(
 » 6 years ago, # |   +5 Why ivan.metelsky's A got TLE?
•  » » 6 years ago, # ^ |   -28 Задача С ужасная: идеи никакой не нужно и как-то несерьёзно, что TL зависит от оператора вывода и компилятора.
•  » » » 6 years ago, # ^ |   -8 Почему же, идея в том, что нельзя было вычислять середины отрезков и складывать в массив пары <координата, номер камня>, потому что длина строки — миллион. И тл там больше зависит от работы контейнеров stl, по-моему.
•  » » » » 6 years ago, # ^ |   -16 нет, один и тот же код на gnu c++ заходит а на ms c++ tlится. это ненормально, по-моему.
•  » » » » » 6 years ago, # ^ |   +3 Как раз скорее разница в контейнерах у них. На одной из олимпиад у нашей команды не зашло решение на gcc, но проходило (как впоследствии выяснилось) на msvc. Просто нужно понять — компиляторы разные. И нужно знать их особенности.
•  » » » » » 6 years ago, # ^ |   +17 ItsLastDay выше всё сказал абсолютно правильно. Было бы странно, если бы любой код под обеими компиляторами работал одинаково, не так ли? Например, знаете ли вы, что в g++ по умолчанию вектор при реаллокации увеличивается в два раза, а в msvc++ — в полтора?
•  » » » » 6 years ago, # ^ |   -16 да елки палки! была уже статья про использование stl, статистика и все такое. Там наглядно показано, что stl- это хорошо, ничего там не тормозит. А если кто не использует reserve/resize — так это их проблемы. а задача реально безидейная, а AC зависит от выбора компиля. Сам на это наткнулся.
•  » » » » » 6 years ago, # ^ |   0 А что за статья? Про вектор на сколько я помню было в комментах много обсуждений, что хорошо, а что нет. И что их все-таки лучше не юзать, когда есть возможность.
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   +21 AC зависит от выбора методов ввода/вывода, уж сколько раз твердили миру, что cin/cout == тормоза, а endl — еще дополнительные тормоза, т.к. он флашит поток. Может, для кого-то будет уроком.P.S. Твое решение с '\n' вместо endl: 1078 мс (2974799) и с быстрым вводом-выводом: 437 мс (2974853)
•  » » » » » » 6 years ago, # ^ |   +4 И это по твоему идея данной задачи?))))) Я кончено понимаю, что накосячил, выбрав endl, cout и т.п.... Просто если опустить все эти мелочи по сути, то задача простецкая. А оптимайз высосан из пальца. ИМХОP.S. по поводу топика погорячился. Там рассказывалось про stl'евские пары.
•  » » » » » » » 6 years ago, # ^ |   +5 Для A абсолютно нормальная задача. А то, что кто-то не знает о скорости ввода/вывода — ну что ж, вот оно, самое время узнать
•  » » » » » » » » 6 years ago, # ^ |   0 Это была С))
•  » » » » » » » » 6 years ago, # ^ |   0 Тут дело скорее в компиляторе, а не в скорости ввода/вывода в C++ в целом. На GNU C++ нужно было постараться, чтобы получить TL по этой задаче просто из-за того, что неправильный способ вывода выбрал.По крайней мере моя посылка с cin/cout, endl и без выключения синхронизации с stdio уверенно заходит.
•  » » » » » » » 6 years ago, # ^ |   0 Не очень понятна точка зрения. Обжечься на таком же моменте с более сложной задачей тебе было бы менее обидно? o_O
•  » » » » » » » 6 years ago, # ^ |   0 Ладно, предлагаю на этом закончить спор. В конце концов каждый останется при своем. А по задаче — на то воля автора.
•  » » 6 years ago, # ^ |   0 I have experienced the same problem -TLE in my java solution. We should use StringBuilder instead of println all numbers individually
 » 6 years ago, # |   0 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
•  » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ |   +8 if(i == strlen(s)) — probably, strlen is computing on every step, which results in quadratic time.
•  » » » 6 years ago, # ^ |   +1 Yes, that was the issue :-/ Feel so stupid. :|
 » 6 years ago, # |   0 Someone explain me please, how to solve the problem "Good Sequences" (D div2 and B div1)?
•  » » 6 years ago, # ^ | ← Rev. 4 →   +4 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.
•  » » » 6 years ago, # ^ |   +3 In fact it can be done in O(nlogn) time using a preprocessing with the sieve of Eratosthenes.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -8 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.
•  » » » » » 6 years ago, # ^ |   +3 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).
•  » » » » » » 6 years ago, # ^ |   0 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)).
 » 6 years ago, # |   0 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. громоздкое) :( )
•  » » 6 years ago, # ^ |   +3 There is int overflow in 3 places in your code. values[i]*a and values[i]*b aren't necessarily fit into int.
•  » » » 6 years ago, # ^ |   0 а что неправильно в этом решении задачи Д 2-ого дива? http://codeforces.ru/contest/265/submission/2972639
•  » » » » 6 years ago, # ^ |   +6 You can try to write a naive solution and use it to find some small test case on which your solution fails.
 » 6 years ago, # |   0 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?
•  » » 6 years ago, # ^ |   +6 Compilers are different. This solution gets TLE on MS C++ and AC on GNU
•  » » » 6 years ago, # ^ |   +2 I didn't notice that. Thank you very much.
 » 6 years ago, # |   +4 Blue again :) ! I really liked the problems :) ! And the plot was very cool too ! Thanks a lot for this great contest :)!
 » 6 years ago, # |   0 Div2-CCan't make it pass by using Ruby or Scala. Very easy to pass in Java. :( Looks like Ruby or Scala are not encouraged.
 » 6 years ago, # |   +2 Anyone knows why scala is so slow on codeforces? It's supposed to be a fast language.
 » 6 years ago, # |   +8 I wrote editorial slides about the problems Div1 A and Div1 B(Div2 C and Div2 D). (But in Japanese)I will write editorial in English soon.
 » 6 years ago, # |   0 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...
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 Nice squirrel!!
 » 6 years ago, # | ← Rev. 2 →   0 This one of the best programming community I ever seen. While going through each archive contests, I am getting a plenty of new ideas. Hat's off to the Authors and Contestants.
 » 4 years ago, # |   0 In problem B (Div 2), with this test case: 31 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!
 » 2 months ago, # |   0 I want to provide a data to the B. Good Sequences, such as input: 5 1 1 1 1 1 output: 1I think the data maybe to hack anything