Почему рейтинг не всем дали?

Why does 63503240 gives TLE in div2 B2?

I solved D, with a different approach(after contest).
I calculated divisors of $$$x^k$$$ for every $$$x$$$ such that 1 <= $$$x$$$ <= $$$10^5$$$ and $$$x^k$$$ <= $$$1e10$$$.Since $$$x$$$ can be only in range $$$1$$$ to $$$10^5$$$ in worst case, we can calculate the divisors of $$$x^k$$$ using prime factors of $$$x$$$. Caluculating prime factors of $$$x^k$$$ is easy if we know prime factors of $$$x$$$, we just need to multiply power of every particular prime factor by $$$k$$$. Since we know divisors of every $$$x^k$$$ we can easily count pairs such that $$$Ai*Aj$$$ = $$$x^k$$$.

Can someone tell me what is wrong in my coding approach for Power Products(D)

I am sorting the array and using two pointer approach to find possible pairsI

63471990

Has the tutorial not been made or there is some bug.It is showing tutorial not available for problems D-G

Edit:resolved

in Problem E what is the best RSQ can be used with a few implementation cause i thought of segment tree so that we have n segment tree of base m and m segment tree of size n but it would be a lot of implementation so what do u think ?

In problem $$$C$$$, why does $$$n-kp$$$ has to be at least $$$k$$$ can someone please throw some light on it?

Please look upon the issue of editorial.It's showing that "Tutorial is not available"

can someone explain how to solve div2E/div1C , in editorial it's not clear about defination of D,R arrays?

It would be great if someone can explain me easier way solution of div2-C. I cant understand the solution and I,m not so fimiliar with binary numbers, bit cnt etc.

Thanks a lot. :)

My approach for D:

Let $$$f_{1}$$$ be a function such that $$$f_{1}(a)=b$$$ for $$$1 \le a \le 10^5$$$ where $$$b=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}$$$. Here $$$p_{i}$$$ is a prime and $$$c_{i}<k$$$.

Let $$$fr$$$ gives frequency of an element in given array. Hence for $$$1 \le i \le 10^5$$$ do $$$freq[f_{1}(i)]=freq[f_{1}(i)] + fr[i]$$$.

Now, let $$$f_{2}$$$ be a funtion such that $$$f_{2}(a)=b'$$$ where $$$b'=p_{1}^{k-c_{1}}p_{2}^{k-c_{2}}...p_{m}^{k-c_{m}}$$$.

The answer is ans

$$$ ans= \begin{cases} ans \enspace + \enspace freq[f_{1}(i)] \times freq[f_{2}(i)], & \text{if } f_{1}(i) \ne f_{2}(i)\\ ans \enspace + \enspace freq[f_{1}(i)] \times (freq[f_{2}(i)] - 1)/2, & \text{otherwise} \end{cases} $$$

Note: Chech if $$$f_{1}(i)$$$ has already been calculated as $$$f_{1}(i) = f_{1}(j)$$$ for $$$i \ne j$$$.

Link to code

Alternative solution to G:

• Consider the dumb $$$O(N^\alpha 3^N (\sum a_i)^2)$$$ DP solution that just finds numbers that can be made from each subset. It's too slow.
• Add bitsets. It's still too slow.
• Consider a different $$$O(N^\alpha 3^N (\sum a_i)^2)$$$ DP solution that goes in the reverse direction and calculates for each subset and number "if we can make this number using this subset, we win". It uses the results of the previous DP, because when we want to make $$$x$$$ (or $$$xK, xK^2, \ldots$$$) using subset $$$i$$$ and we can definitely make $$$y \le x$$$ using a subset $$$j \subset i$$$, then we want to make $$$x-y$$$ using the subset $$$i-j$$$. It's still too slow.
• Combine these two DPs in a meet-in-the-middle approach. Due to symmetry, we only need to consider cases where the subset $$$j$$$ above is smaller than $$$i-j$$$, or equally large (with some tiebreaker like j < i-j). As soon as we find out that we both can make number $$$j$$$ using subset $$$i$$$ (first DP) and if we make it, we win (second DP), we can stop and use the first DP to construct a solution.
• The first DP now only needs to consider subsets with size $$$\le N/2$$$. The theoretical bound isn't much better, but in practice, we have much fewer states to consider both because there are less subsets and much fewer numbers to make using small subsets.
• The second DP only needs to consider the remaining subsets and it will either quickly find a solution or have very few states to process, so it's pretty fast either way. Intuitively:
  • If the first DP finds many numbers, the chance that the second DP also finds many numbers (using those found by the first DP) and therefore that it quickly stumbles upon a solution is high.
  • If the second DP finds few numbers, the first DP will have difficulty forming many numbers we want to make using large subsets. Small subsets should automatically consume little time, since they have fewer subsets and in the split $$$i \rightarrow (j, i-j)$$$ described above, if the sets $$$j$$$ and $$$i-j$$$ are both processed by the first DP, we don't gain any states in the second DP.
  • If $$$i$$$ is large and $$$j$$$ is kinda large, then $$$i-j$$$ is much smaller than $$$i$$$ and we already get a small state. On the other hand, when $$$i$$$ is large and $$$j$$$ is very small, then there are few numbers we can make using the subset $$$j$$$.

Time complexity: 1200 ms.

I waited for like 10 MINUTES and there was still no editorial. Can anyone who can see the editorial for Div. 1 B to Div. 1 F consider posting the editorial on somewhere else for others' convenience?

I got TLE in div2 B2 when contest final consequence came out.But accepted it after contest with exactly the same codes.

Is this an alternative solution to problem F(Div. 1)?

Again, solve it backwards.

Consider elements in [L, X] can reach X in no more than K steps. Then, elements in [L', X] can reach X in no more than K + 1 steps, where L' = min_i{pre[i], L <= i <= X} where pre[i] = the last occurance of ch[i] before i(ch[] is the string in the input).

Let's try to fix X. Then, the process above forms a tree structure, and what we need to compute is the sum on the path from X to the root.

Consider how does the tree change when 1 is added to X. The parent of an interval [[the minimal Y such that min{pre[Y...X]} >= pre[X]], X] will be modified to pre[X] while the other vertices of the tree remain unchanged. Put the intervals with the same parent together and we only need basic operations in dynamic trees to fix it.

Use Link Cut Tree or Euler Tour Tree(I'm not sure because I don't know ETT well) to solve the problem in O(n log n).

For Div2 C can someone explain the case when P is negative answer for K still won't cross 31

In solution of D there is a small mistake. It is given that 360 = 2^3 * 2^2 *5 but it should be 360 = 2^3 * 3^2 * 5

Could someone give me a elaborated explanation for problem Div2-C. The Edtiorial is so hard to grasp, especially the range of all $$$k$$$ value. Thanks

Что значит Разбор недоступен, начиная с задачи D по F?

Why does https://mirror.codeforces.com/contest/1225/submission/63542673 give TLE using g++, but works with MSVC???

Почему https://mirror.codeforces.com/contest/1225/submission/63542673 ловит TLE c g++, но берёт accepted с MSVC??? Помогите, пожалуйста.

In case(like me ) you are having a hard time implementing problem D tutorial (DIV 2) here is a implementation of the given approach
https://mirror.codeforces.com/contest/1225/submission/63557938

Can someone explain B2 to me..

Typo in ur editorial of D -> factorisation of 360 should be 2^3 3^2 5^1 u mistyped 2 in place of 3

Maybe it will be useful for users who will try to solve this task later. I've found that the following solution passes all authors' tests although it's incorrect: Let's consider DP[N][X][Y] — it is 1, if we can apply such consequence of operations to N-length prefix of an array so that last two numbers are X and Y, and 0 if we can't. Then DP[2][A[1]][A[2]] = DP[2][A[2]][A[1]] = 1, and for each i from 2 to N and X, Y from 1 to 2000 if DP[i — 1][X][Y] == 1 then DP[i][f(X+A[i])][Y] = DP[i][Y][f(X+A[i])] = DP[i][X][f(Y+A[i])] = DP[i][f(Y + A[i])][X] = DP[f(X+Y)][A[i]] = DP[A[i]][f(X+Y)] = 1. So in the end we just have to check if for some X, Y such that f(X+Y)=1 DP[i][X][Y] == 1, and restore the answer. The problem is that in general it's not true that f(f(a+b)+c) = f(a+f(b+c)). Test that breaks this solution: 8 4 39 39 51 13 38 66 98 86

I found it interesting that my friend skip1978 solved div1 E using the random method.

I wonder how high the correct rate of this method is.

63493030

Can someone please tell me what is wrong with my prime factorization in this code for D : Code 1

Also , after changing it I got ac Code 2

Thanks in advance !

I cant understand in D one thing. What if we have ones? This solution doesn"t work in this case.

Can somebody tell me how to solve div2 B2 in O(n) as maintaining count with array will give TLE?

Can someone explain problem E to me?

In the task D how can we find factorization of every number in the sequence with sqrt(max ai) or log2(max ai) complexity?__

I am unable to understand E's editorial. please help.

Thanks for Fast Editorial.

Почему в задаче с p + 1 < 0, при n − 31 (p+1) < 0? При n n = 10 и p = 1 первое условие неверно, а второе — верно. И почему n — 31p < 2^31 при n >= 31p + 31, а не при 30p + 30, если так проверяемых k меньше?

In problem D, we don't need to store the whole list. We know that each list gives us unique number so we just store that number and its frequency.

why 197067161 gives TLE? i'm really sure that code is O(n) per test case

My $$$O(n^\frac{5}{3})$$$ code works for D, just thought it was interesting and curious that it got accepted.

On a second look, I think it can be hacked easily. The test cases for D were quite weak.

233245894

Why don't the dickhead authors provide their own code ?