**We are aware about the issues with rating in Division 2. MikeMirzayanov is on it and will fix everything soon.**

Congrats to the winners!

Technocup edition:

Div. 1 round:

Div. 2 round:

Analysis can be found here (if it doesn't show the analysis, just wait for a little bit).

**Scoring distribution**:

elimination round: 500-750+750-1500-2000-2750-3250-3750

division 2: 500-750+750-1500-2000-2750-3250

division 1: 500-1000-1750-2250-2750-3250Hi Codeforces!

This weekend, on Oct/26/2019 14:05 (Moscow time) we will hold Codeforces Round 596. It is based on problems of Technocup 2020 Elimination Round 2 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fit into this category, please register at Technocup 2020 website and take part in the Elimination Round 2.

Div. 1 and Div.2 editions are **open and rated for everyone.** As usual the statements will be provided **in English and in Russian**. Register and enjoy the contests!

Have fun!

I hope, that DDOS team will sleep this day.

We never sleep.

once again a required hope prevailed

UPD: And a few unspoken : extended queues, clear stmts, etc.An English article is preferred ;)

Now it

isin English!How can someone with rating >= 1900 register in div.2? :P Or CF doesn’t care about division anymore? I saw some blue competed as rated in last div.3.

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

I think you mean about div.3? If it’s that case, check this. It was rolled back once, but still not completely fixed.

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?

Yeah, seems like someone put the wrong rating range.

I clicked register and got a pop-up saying it's only for people up to 2099.

Fixed now.

Thanks!

What's going on?

Registered before becoming expert

is it rated?

is it rated???????

Div. 1 and Div.2 editions are open and rated for everyonePrepare yourself for DDOS

Is that a threat?

Absolutely no. I just meant that I would be really sad if that happens again, but given the history of technocups on cf I think it is likely and I hope some steps were taken to prevent such disasters in future.

Everyone knows online threats are very dangerous. /s

Hope not, I kinda like the problems

Me too!!

By the number of upvotes, this round is so underrated.

Don't abandon your posts thoughtechnocup =

unrated...Will need there a 12-hour hacking phase after the cont est or not?

2 hour hacking phase for DDosers only

Почему раунд начинается в такое неподходящее время? В 14:00 еще многие учатся.

I believe one possible reason could be codechef lunchtime today?

Today,I wanna ,but NanJing Region .

Will there be English statements?

Of course

Why do you ask such question,DST？

It was mentioned in blog.

It wasn't then.

The experience of Technocup Elimination Round 1 was not good. Due to DDOS attack it was declared unrated. Hope the authority will try their best to avoid these circumstances today.

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

When will the number of problems and score distribution be revealed?

Score distribution?

How many problems are there in div 2?

Edit: announecd now!

>Technocup

INB4 404

Unable to hack?.It's saying can't process your hack. Can anyone help me with it?

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

Very nice questions but website went down..

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

I'm so sad I wasted so much time thinking in some dp solution for C while it's way easier than what I thought

edit:next time I'll talk about how easy the problem is after it's judged lol it's wrong

What's the solution for C?

Here is correct solution, but it needs all google servers or at least a quantum computer

SpoilerYour text to link here...just vary k here

Since p can be negative we cannot simply add up the summands. There could be solutions with (possibly huge number of) negative summands.

How to consider that?

I think there is a short solution to it, mine got accepted, basically I used this,

SpoilerSame bruh! It's so tough to realise your approach is wrong and you should switch methods.

Couldn't load question 'c' at last 10 mins during the contest although I could load other problems. Did you have the same problem ??

same, here

How to solve Div.2 E ?

SpoilerI am not sure if my idea is correct. But I think DP + BIT. dp states are current row, current column, next direction (right or down). From a state we can find till how much we can move in next direction. then dp can be expressed as a range summation, which can be optimized using BIT / segment tree.

You need to consider the pushed rocks, too. So dp[][][] is about position and somehow pushed rocks.

I don't think your idea will pass, as n*m*n is really large.

SpoilerIn my dp, I am making all moves in the same direction at once, so no need to keep pushed rocks in state.

(P.S. I have not been able to submit yet, so not sure about my idea either).

Yes, that is the "somehow" part... ;)

But for sure, one cannot ignore the rocks.

For a position x,y the number of remaining possibilities is dependend on the number of rocks which where pushed on the last move into that position.

You don't need BIT if you do prefix sums.

can you please elaborate on your solution?

My solution was same as the one explained in tutorial. I don't think I can elaborate more than the tutorial. If you fail to understand something from the tutorial, you can ask that specifically.

Thanks for the GIFs in E!

test case 2 in div2 D?

6 2 1 2 4 8 2 4

Yet another hackforces?

I would be very sad if that happens :(

got a message that gave me a heart attack "my solution has been hacked or resubmitted" but nothing changed in my submissions

Hack for d2 C?

Try for smaller P?

5 2

output should be -1?

Yes

Nice problems.

I was having such a good contest till my locked submission for C was hacked..

Respect for E — reference to game Baba is you

So, what is the "trick" in C, how to solve it?

Case p is positive, I found trivial solutions. But for negative p?

What if there are only such solutions that 2^x is huge?

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

Since we can add up infinie number of reps we can add up infinite huge negative and positive numbers. So for negative p there should allways exist a solution.

How to find that one?

What I did was search for answer values only in range from 1 to 50, to get the answer..

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

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.com/contest/1247/submission/63459624

(still proud plz upvote minecraft is the best)

I know for positive p, n-k*p > 0 was the breaking condition for loop. But i wasn't able to get breaking condition for -ve p. Can you tell how you came to know that answer will always be possible for -ve p? And also it was my intuition that incrementing and checking for every k will work.

I just couldn't understand how this solution gives a TLE for B2. Anyone can help?

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

That was exactly the mistake. Thanks!

same was the case with me

Same , very sad , a map could do the work

So how to solve the problem D.

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):$$$

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

What's the hack in div1A?

9 4. ans will be -1 and not 2

daaaamn my solution is wrong but why it's wrong

9-2*4 = 1 cannot be represented as sum of two powers of 2.

:(

I feel you bro :'(

Something like 11 5.

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

How to solve DIV1 — C?

how to solve DIV2-D

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.

thanks man, I understood and submitted accepted code

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

Similar to livw, 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.com/contest/1246/submission/63477502

Everyone knows how to solve div_1 B, except me :(

That last half an hour period of unresponsive site was a nightmare .....My heart stopped for a second (Not literally... XD).

the time limit in problem E was very strict so that recursive do doesn't work sadly there were no time to change the recursive version to the iterative version

Hello,

HackForces!Although my solution on problem A was hacked, I gained

650points just by hacking others!(Why there are only 40 participant in each room?)

Me too! 650

Well-balanced contest

Actually before the contest I was expecting some Hacking on Codeforces (DDOS)

It turned out that there is indeed some hacking, and though I was hacked, I also hacked 7 solutions!

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

same here xD

Did anyone else faced this 504 GATEWAY TIMEOUT issue? Was hoping for extended round :(

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.

!!!

What is the hack for div 2 C and div2 A __

Flag is Win

What is the hack for C div2 or A div1 and A div2?

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

It should give 2...16-4+1-4

It's +4 in the testcase

I think few people will pass problem C bacause there are a great deal of hacks and FSTs!

My code passed :O omg

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

Can someone explain me how to solve Div2 D please?

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.com/contest/1247/submission/63489009]

Thank you!

How to solve Div2-D? I think that separating case $$$k=2$$$ will be enough but I can't submit it as the site is not working in the last minute. Is this the solution because for case $$$k = 3$$$ I think that it might TLE?

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.

How many instructions can run in one second? I every time think about time complexity in terms of Big-O notation.

Case by case. From my experience,

Thanks!

I ran a loop once on codechef IDE, till 1e18, with just 1 operation, incrementing a variable, and it ran in 0 seconds....

It is very good optimization by the compiler.(maybe) Sometimes it will occur.

I solved it like this and it worked

i did the same thing . Pretest Passed

Systest when?

Can div2-B be solved with window slidding technique? Counting the number of different elements in each subarray of length

d?Yes.

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

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

You may have declared the count array for every testcase individually which leads to a complexity of O(tk) (As you need to initialize it with zeros). I did the same mistake and got TLE on testcase 18 as well :( .

where do I find the Editorials of the problems?

Just wait! There will be a link given later.

I submitted div1 C but it's not showing up...

Any one know how to solve Div2 D using single approach for all possible value of k

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

can anyone explain how to solve div2 D??

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.TLE on B2 for not using erase :(

why ?

I didn't pay attention that the test cases number can be large and I kept initializing a 10^6 array each time instead of using map then clearing it.

Why does this result in TLE?

Because sum of k is not guaranteed to be

`<= 1e6`

, so it's $$$O(t * k)$$$Thanks!! Never try to extract elements thinking you will get in O(1) time using vector or unordered map in such cases ,its safer to use map cause its O(logn) always. I wish i could have joined codeforces before ,such an amazing platform!!

This multiple test case thing is so irritating. Fucks me always. My B2 got TLE because I didn't declare one of the array's globally. Why cant you just put all the test cases separately?

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

But it's good to have it in the pretests

Same here, it is annoying that it does not pass because of a small technicality instead of the correctness of the solution. I started doubting the whole solution and did not suspect the initialization of the container :/

What is the logic behind saying that it is guaranteed that sum of n <= 2e5 but sum of k IS NOT. WTF?

I thought multitests' goal is to make pretests better and testing faster BUT not to make your fully correct solution fall on such stupid testcases

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

My main idea is O(n). The reason it falls is just how you clean your array between multitests. I... I..., I have no words...

Don't you just create a new array each test case? I use python so I just do

is it different in cpp?

You have used map. I used a vector. It costs O(k) time to initialize it.

Wait what? What was your algorithm? Can I take a look at code? I’m interested lol

63447527

That’s unfortunate. Why didn’t you use a map though, I thought it’s natural to use when you’re counting with a key?

I could not imagine that sum of k would be greater than 1e6. I still don't see a logic of doing it.

do wrong answer of pretest 1 gets penalty, i never noticed it, i submitted solution of one question to another.

I don't think so.

No, it doesn't.

Poor Testcases :{

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

What is FST?

Failed system tests

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.

You have stolen my dreams and my rating with your empty pretests...

22th testcase of d2 C...

Mathforce and fstforce :)

RIP half of all Div2C submissions. Good job Thanos.

RIP half of all Div2B2

Uh, so does the DDOS attack affect whether this round rated?

It sometimes does, sometimes doesn't, depends on the duration and extent of DDOS attack i believe.

Why part of people's rating changed but others not(like me)?

I have same doubt

What is the expected time complexity of div2 B(hard version) ?

I did it in O(n*logn) during contest but it can be done in O(n) as well

63468353 Why is this giving TLE then ?

Looks like cout issue.

I have already synced out stdio. Or am I missing anything else ?

Oh, sorry, this code:

runs 10000 times for k = 10^6

oh, I get it. What should have been the approach there ?

for (int i = 0; i <= n; i++) hash[a[i]] = 0;

Ohk, thanks :)

For each test case you are declaring a hash array of size k, you need to use hash array globally

63491783 Why now ?

Still $$$O(tk)$$$. There is need $$$O(sum(n))$$$.

yeah, got it. Thanks

Why TLE ? : https://codeforces.com/contest/1247/submission/63464491 I did binary search.

Can be done in O(n).

why? The same code got a TLE in System test, and got AC after System test.

63463673 TLE

63489980 AC

`memset(vis,0,sizeof(int)*(k+5));`

Sum of K is not guarranted to be <=

`1e6`

Year,I know. But,why i got ac after System test with the same code.

And, i am shocked at my friend got ac who used

`memset(vis,0,sizeof(vis))`

.(sorry for my poor english.That's all random, my friend. Anyway I don't see logic of saying that sum of N is <= 2e5, but sum of K is not...

It's very logic. You have to read input sum of N times, so sum of N need to small, for example ~ 2e5 so that people can read input in time. Other than that, there is nothing to do with sum of K. K can be 1e9, or even 1e18. You declared an array of size K for each T testcases without thinking about limit of K * T, that is your fault.

can anyone explain the testcase 22 of problem c?

101 50

If you outputted 2 it's not correct.

$$$2^{a_1} + 2^{a_2} = n - 2*p$$$

$$$2^{a_1} + 2^{a_2} = 1$$$

$$$2^0 + 2^0 > 1$$$

Lesson learnt from Div 2B (Hard Version): Pay attention to the sum of variables like $$$n$$$ and $$$k$$$ over all $$$t$$$ testcases.

For div2C: Reality is often disappointing

How to solve d2c . I saw some submissions they used builtin function . Wondering what the function represent?

It tells you the count of set bits in a number

ooo...got it ......of binary number.....thanks

300iq, top 10 codeforces !!!

Pretests way too weak :'( Lost a lot of rating points.

Bye, Master.. (￣ヘ￣)

Time constraints too strict in B2.

Well done guys

that refers to indices, not values

if we take two elements, the position of one will be guaranteed to be greater than the position of the second. Two elements do not stand in one position. This line just makes no sense. As well as the case when we can take the same numbers. They are either the same or one is larger than the second. In short, this absurdity cost me one task

I think the statement makes sense. It is specifically clarifying the point to not count cases like $$$a_1 \cdot a_1 = 1 = 1^3$$$.

idk how it sounds in English (i use Rus language as u can see), but in the condition it is said to find PAIRS OF NUMBERS. Pair of one and one? May be my bad but i really confused

Not pair of numbers but pair of indexes. i and j are indexes

$$$i = 1, j = 6, 1 < 6$$$

$$$a_i * a_j = 1^3$$$

A moment of entertaining terminology: commutativity. We can get i = 6 and j = 1; a[i] * a[j] == a[j] * a[i] == 1; F A N T A S T I C

What's the problem, dude. If you take i = 6 and j = 1, than i is greater than j

But it still doesnt matter :D

i and j are the indices, not the values of elements.

but $$$1<6$$$ is true man you misunderstood it sadly :eyes:

my rating wasn't updated, why?

Ratings are being updated I guess.

Same here.

Same here

got hacked on C due to my carelessness. so sad:(

I would have said "due to weak pretests" if I were you.

Unable to go to the contest page. :(

Oops! Probably Codeforces can't be reached right now or your Internet connection is broken

Why is my account unrated?

When can I start to upsolve? What is going with the contest right now, there is an error... Does anybody know?

Problem B2 : O(n) solution shows TLE. I used an array, whereas my friend used a map. He got AC. Why?

Maybe you clear the array so many times and the solution is O(n*d) (I don`t remember the letter, seems to be d)

You are clearing the whole array in every testcase .. But you can make array cnt global and clear only used a[i] for every testcase

Why has rating not been updated on my account ?

Why is this round rated for someone while not for others? @Endagorion

May be it is still updating

Even mine too.

![ ]() Whats happening ?

Is rating updating or what?

rating is very funny !! unrated solved 4 problems .. and become unrated !!

Why my rating is not evaluated after end of the Codeforce round 596-div2?

Why I got the time limit exceeded in question B2 in 18th test case. Instead of using vector when I used map then I don't got the error.

Answer is here And hide your code in a spoiler or smth

I made the same mistake. You are declaring a new vector of size k for each test case. Now in the problem k <= 1e6 and no. of test cases t <= 1e4 which makes your solution a O(t*k) time complexity which is 1e10 operations in worst case leading to TLE.

You initialize v2 array for every test case.

and it takes too time for every test case in 18th case.

limit of t... 1≤t≤10000 .

limit of k.... 1≤k≤10^6

so your code run for 10^4*10^6 = 10^10 times .

because of vector v2(k+1,0); this .

Can someone help me. I have little trouble with div2/B2. My solution got TL at the main tests, but same solution(absolutely same) got AC. Here is my solutions: https://codeforces.com/contest/1225/submission/63468733 https://codeforces.com/contest/1225/submission/63494209

Answer

Too much mess with this round, lol

Looks like Thanos snapped half the ratings too along with the submissions.

Just give me my +85 :(

Ittne me itna hi milta hai re baba

Rating system got dddrunk!!!

:3

I want to upsolve but I only can see the "bugs"

Even there contest rating failed after user rank #368

KarmaBaba is you!

Come on, any update on rating changes?

Sir, please clarify that whether the Div. 2 version of this round is rated only for the Top 370 contestants or the round is unrated or something others?

where is rating change?my contest performance is very low :p.unrated is not expected as so.. please... give rating change as soon as possible. :D

Endagorion is this round even rated for everyone

I'm sure it'll be resolved soon. Anyway, I can't help with this

Thank you

why hasn’t my rating changed?

Div. 1 rating has been changed 2 hours or more ago,still why Div. 2 rating has been paused?

Why im not rated in this contest

Even rating updater is ratist :sadness:

I'm wondering whether codeforces authority even noticed that div2 rating update has been stopped at rank 368 where div1 rating changes has been finished 1 or 2 hours ago. At least we deserve to know what's going on. Endagorion MikeMirzayanov

You're right. Now we are trying to figure out what’s the matter and soon it'll be fixed.

Atlast, someone from headquarters,

Thank you for the official reply and reassurance. Now we can rest easy knowing that Headquarters is on the case.

Any idea why my contest rating has not been updated yet? The contest is not appearing in my profile

Rating changes for the last round are temporarily rolled back. They will be returned soon.****watch at the top at codeforce !!!

Missed D by a bit and did silly mistake in A ;P

Hoping the problem related to rating will be fixed soon!

Finally rating updated !!!

my rating shows 1475.

why still pupil??

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. :)

In div2-B2, why I tle on test 22 in the contest and I just submitted the same code, it was accepted!

Answer is O(tk) because you are resetting

`b`

every time.thx

Jury's answer to 10 7 is -1. But can't 10 7 be made by 10 numbers of the form (2^3 — 7)?

its 2^x

+p so your input should be 10 -7.and 10 = (2^4-7) + (2^3-7)

Thanks

Can someone help me to figure out why my submission for problem D is giving WA for test case 12? Submission ID: 63491511

Any kind of help would be greatly appreciated. Thanks!