C was awesome!

I made a different algorithm for B and i like share it with you:

   let ans = 0
   let sz = numberOfDigits(n)
   let ans = sz * n
   for(p=10;p<=n;p*=10)
      ans -= p-1
   print (ans)

It's sad to know that O(N^3) passed for problem D for some of my friends while I have been struggling to make an O(N^2 logN) algo. Why 4 sec time limit?? :(

in D, how did O(n^3) pass for n=2000 I got 2 unsuccessful attempt trying to hack O(n^3) solutions

Please check the following two codes for Problem D:

http://codeforces.me/contest/552/submission/11648893

http://codeforces.me/contest/552/submission/11646357

I think both have same time complexity (O(n^3)) but first one got accepted and the other (my solution) got TLE. Why do I get TLE error. Please let me know if I have missed something. Thanks!

My solution for C was brute force:
if(w = 2 or w = 3)
The answer is always yes
else
Every weights has three cases:
1:on the left pan
2:on the right pan
3:unused
and the order is O(3 ^ x) where w ^ x = m

My solution for C was brute force:
if(w == 2 or w == 3)
The answer is always yes
else
Every weights has three cases:
1:on the left pan
2:on the right pan
3:unused
and the order is O(3 ^ x) where w ^ x == m

i tried solving D in contest but got WA.here's my submission...can someone please find a bug in my solution!!

I don't understand the solution for problem C. Specifically the second part -

"if it becomes equal to 0, then we don't put weight, in another case we can't measure the weight of our item and answer is No."

How will it become zero? In base w, no digit will ever exceed w-1, so by subtracting w you can't get zero :/

Я решал C так:

Пусть s = (1 + w¹ + w² + w³ + ... + wⁿ), где s > m.

Тогда проверим все ли цифры числа (s + m) в системе счисления с основанием w меньше либо равны 2.

код: 11645367

In problem D there was also O(n^2 * maxX) solution. For each pair of points we calculate equation of line y(x). Then for each x coordinate we find y(x) and if it is integer and point (x; y(x)) exists, we decrease number of triangles by 1.

D passed in 1.7 seconds and it was O(N^3) 11653540

My solution for Problem C is very simple and it passed: http://codeforces.me/contest/552/submission/11646617

Basically, let's try to solve:

c0 + c1*w^1 + c2*w^2 + ... = m      ------ (Equation 1)

Where each c0, c1, c2 are either -1, 0 or 1.

-1 means we used the weight on right, +1 means we used the weight on left and 0 means we did not use the weight at all.

=> c1*w^1 + c2*w^2 + ... = m - c0
=> w(c1 + c2*w^1 + c3*w^2 + ... ) = m - c0
=> c1 + c2*w^1 + c3*w^2 + ...  = (m - c0)/w        ------ (Equation 2)

Now, notice equation 1 and equation 2 -- we are trying to solve the same problem all over again! So let's recurse!

For such a solution to exist (m — c0) must be a multiple of w.

Let's divide both sides by w and recursively solve if we can find such an m-c0 where c0 = -1 or 0 or 1

Here is solution in plain code:

boolean solve(int w, int m) {
  return w <= 3 || m == 1 || trySolve(w, m-1) || trySolve(w, m) || trySolve(w, m+1)
}

boolean trySolve(int w, int m) {
  return m%w == 0 && solve(w, m/w)
} 

This is also one way of proving that if w = 2 or 3 it always possible since it is guaranteed to find atleast one multiple of 2 and 3 in m-1,m and m+1.

Я думаю, что в Е тоже ограничения заданы неправильно, так как у меня зашел квадрат — предпросчитаем префиксные и суффиксные ответы, дальше перебираем начало и последовательно добавляем элементы, модифицируя, если нужно, ответ

По решению из разбора — можно также предпросчитать префиксные и суффиксные ответы, и начинать идти только от элементов, перед которыми стоят *. Итого ассимптотика O(|S| * кол-во умножений)

In problem B, Why funtion pow() to find powers of 10 doesn't work right sometimes ? ...anyone? in my machine pow() worked well, but when sent to CF judge I receive WA. T_T.

for Problem D,I have subtracted triangles formed from collinear points from total no of triangles but still getting wa. please help .Here is my solution

http://codeforces.me/contest/552/submission/11656405

(For problem B)
why function pow() doesn't work right sometimes?
what should I do in case of finding power ?

Thank you.

А как может получиться ноль? "пытаемся отнять от него w" ... "Если этот разряд ... 0" Если он был [0..w-1] |-w => [-w..-1] как может быть 0?

C can also be solved with this simple approach :-

If m is a power of n then answer is "YES" otherwise check :-

In an array store values of powers of n such that values are less than m .. Also add m and a the power of n just greater than m.. (This is because higher powers of n will not be useful in contributing to the weight on either side !)..

Let elem be the count of elements in the array .. For ex- n=3 m=7, arr={1,3,7,9}; elem=4;

Then simply run a O(2^elem) recursive function to get the values of sum of all 2^elem possible subsets of the array ... If any of the sum (out of 2^elem) repeats then answer is "YES" otherwise "NO"..(It can easily be checked by using a map).

One of my friend Meintoo got it correct during the contest — his iterative solution

here's the link to my solution(after the contest) — recursive solution with comments

Wild_Hamster Many solution get AC below 3 sec.So TL 3 sec not enough to block the n^3/6 solutions.

UPD: Now I see some solution gets AC in 1.1 sec .

It was great contest especially the A,B and C problems can be solved in math ways :)

For problem D, I had a O(n*x[i]*y[i]) solution:

11646915

Can anyone explain me the solution of C 11641785 by I_love_Hoang_Yen , the attempt part and the prove that it will give correct answers?

Can you explain more in problem C. I am not getting when it is not 0/1 what are you saying. Plz explain something more means idea and concrete proof briefly

По-моему, задачу В проще решать рекурсией In my opinion, it is easier to solve B with recursion. http://codeforces.me/contest/552/submission/11638760

Unable to parse markup...

please fix this:) Wild_Hamster

Can someone please explain me why the time complexity of 552D for the solution mentioned is O(n^2*logn)?

Could someone please share their/an implementation of the editorial for C? I am struggling to implement the idea.

Thanks for providing solutions but I think it makes more sense to actually submit them to CF instead of putting to ideone. In this case we will be able not only see the code but also see the time and memory consumed by your solutions (and their own output in case if multiple solutions are allowed).

hello in problem D , can anyone explain how to check the number of point that lay in each line in O(log(n)) thanks in advance

Java solution O(n^3) for problem D works :) 11671766

Can someone explain me this code for Problem D : http://codeforces.me/contest/552/submission/11636769

I know that he is calculating the equation of the line .. But how trip (variable) is working here and also about ans -= trip/3 .... Thanks in advance :)

Zlobobers code for problem D gives compilation error on ideone

Can somebody explain why the complexity of E was O(|s|*17^2) !

Hi everyone,

I'm trying to understand problem D (Vanya and Triangles) but I really can't get it. What does it mean "If some line includes x points, then in fact we counted, that it has 2 * x * (x - 1) points, because we included each point 2*(x-1) times in this line."?

I've tried looking at this solution http://codeforces.me/contest/552/submission/11663734 and I kind of get what he did even if it's not clear what exactly the normalize table does for me.

Can someone explain me more clearly?

I ways get a wrong answer on case 41 in problem E ,can anyone help me to check my program. http://codeforces.me/contest/552/submission/11986906

Thank you :)

how can E be done by brute force?

Прочитал разбор после виртуалки, ради интереса написал Д за куб. Так оно работает быстрее чем n2logn с map!!

Man I can't understand a thing from those solutions, this editorial should be way more clear

Can someone please explain me how to turn some value into a w-ary representation? Because as I know it's always possible to turn any number to only BinaryRepresentation, sorry for my English if there're some mistakes. Thanks in advance!

I solved C a bit differently. Looks like it isn't mentioned in the comments. Apologies if I missed it. So if n = 2 the answer always exists. From n = 3 let's find the sums of all possible subsets of (w^1, w^2, w^3, ...). We only need at most 20 because after that it exceeds 10^9. (This limitation is actually a bit more complicated than that but let's assume it works). Because there are only 20 of these values, one can generate sums for 2^20 subsets within the time limit. If m is present in one of these sums, then the answer is YES. Or if the difference of sums for two subsets is m, the answer is YES. One additional condition to look for is that the subsets must be disjoint. Because you can't have the same weight in both the pans. So for each sum in the found sums array, check if a subset with sum = m - sum[i] exists and see that position_of_found_sum & i is 0 (disjointness).

C is awesome!! Loved it