Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

By Endagorion, 4 months ago, translation, In English,

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:

  1. cookiedoth
  2. MaximOboznyi
  3. AlFlen
  4. Chereshnya_
  5. DANDROZAVR

Div. 1 round:

  1. Benq
  2. wxhtxdy
  3. tourist
  4. Um_nik
  5. TLE

Div. 2 round:

  1. BBumblebee
  2. twytch19
  3. zhongyuwei
  4. kpink
  5. 1LLUS0RY

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!

 
 
 
 
  • Vote: I like it
  • +187
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +85 Vote: I do not like it

I hope, that DDOS team will sleep this day.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

An English article is preferred ;)

»
4 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      Fixed now.

»
4 months ago, # |
Rev. 3   Vote: I like it +46 Vote: I do not like it

What's going on?

cf-problem

»
4 months ago, # |
  Vote: I like it -22 Vote: I do not like it

is it rated?

»
4 months ago, # |
  Vote: I like it -32 Vote: I do not like it

is it rated???????

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it +15 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -39 Vote: I do not like it

Prepare yourself for DDOS

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Is that a threat?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +79 Vote: I do not like it

      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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Everyone knows online threats are very dangerous. /s

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +143 Vote: I do not like it

    Hope not, I kinda like the problems

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Me too!!

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

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it
    Don't abandon your posts though
»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

technocup = unrated...

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    I believe one possible reason could be codechef lunchtime today?

»
4 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Today,I wanna ,but NanJing Region .

»
4 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Will there be English statements?

»
4 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Score distribution?

»
4 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

How many problems are there in div 2?
Edit: announecd now!

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

>Technocup

INB4 404

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Very nice questions but website went down..

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    What's the solution for C?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

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

      Spoiler
    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      Spoiler
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div.2 E ?

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it
    Spoiler
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        Spoiler

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

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

          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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please elaborate on your solution?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
4 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Thanks for the GIFs in E!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

test case 2 in div2 D?

»
4 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Yet another hackforces?

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack for d2 C?

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice problems.

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

»
4 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

Respect for E — reference to game Baba is you

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

    (still proud plz upvote minecraft is the best)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So how to solve the problem D.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What's the hack in div1A?

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve DIV2-D

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks man, I understood and submitted accepted code

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
    Rev. 20   Vote: I like it 0 Vote: I do not like it

    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

»
4 months ago, # |
  Vote: I like it +24 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it +79 Vote: I do not like it

Hello, HackForces !

Although my solution on problem A was hacked, I gained 650 points just by hacking others!

(Why there are only 40 participant in each room?)

»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Well-balanced contest

»
4 months ago, # |
  Vote: I like it +41 Vote: I do not like it

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!

»
4 months ago, # |
  Vote: I like it +54 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Flag is Win

»
4 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me how to solve Div2 D please?

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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]

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Case by case. From my experience,

        • If the instructions are complicate (like multiplication,division...), it will be $$$10^8$$$.
        • If the instructions are quite simple (like addition,subtraction,easy conditional branch...), it can reach $$$10^9$$$.
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks!

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I solved it like this and it worked

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did the same thing . Pretest Passed

»
4 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Systest when?

»
4 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Yes.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

where do I find the Editorials of the problems?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    see mine its single approach i am working under modulo k

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

can anyone explain how to solve div2 D??

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it +95 Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

TLE on B2 for not using erase :(

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    why ?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why does this result in TLE?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Because sum of k is not guaranteed to be <= 1e6, so it's $$$O(t * k)$$$

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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!!

»
4 months ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But it's good to have it in the pretests

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :/

»
4 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        for _ in range(int(input())):
            a,b,c=map(int,input().split())
            arr=list(map(int,input().split()))
            # BLA
        

        is it different in cpp?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Poor Testcases :{

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 months ago, # |
Rev. 2   Vote: I like it +54 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

22th testcase of d2 C...

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Mathforce and fstforce :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

RIP half of all Div2C submissions. Good job Thanos.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

63463673 TLE

63489980 AC

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    Sum of K is not guarranted to be <= 1e6

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      And, i am shocked at my friend got ac who used memset(vis,0,sizeof(vis)) .(sorry for my poor english.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the testcase 22 of problem c?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

For div2C: Reality is often disappointing

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

300iq, top 10 codeforces !!!

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bye, Master.. ( ̄ヘ ̄)

»
4 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Time constraints too strict in B2.

»
4 months ago, # |
  Vote: I like it -74 Vote: I do not like it

Well done guys

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    that refers to indices, not values

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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$$$.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it -6 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But it still doesnt matter :D

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

my rating wasn't updated, why?

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
Rev. 14   Vote: I like it +1 Vote: I do not like it

Unable to go to the contest page. :(

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is my account unrated?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)

  • »
    »
    4 months ago, # ^ |
    Rev. 7   Vote: I like it +1 Vote: I do not like it

    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

»
4 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Why has rating not been updated on my account ?

»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

![ ](Screenshot-869.png) Whats happening ?

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Is rating updating or what?

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You initialize v2 array for every test case.

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Too much mess with this round, lol

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Rating system got dddrunk!!!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Even there contest rating failed after user rank #368 Karma

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Baba is you!

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Come on, any update on rating changes?

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Endagorion is this round even rated for everyone

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

why hasn’t my rating changed?

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why im not rated in this contest

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Even rating updater is ratist :sadness:

»
4 months ago, # |
Rev. 10   Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Atlast, someone from headquarters,

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Rating changes for the last round are temporarily rolled back. They will be returned soon.****

    watch at the top at codeforce !!!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Hoping the problem related to rating will be fixed soon!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally rating updated !!!

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

my rating shows 1475.

why still pupil??

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!