We never sleep.

once again a required hope prevailed UPD : And a few unspoken : extended queues, clear stmts, etc.

Now it is in English!

Wasn't it because of the temporary rating change rollback?

Must be some bug, usually only standalone Div 2 rounds are rated for <= 2100. Endagorion, is this normal that I could register for both Div 1 and Div 2 rounds?

Registered before becoming expert

Div. 1 and Div.2 editions are open and rated for everyone

Is that a threat?

Hope not, I kinda like the problems

2 hour hacking phase for DDosers only

I believe one possible reason could be codechef lunchtime today?

Of course

Why do you ask such question,DST？

It was mentioned in blog.

Now, it has become one of the cliche comments. Every one of us wants the round to be safe from DDoS attacks.

Same here. I know a good input to hack, but unable to submit it :(

I agree. I wanted to submit a solution in the very last minute but couldn't because site went down :(

What's the solution for C?

same, here

6 2 1 2 4 8 2 4

I would be very sad if that happens :(

Try for smaller P?

5 2

I thought that answer is always in a small range, I could be wrong though...

I SOLVED IT OMG I AM SO PROUD

ok anyways so basically if you write n as sum of k (2^i+p), then

n = (2^a + p) + (2^b + p) + ... + (2^x + p) right

n = (sum of k "power of 2s") + kp

sum of k "power of 2s" = n — k * p

So what remains is to check whether n — k * p can be written as k "power of 2s" (with duplicates). This is kinda well known lmao. But basically

def check(x, k):
    if k < x: return False
    if bin(x).count('1'):
        # counting the number of set bits in binary of x
        # This is because the binary expression is the unique way of representing x as sum of power of 2s with minimal number
        return False
    return True

Sorry if you don't code in python but I'm sure you can code the "count set bit"

Now loop through all k (while n — k * p >= 0) and check that

Code: https://codeforces.net/contest/1247/submission/63459624

(still proud plz upvote minecraft is the best)

have u declared an array for counting in every test case??

Firstly,we use backet sort and convert the input to backet[number]={count}.

And do next for all $$$i(1 \le i \le 10^5):$$$

• find the minimum $$$p$$$ that satisfies $$$i*p = x^k$$$(we can use prime factorization for this.)
• count pair $$$(i,p * v^k)(1 \le v \le 500$$$ thanks to $$$k \ge 2$$$ and $$$N \le 10^5)$$$

We have to use valid pre-calculation for doing this.

9 4. ans will be -1 and not 2

Something like 11 5.

Basically, checking if N — i * p <= i.

How to solve DIV1 — C?

Let the prime factorization of y be p1^k1 + p2^k2 + ... + pm^km. Then y = x^k if kj % k == 0 for every j<=m. So we only need to take care of modulo of kj with k.

For each ai, find it's modulo prime factorization (i.e p1^(k1%k) + p2^(k2%k) + ...). Note that we need to remove pj^kj if kj = 0. Then aj * ai = x^k if modulo prime factorization of aj equal p1^(k-k1%k) + p2^(k-k2%k) + ... Let it be ai's reverse modulo prime factorization.

Store number of each modulo prime factorization by map, iterate from 1 to n, for each ai add number of it's reverse modulo prime factorizations to result, then update it's module prime factorization.

refer my comment, let me know if its correct. https://codeforces.net/blog/entry/70852?#comment-553827

Similar to tantam75, I also use prime factorization.

Noted that if $$$a_i \times a_j = \sum p_i^{u_i} $$$, then $$$k|u_i$$$. So for each $$$a_i=\sum p_i^{x_i}$$$, We store every $$$(p_i, x_i \ \mathrm{mod}\ k )$$$ in an array . To satisfy the equation, $$$a_j$$$'s factorization must be $$$\sum p_i^{k-x_i \ \mathrm{mod} k } $$$. Therefore we only need to count how many arrays in which every element equals to $$$ (p_i,k-x_i \mathrm{mod}\ k) $$$. map< vector< pair<int,int> >, int> cnt; can do that.

Complexity: As the size of each array is at most $$$O(\log n)$$$ , the final complexity is $$$O(n \log ^2 n)$$$

Code: https://codeforces.net/contest/1246/submission/63477502

Me too! 650

Wise decision! While it was too late when I realized it :)

Yep , Same here

Yes, lots of times. I tried to hack some solutions, and when I loaded the room, it gave me that error too.

!!!

9 4. should give -1 and not 2.. for div2C

My code passed :O omg

https://codeforces.net/contest/1247/submission/63459624

For each number, do the prime factorization, and do a modulus of the powers with K. So for the given sample case in the problem, your array becomes 1 3 9 1 3 1. Lets iterate from left to right in this array. At say i = 2, (number is 9), what you want is 3 to make it "good". What you have is 9. See from some frequency table if you have what you need, and update answer. Also then, add what you have in this frequnecy table. See submission #63466377 of me, to get the above idea.

EDIT: also take care of overflows [ https://codeforces.net/contest/1247/submission/63489009]

How do you solve that cases with small k, ie k==2?

I think it will not TLE because, if $$$k = 3$$$, No. of Instruction will be around $$$217000000$$$ (Approx.) that is $$$(2.17 * 10 ^ 8)$$$. That should runs in less than a $$$1$$$ second.

i did the same thing . Pretest Passed

Yes.

Yes, I used an ordered map for it... :D

Facing TLE on test case 18 with window sliding technique. Does anyone know why?

Just wait! There will be a link given later.

Couldn't submit, but this is how I approached the problem, for each element, find its prime factorization, say p1^m1*p2^m2...pn^mn be prime factorization of some element arr[i] in the array. Now take modulus of each m's by given 'k', and replace arr[i] by p1^(m1%k)*p2^(m2%k)...pn^(mn%k). Now store the count of these elements in a map.

Now traveling the array, picking each element, find its counterpart (p1^(k — m1%k)*p2^(k — m2%k)...pn^(k — mn%k)) count in the map, increase the number. Note if counterpart is same as a[i], then decrease the count by 1 (not counting the array element with itself). Then return total count /2.

Let $$$a_i=\prod p_{i,1}^{c_{i,1}}\times p_{i,2}^{c_{i,2}}\times \dots \times p_{i,l_i}^{c_{i,l_i}}$$$.($$$p$$$ are increasing, $$$c$$$ are positive numbers)

$$$i$$$ and $$$j$$$ satisfy the condition if and only if $$$l_i=l_j$$$ and $$$p_{i,x}=p_{j,x}$$$ and $$$k|(c_{i,x}+c_{j,x})$$$.

So push all $$$(p_{i,x},c_{i,x}\bmod k)$$$'s into a vector, and use a map to calculate the times it occurs before.

see mine its single approach i am working under modulo k

With each $$$a_i$$$, add result with number of $$$a_j$$$ that $$$j<i$$$ and $$$a_j \times a_i = x^k$$$. You can think of prime factorization, but since different numbers has different factorizations, you need to minimize those factorizations by modding exponents with $$$k$$$ and remove prime factor whose post-exponents equal to 0.

why ?

Would you like a problem with 1e5+ test datas?

your code should be O(n) not O(k) unfortunately :( (I think)

I don't think so.

No, it doesn't.

Yes,I got FST on problem C,and my rating will drop below 1700...

I think it was better to not include the test cases > 60 in pretest and let many fail. People nowadays just guessing the answer without doing any work on what limits should one use.