Your last round was interesting and solvable ! I believe it will be easier than round 307 :)

just noticed round #280 is my first contest in code forces. Well, and after this round I am in Div-1, so when is the next round maybe i will be red :D

Happy to you as well.

Синим ещё куда не шло, главное голубым сегодня не стань :-)

а я думал что я тут слабый, всего-то фиолетовый, а тут люди синими мечтают стать

How many times have you written this in the announcment?

izi is love, izi is life

then u should attempt div 1 mate !!!

His profile pic is in Russian, but my interface is in English :)

Also the rating and contribution are different.

My guess would be 1. take a screenshot of your profile. 2. copy+paste 3/4th of the screenshot to the remaining 1/4th space by reducing its size. 3. Repeat 3-4 times till its possible to do this within the smaller window each time. But this is just my guess.

блиииин, забыл зарегатся(((((

better change your user to BornToBeLoser, it will suit you better

it's your second round be patient! :3

Especially, when you BornToBeWinner :)

Bro :(

codeforces everyday growing! Keep on!

5-10 seconds of the highest quality drama on every submit! (Jaws music on the background) :)

I'm gonna be captain obvious here in case there's someone that doesn't know — Div1 users make new accounts to win Div2.

Brute Force, Digit DP, Number Theory ( ok, this one is math ), Geometry and I am not sure about the last one since I couldn't solve it. It was somewhat balanced I guess.

А кто-нибудь решил её быстрее, чем за N^2logN?

Там 4 секунды... Я такое решение сам у себя пробовал на C# — чуть чуть не укладывалось (5-6 сек было), так что на плюсах должно было пройти.

переполнение инта, подозреваю

I think D has less geometry than it seems to have.

Yea, I realize now that my 308B is wrong ;_;

Same here, Don't understand why gcc pow function fails though ?

same problem ....faced twice on codeforces

For some reason codeforces, which uses mingw (i think) is giving a bad answer with pow. Ideone gave right answer for the same code of mine. I feel it should not have to approximate since pow(integer) would return an integer in double form, which would not need any truncation.

I know that feel bro.

Try powl someday or use pow with nearbyint ...

Нет. Давайте почитаем число плохих троек точек(точек, лежащих на одной прямой). Переберем одну из точек тройки и покидает в set направляющие векторов от этой точки до всех остальных. Пусть у нас x раз встретился некий вектор. Тогда уменьшим ответ на x(x-1)

Eval gets Tl, doesn't it?

Yes, I was a bit surprised my solutions passed on those problems. The TL for D and E should have been tighter.

check for w=3 and m =17

Try to debug . It gives WA for 4 11 Your output NO Correct YES; 11 + 4 + 1 = 16

no

I tried and got time limit error

I submitted O(N^3/6) and it passed the pretests.

UPD: My solution also passed system tests.

Depends. I've tried on C# — it was like 5-6 seconds. So probably C++ could pass.

I think O(n^3) is too slow, but we will see.

IT PASSED :D

my first time to solve problem D during contest :D

Should it pass? If yes, then why?

I used n^2logn and it took me long time and cost 1 submission. :(

O(n³)??? This is the first thing I thought and then I spent all the contest trying to optimize to O(n²_logn). Sad!!!

http://mirror.codeforces.com/contest/552/submission/11663481

http://mirror.codeforces.com/contest/552/submission/11663430

C++ VS Java

wait for the editorial

If m = 2, then solution always exist — it likes writing m in binary base.

If m >= 3, find the first value of n that w^(n-2)*(w-1) > m. With m = 3, n = 18 and as m goes greater, n goes smaller. So, an O(3^n) brute-forces (considering each scales to be on the same pan with the object, different pan with the object or outside the pan) with properly branch-bound should be fast enough to get AC.

The answer is "YES" if it is possible to add another number that only contains 0s and 1s (in base w) to m such that the resulting sum only contains 0s and 1s as well. Just use the algorithm for naive sum, if the sum at the current digit is w — 1 set carry = 1, if the sum at the current digit is 1 set carry = 0, if sum at the current digit is different than 0 return "NO" .

our m needs to satisfy m = a_100*(w^100)+ .... a_0*(w^0),where a_100..a_0 are -1,0,1 we just test if m satisfies this

http://mirror.codeforces.com/contest/552/submission/11642323

Write m in base w. let b[i] be the i'th least significant number in the representation m in base w.

Loop over m (in base w) from right to left (from least significant to most significant).

Then if b[i] is 1, we can match it using (w^i). if b[i] is w - 1 then we can add w^i to the balance side of m. Then the representation of m becomes such that b[i] = 0 and b[i + 1] = b[i + 1]+1. so we increase b[i + 1] by 1.

Notice this could lead to have b[i + 1] equals to w in this case we should repeat the last case on b[i + 1] (i.e increase b[i + 2] by 1 and make b[i + 1] = 0).

the last case if b[i] > 1 and b[i] != w — 1 and b[i] != w we cannot represent m.

In contest I did not handle case where b[i] = w. But when i did (after contest) the solution passed all the cases) 11654584

My solution was not brute force. You can convert m to base w. Then iterate from least significant digit to most significant digit. If a digit d[i] =0 or d[i] = 1 then skip it (w^i is either skipped or added to the set). If d[i]==w-1 or d[i]==w, then subtract w from it, and add 1 to the next higher value bit (d[i+1]+=1). d[i] will become either 0 or -1 (w^i is skipped or added to the other set). This works because subtracting w from a digit is equivalent to adding 1 to the next higher digit. If d[i] is anything else, then it is not possible. complexity: O(logw(m))

I had the same idea! Also had no idea how to implement it. Although I believe that there's a O(1) solution. If that's true — can somebody give a hint? Thanks in advance.

We have to find a solution to this equation: m=a0+a1*(w)+a2*(w^2)+...+a100*(w^100), where -1<=ai<=1 and ai is integer If w=2, then it is always possible, because every number have a binary representation. Let's calculate a0 when w>=3: m-a0=a1*(w)+a2*(w^2)+...+a100*(w^100) Note that m-a0 must be a multiple of w, moreover (m-1)%w != m%w != (m+1)%w. So there are just one possibility for a0. After calculating a0, we can divide both terms by w and repeat the process;

You don't know python 11645160

some things never change

I guess now-a-days they are getting caught and discluded from final standings.

same here