понятно что решение с перебором O(n^2) проходят, не понятно почему много кто их отправлял и в разборе алгоритм с более сложной асимптотикой

NlogN видимо

Тоже интересно. Решал так же, интуиция подсказывает, что слишком далеко перебирать не придется, но "не слишком много" — это не самая точная оценка времени.

Я такое же сдал и, на сколько я понимаю, сложность O(log N) — так как увеличение V будет мало. (лучше точно проверить, но вроде как всегда меньше 10 раз)

Посмотри моё решение.

А кто-то может доказать, почему такое решение работает?

чем?

По-моему проще написать бинпоиск, хотя так тоже можно)

Эта формула по сути выводится из формулы бесконечно убывающей геометрической прогрессии(ans/1-1/k)>=n => ans>=n-n/k где ans это первый элемент,1/k-знаменатель прогрессии,а n-сумма прогрессии.Говорим об одних и тех же вещах разными словами.

var k,s,ans:int64;
    c:char;
    sum:array [0..1001000] of longint;
 begin
  readln(k);
  sum[0]:=1;
  while not eoln do
   begin
    read(c);
    s:=s+ord(c)-ord('0');
    if s-k>=0 then ans:=ans+sum[s-k];
    inc(sum[s]);
   end;
  writeln(ans);
 end.

Вот самая простая реализация на паскале...

Интересно...я в дорешивании тоже пытаюсь сдать такое решение(мне оно тоже показалось проще), но падает на 67 тесте, и, смотрю, не у меня одного. Не могу понять, почему.

Use Heavy Light Decomposition

My solution : https://mirror.codeforces.com/contest/165/submission/243532902

Actually this solution is incorrect. It gives wrong answer even on test #1, anyway idea is quite simple. If for position i sum of 1's from position 0 to i is equal s and s >= k then you need to find number of positions with sum of 1's equal s-k (let's denote it as C[s-k]) and add it to the result. We will get full result after processing all positions.

Instead of processing each position individually we can count the number of positions with sum of 1's equal to 1, 2, ... etc. and iterate over them. Then if we are processing some sum equal s we should add to the result value C[s]*C[s-k]. This solution will not work for k = 0. In this case we should add value (C[s]-1)*C[s]/2. Why? Because if we've got C[s] positions with sum equal to s then one of this position contains 1, so we need to find how many different sub strings we can get from C[s]-1 0's.

Correct solution: 11487947

Consider two different cases when k=0 and when k!=0; When k=0, it is simple to calculate the number of strings by storing the position of occurrence of '1' in a vector and then iterate over the string and calculate the answer.(try it yourself it is simple). When k!=0,let's assume dp[i] = number of strings ending at position i and containing k 1's. Make a vector which stores the position of occurrence of 1 and use to calculate the answer. try it yourself.

Let's suppose you have a number X and we invert the binary digits of X, now we have a number Y that has some 1s and some 0s, we want to find another number Z that has a 0 in every position where Y has a 0. It is important to note that every 0 in Y must strictly be a 0 in Z, but each 1 can be either a 1 or a 0 in Z.

A naive solution would be for every number Y in the range [1-4*10^6] iterate over every number Z in the same range, and for every valid pair, check if that number exists in a, if it exists you found an answer for Y, otherwise it's -1. Then you can just iterate over a and look at the solutions you precalculated by inverting the bits of each a[i].

Of course, this wouldn't work because it's too slow, time complexity would be O(2^2*maxBits) if you iterate over all numbers in the range [1-4*10^6], or O(3^maxBits) if you use bitwise operations to ignore invalid Zs. Both too slow, so we need to optimize it.

We will take similar idea, but change it slightly, for every Y that has an answer we say that we can propagate the answer to another number W, if and only if Y&W=Y and W has exactly 1 more bit turned on compared to Y. This works because as we stated earlier, we want Z to have zeros where Y has zeros, but if Y has a 1, we don't care what we have in Z, and because W is the same as Y, except that one 0 is now a 1, we know that Z will still be valid. We code this idea with DP and it becomes O(maxBits*2^maxBits)

http://www.codeforces.com/contest/165/submission/18102743

Read code of top rating, maybe it helps (at least for me) =))

you can use binary search as given in the editorial but i have another approach -->

think of it as

find min v, such that:-

1) n <= v*(1 + flr(1/k) + flr(1/k^2) + flr(1/k^3) ...)         
consider this:-

2) n <= v*(1 + 1/k + 1/k^2 + 1/k^3 + ...)

lets just keep lhs aside for now, think about try to keep the rhs constant on going from eq 1 to eq 2.
like:- 
3) v1*(1 + flr(1/k) + flr(1/k^2) + flr(1/k^3) ...) = v2*(1 + 1/k + 1/k^2 + 1/k^3 + ...)

as we can easily find (1 + 1/k + 1/k^2 + 1/k^3 + ...) == (k)/(k-1) and we can see from eq 3 that v1 >= v2 as (1 + flr(1/k) + flr(1/k^2) + flr(1/k^3) ...) <= (1 + 1/k + 1/k^2 + 1/k^3 + ...)

so we can find v2 very easily using v2 = n*(k-1)/(k)
v2 is the lower limit for our ans (==v1)
now just run a loop from v2, as soon as the sum becomes >= n, break and you have the answer

please correct me if my logics wrong here is the code 83607371

I just did, you can see my solution here — 87349681

Here is my logic —

Basically, we do a 2 pointer theorem approach, in that we find the sum of substring starting with index i with the help of binary search for all i (Maintain a prefix sum array, to easily calculate required sum in a given interval starting from i).

When that sum is same as k, we take 'mid' element we have obtained via binary search (corresponding to the right end of the substring) and take the left and right extremities of adjacent elements having the same value as the 'mid' element in the prefix sum array (Notice that each pair of extremities would have a unique identifier as the values in prefix array are increasing).

For better understanding, I would recommend you to see the solution