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.

I will encounter many difficulties about stones, nuts, and sequences... Please help me!

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:

- 1: Petr
- 2: AleX
- 3: scott_wu
- 4: Zhukov_Dmitry
- 5: al13n

And in div2:

- 1: kesongyu
- 2: Moor
- 3: Qwaz
- 4: tsunayoshi
- 5: step5

Congratulations!

Also congratulations al13n and Komaki for solving div1 E problem.

The authors were

- 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

UPD: Tutorial was added here.

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://codeforces.com/submissions/hariprasath

A man obsessed with being on top

http://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

Actually hARRAY is my original hadle... Check that out and give advice dudes!

Without knowing rules and rating i started this account :(

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.

and what about money?:D

are they gonna split it?:D

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.

i am not able to register..can u please help be understanding why is this so..

There are 8 more hours(from now) until registration is made possible.

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

хорошо сказал он не красиво поступает этот GERALD

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.

Half the time the room is down.

Very slow.Unable to hack. disappointed.

I hv a bad feeling that 80% of solutions for div2 A will fail :D

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

h_{i},x_{i}≤ 10 (after half-hour thinking). IMHO, you'd better state this very important constraints in description, andnotin the 'input' section next time.Spent half of the contest solving C when ball order doesn't matter...

Very slow system testing:(

O(n) solution for C div2 fall with TL (C#)

WTF???????

http://codeforces.ru/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://codeforces.ru/contest/197/submission/2295950 http://codeforces.ru/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://codeforces.ru/contest/265/submission/2973455 http://codeforces.ru/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.

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 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.

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).

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

mustend 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]*a`

and`values[i]*b`

aren't necessarily fit into int.а что неправильно в этом решении задачи Д 2-ого дива? http://codeforces.ru/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 :)!

Div2-C

Can't make it pass by using Ruby or Scala. Very easy to pass in Java. :( Looks like Ruby or Scala are not encouraged.

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

othercolor. So, if overall max is in this color you need another (second) max.Nice squirrel!!

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.

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!

I want to provide a data to the B. Good Sequences, such as input: 5 1 1 1 1 1 output: 1

I think the data maybe to hack anything