https://translate.yandex.com/

Не дает посмотреть решения: "Недостаточно прав для просмотра запрошенной страницы".

I think it is important to mention in this analysis that Div2 C gives TLE without using some IO optimizations such as ios::sync_with_stdio(0), cin.tie(0) and '\n' instead of endl, or using scanf/printf. Maybe some other languages have the same problem with IO. So, even if you have right solution with O(log(ab)), it is quite possible to get TLE.

I tested my code with different combinations of IO optimization and only combination of all the mentioned methods (without using scanf/printf) gives AC.

Nice solution in div2 C :)

I had an idea that we could imagine S and P as composition of prime numbers. For example: a = b = 8 = 2³, each game add 2¹ to S/P and 2² to another set. As we see, game could be only if summary power of 2 in P and S divided by 3 (2 + 1 = 3) and.. some another checks. But it will not pass anyway, cnt_prime is too big for sqrt(10⁹).

P.S. cubic root could be found in O(1)? Or you mean single function call..

The time limits of problem C seems to be very strict.

Fast IO — Time limit exceeded

Scanf/printf — passed.

I have to ask one more thing. I thought of one more approach for problem C although I believe it might exceed time limit but the problem is that I am getting wrong answer. Just wanted to know the reason behind it.

My idea is to take input two given numbers and factorise them.

Then start subtracting/erasing smallest prime number in both of them according to need.

For example if a is having 2 in its prime factors with power 1 and b is having 2 with power 2 so subtract one and two accordingly. When power of a number becomes 0 , erase that.

If at any point of time till all factors get erased from map/vector, the lowest prime factors of both numbers are not equal, print No.

If everything passes successfully, print Yes.

Do I have missed anything in my solution?

My solution — http://codeforces.net/contest/834/submission/29031585

Can you find out what's a time complexity with my code? ( Div2 C) 29033678

I think it's O(sqrt(a)+sqrt(b)).But I got TLE in test8

thank you

Content of Bakery is full of mistake.

In case someone is scared away by the treap in 1D's model solution: replace it with a binary indexed tree of size 4n and things will be fine (and faster!).

About Div1-B: we can write D&C solution with O(NKlogN) complexity.

We need build persistent segment tree for queries 'amount of unique numbers on [l; r]'.
And we need array next[i] — such index that a[i] = a[next[i]], i < next[i].

Now in D&C calculation we have M — index on current layer and [start;end] — limits of previous layer.
We can do exactly one query to PST about segment [end + 1;M] in O(logN).
After that we iterate prevIndex from end to start and update amount of unique numbers in O(1) — it increases only if next[prevIndex] > M.

So, additionaly to standard D&C we do one query in O(logN) for each index on current layer, total complexity is O(NKlogN + NKlogN) = O(NKlogN).

834 b can be solved in a single traversal of the string, by maintaining total count of each character.Now, if any character occurs for the first time, then we open the gate and when it's count reduces to zero, then gate is closed. Accordingly keep a gate variable and increment and decrement it in respective situations specified, if at any instant, the value crosses k, print yes otherwise no..

dp(k, n) = min1 ≤ i < ndp(k - 1, i - 1) + c(i, n)

should "min" be "max"?

For problem B in div1, I use divide & conquer optimization and president tree with complexity . In a layer we only need O(n) queries in president tree, then other queries can be calculated from these in O(1) time each. See my code for more details: 29023103.

Can someone explain Div2 D?

In problem Div2.C why do we need to check that the cubic root divides a and b? Also, although I found integers x and y such that a=x^2 * y and b=x*y^2 my solution still fails. Any ideas why?

I'm not sure I understand the described solution to Div1 D, possibly because I'm not very familiar with centroid decompositions. What is a "suffix" of a tree?

My solution is I think O(n log n) operations in Z_M, where some of them are divisions or exponentiation and so take O(log M) time. I haven't checked whether this ends up being O(n log n + n log M) or O(n log n log M) overall.

I use three passes, one to count the total product for all paths, then two more to count it for paths that are too red or too black. For a particular pass I weight the edges as, say -2 for red and 1 for black, and then count only paths with positive total weight. For each subtree I count the number of paths of each possible weight, and the product of their clamminess. So far I think this sounds similar to the official solution, but without the benefit of centroid decomposition to handle balancing. Instead, I use a merging algorithm that can merge trees of size a and b in O(b) time, and always start with the largest child (similar idea to heavy-light decomposition). Each element can thus only be merged O(log n) times.

While this could be achieved with a segment tree, I had a tricky data structure to describe the counts and products on a subtree that had - A deque with an indexing offset, to allow growth at either end, and shifting by a fixed amount (to add the weight of the parent-child edge). - A scale factor that was lazily applied to every path (to account for the clamminess of the new edge). - A combined count+product for all paths with non-negative weight. This allowed computing suffix sums in time proportional to the absolute value of the query weight, and count be adjusted in constant time as the indexing shifted (assuming that all edge weights are O(1)).

This made all the necessary operations on the structure take time scale with the size of the smaller structure being merged in, independently of the size of the merge target.

Can someone please explain this from the editorial of div1-c : "At a first glance it seems that out bruteforce will end up being O(2^n). But an easy observation shows that there can be no more that two separate branches here. The total bruteforce complexity is O(10·n). "

div1 C can be solved in .

Let's select the first digit in which L and R are different (digits before it can be ignored). [L, R] can be split to , and possibly if A + 1 < B. Now we can actually make b₁ ≤ ... ≤ b_k, because if for some index b_l > b_l + 1 then the sets of inedible tails for segments and would be the same. We can also assume that all inedible tail are filled with zeroes to the same length k + 1.

The key observation is that the set of tails for segment can be split into no more than 10 disjoint sets Β₀, ... Β₉ each is described as a fixed set of digits and a minimal value for the rest of k + 1 digits (for example the set of tails for [400, 423] is split into {4} and 0, {4, 1} and 1, {4, 2, 2} and 2, {4, 2, 3} and 3). Then we do the same thing for segment and obtain disjoint sets Α₀, ... Α₉. All we have to do now is calculate the sizes of Α_i, Β_j and Α_i Β_j which can simply be done in O(k) given how those sets are described. If A + 1 < B we simply ignore tails that have at least one digit between A + 1 and B - 1 in Α_i and Β_j while counting and add the number of different tails from to the answer. Total complexity is .

submission

getting tle in D. any idea how to optimize it?

couldn't understand the tutorial.

In problem D (div 2) do we need to pack all n cakes into boxes or just some of them?

Не, я вот четвертые сутки зырю этот разбор Div.1 B и решительно не могу понять идею решения.

Как от одного слоя переходить к следующему? Почему в дереве отрезков лежит величина dp(k,  j  -  1)  +  c(j  +  1,  i)? А именно, почему dp(k, ...), а не dp(k - 1, ...), если мы считаем k-тый слой? Почему пирожное j не попадает ни в левое, ни в правое слагаемое? Мож здесь вообще опечатка?

Я, конечно, с деревни, но разборы Div.1 B, как правило, доступны мне для понимания

Persistent Segment Trees are unnecessary for div1B, as one can instead use the same trick from 868F, where we have the range "sliding" around. Full disclosure: this trick was obtained from Benq

http://codeforces.net/contest/833/submission/33818859

Что означает суффикс некоторого дерева в разборе задачи 833D - Красно-черная паутина?

can anybody explain the implementation of solution I working ? $$$dp(k, n) = max1 ≤ i < ndp(k - 1, i - 1) + c(i, n)$$$ I dont think a one-liner can explain it