By Endagorion, 5 years 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. MaksymOboznyi
  3. AlFlen
  4. talant
  5. DANDROZAVR

Div. 1 round:

  1. Benq
  2. jqdai0815
  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

| Write comment?
»
5 years ago, # |
  Vote: I like it +85 Vote: I do not like it

I hope, that DDOS team will sleep this day.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

An English article is preferred ;)

»
5 years 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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years 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.

  • »
    »
    5 years 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?

    • »
      »
      »
      5 years 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.

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

      Fixed now.

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

What's going on?

cf-problem

»
5 years ago, # |
  Vote: I like it -32 Vote: I do not like it

is it rated???????

  • »
    »
    5 years 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

»
5 years ago, # |
  Vote: I like it -39 Vote: I do not like it

Prepare yourself for DDOS

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

    Is that a threat?

    • »
      »
      »
      5 years 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.

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

      Everyone knows online threats are very dangerous. /s

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

    Hope not, I kinda like the problems

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

      Me too!!

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

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

technocup = unrated...

»
5 years 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?

»
5 years ago, # |
Rev. 5   Vote: I like it -13 Vote: I do not like it

Why does it start so early?

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

    I believe one possible reason could be codechef lunchtime today?

»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Today,I wanna ,but NanJing Region .

»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Will there be English statements?

»
5 years 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.

  • »
    »
    5 years 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.

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

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

Score distribution?

»
5 years 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!

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

>Technocup

INB4 404

»
5 years 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?

  • »
    »
    5 years 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 :(

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Very nice questions but website went down..

  • »
    »
    5 years 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 :(

»
5 years 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

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

    What's the solution for C?

    • »
      »
      »
      5 years 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
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years 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?

    • »
      »
      »
      5 years 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
»
5 years 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 ??

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div.2 E ?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it
    Spoiler
    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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).

        • »
          »
          »
          »
          »
          5 years 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.

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

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please elaborate on your solution?

      • »
        »
        »
        »
        5 years 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.

»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Thanks for the GIFs in E!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

test case 2 in div2 D?

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Yet another hackforces?

»
5 years 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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack for d2 C?

»
5 years 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..

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

Respect for E — reference to game Baba is you

»
5 years 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?

  • »
    »
    5 years 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...

    • »
      »
      »
      5 years 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?

      • »
        »
        »
        »
        5 years 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..

  • »
    »
    5 years 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.me/contest/1247/submission/63459624

    (still proud plz upvote minecraft is the best)

»
5 years 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?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So how to solve the problem D.

  • »
    »
    5 years 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.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What's the hack in div1A?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve DIV2-D

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks man, I understood and submitted accepted code

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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.me/contest/1246/submission/63477502

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

»
5 years 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).

»
5 years 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

»
5 years 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?)

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Well-balanced contest

»
5 years 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!

»
5 years 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 :(

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Flag is Win

»
5 years 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?

»
5 years 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!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me how to solve Div2 D please?

  • »
    »
    5 years 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.me/contest/1247/submission/63489009]

»
5 years 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?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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$$$.
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks!

        • »
          »
          »
          »
          »
          5 years 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....

          • »
            »
            »
            »
            »
            »
            5 years 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.

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

      I solved it like this and it worked

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did the same thing . Pretest Passed

»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Systest when?

»
5 years 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?

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

    Yes.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years 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?

    • »
      »
      »
      5 years 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 :( .

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

where do I find the Editorials of the problems?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years 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

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    see mine its single approach i am working under modulo k

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can anyone explain how to solve div2 D??

  • »
    »
    5 years 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.

»
5 years ago, # |
  Vote: I like it +95 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

TLE on B2 for not using erase :(

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

    why ?

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why does this result in TLE?

        • »
          »
          »
          »
          »
          5 years 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)$$$

      • »
        »
        »
        »
        5 years 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!!

»
5 years 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?

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

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

»
5 years 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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years 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...

      • »
        »
        »
        »
        5 years 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?

        • »
          »
          »
          »
          »
          5 years 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.

          • »
            »
            »
            »
            »
            »
            5 years 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

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years 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.

»
5 years 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.

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Poor Testcases :{

  • »
    »
    5 years 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...

  • »
    »
    5 years 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.

»
5 years 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...

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

22th testcase of d2 C...

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

Mathforce and fstforce :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

RIP half of all Div2C submissions. Good job Thanos.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      63468353 Why is this giving TLE then ?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        Looks like cout issue.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

            Oh, sorry, this code:

            for(i=0;i<=k;i++)
                    {
                        hash[i]=0;
                    }
            

            runs 10000 times for k = 10^6

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

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

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

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +2 Vote: I do not like it

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

»
5 years 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

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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.

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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...

        • »
          »
          »
          »
          »
          5 years 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the testcase 22 of problem c?

  • »
    »
    5 years 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$$$

»
5 years 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.

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

For div2C: Reality is often disappointing

»
5 years 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?

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

300iq, top 10 codeforces !!!

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bye, Master.. ( ̄ヘ ̄)

»
5 years ago, # |
  Vote: I like it -74 Vote: I do not like it

Well done guys

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

    that refers to indices, not values

    • »
      »
      »
      5 years 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

      • »
        »
        »
        »
        5 years 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$$$.

        • »
          »
          »
          »
          »
          5 years 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

          • »
            »
            »
            »
            »
            »
            5 years 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

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

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

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

    • »
      »
      »
      5 years 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

      • »
        »
        »
        »
        5 years 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

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

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

my rating wasn't updated, why?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 years 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

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is my account unrated?

»
5 years 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?

»
5 years 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?

  • »
    »
    5 years 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)

  • »
    »
    5 years 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

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Why has rating not been updated on my account ?

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Is rating updating or what?

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

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

»
5 years 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?

»
5 years 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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years 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.

  • »
    »
    5 years 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 .

»
5 years 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.me/contest/1225/submission/63468733 https://codeforces.me/contest/1225/submission/63494209

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Too much mess with this round, lol

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Rating system got dddrunk!!!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Even there contest rating failed after user rank #368 Karma

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Baba is you!

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

Come on, any update on rating changes?

»
5 years 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?

»
5 years 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

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

Endagorion is this round even rated for everyone

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

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

why hasn’t my rating changed?

»
5 years 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?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Even rating updater is ratist :sadness:

»
5 years 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

  • »
    »
    5 years 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.

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

      Atlast, someone from headquarters,

    • »
      »
      »
      5 years 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.

»
5 years 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

  • »
    »
    5 years 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 !!!

»
5 years 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!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally rating updated !!!

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

my rating shows 1475.

why still pupil??

»
5 years 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!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Answer is O(tk) because you are resetting b every time.

»
5 years 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)?

»
5 years 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!