satyam343's blog

Codeforces Round #838 (Div. 2)
By satyam343, 2 years ago, In English

Hello, Codeforces!

amurto and I are glad to invite everyone to participate in Codeforces Round 838 (Div. 2), which will be held on Dec/15/2022 17:35 (Moscow time).

This Round will be rated for participants with rating strictly lower than 2100. Participants from the first division are also welcomed to take part in the competition but it will be unrated for them.

You will be given 7 problems and 2 hours and 30 minutes to solve them. One of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round!

We would like to thank:

Score distribution is 500 — 1000 — 1750 — 2000 — 2500 — 2750 — 3500.

UPD1: Congratulations to the winners!

Overall:

Rated:

UPD2: Editorial is out.

We are looking forward to your participation!

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

Comments Comments (204)
| Write comment?
»
2 years ago, # |
  Vote: I like it +47 Vote: I do not like it

Really awesome problems that I enjoyed testing very much. Highly recommended to participate (and up-solve :P)

→ Reply
»
2 years ago, # |
  Vote: I like it +68 Vote: I do not like it

As a tester, this is truly one of the rounds of all time.

Spoiler
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    brobat orz

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

    A, B, and C are truly amazing. D got fewer solves :-( in this round.

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

      Can you explain your approach for B

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

        sort the array; start making each element a multiple of previous;

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

        Just try to make all numbers (let num be 'x') equal to nearest power of 2 which is greater than or equal to 'x'. And with little observation you will be able to conclude that the nearest power of 2 (let it be 'y') such that it is greater than or equal to 'x' will always be lesser than 'x' i.e. y — x <= x. This way you don't need to sort the array or use any vector.

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

          That's nice, btw one can immediately see the fact if you represent $$$x$$$ in binary. If $$$i^{th}$$$ bit is the msb, then, then after adding $$$2^{i}$$$ (note that $$$2^{i} \le x $$$) the number becomes $$$ \ge 2^{i+1}$$$. So, after adding some stuff which is $$$\le x$$$ we get a number that's higher than the next power of two. So, its proved!

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

            Yes exactly btw what was your approach for this question?

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

        make every element equal to power of 2

        → Reply
»
2 years ago, # |
  Vote: I like it +70 Vote: I do not like it

As a tester master, I am the master tester. First round I tested, orz problems!!

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

    As a tester newbie, I am the newbie tester. Second stack round I tested, orz problems!!

    → Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Cool problems, I recommend taking part.

→ Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

As a tester, Good luck to everyone who will participate

→ Reply
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

As a tester, I can assure you all will have fun in solving problems.

→ Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

As a tester, I have enjoyed testing this problem set and all of the problems are really high quality

→ Reply
»
2 years ago, # |
  Vote: I like it +49 Vote: I do not like it

As a tester, I hope you'll enjoy the problems as much as I did! Yet another well-coordinated round by errorgorn :)

→ Reply
»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Please participate

→ Reply
»
2 years ago, # |
  Vote: I like it +40 Vote: I do not like it

As a tester, I highly recommend reading all the problems.

→ Reply
»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

blog of #838 posted and there's no editorial for #837

→ Reply
»
2 years ago, # |
  Vote: I like it +63 Vote: I do not like it

As a tester, I didn't really tested the problems

→ Reply
»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

As a tester, the round is awesome!

→ Reply
»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I see more comments from testers than from others, so I am also adding mine to increase the count XD.

PS: Problems are really good and one can look at stack's previous round to see his problem quality.

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

As a discusser of problems while proposal was in review and a tester, please let me participate

→ Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

As a tester, so huge number of the testers...

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

As a tester, I really enjoyed testing this round. I solved some of the most enjoyable problems yet!

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

As a participant, I haven't tested the round yet. Really awesome problems that I enjoyed. I recommend this round for everyone.

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

As a participant its scary to have so many testers, I hope everyone may achieve Δ ≥ 0 :)

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

As a non-tester I can assure the problems are of high quality.

Source:- Trust me bro.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

As a tester and an ex-tester, my assertion still holds true.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think it will be interesting to solve this contest

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    it will be nearly impossible to solve contest by us(whole questions),but yeah we can try to solve 3-4 questions.

    → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

As a tester, it’s a(Good) round ^_’

→ Reply
»
2 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

hope to gain more rating which i have lost in previous two contest.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As a nothing, this is truly one of the best contests.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why rating of previous contest is not updated yet??

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have never seen this many testers in any div2 contest.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Will the rating of educational #139 be updated before #838 starts? If not, rating of educational #139 will be updated based on the rating after #838…

→ Reply
»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Stack and Amurto Round. 🛐
Very excited for this contest.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When ratings will change?

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When ratings will change?

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

After a long time. Best of luck Everyone.

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

RETURN MY RATTTTIIIINNGGGGG

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the Ratings change for this round?

→ Reply
»
2 years ago, # |
  Vote: I like it +52 Vote: I do not like it

2 recent contests, someone can do this Meme

→ Reply
»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

There is a list of allowed languages in the announcement Email:

C/C++, Pascal, Perl, Java, C#, Python (2 и 3), Ruby, PHP, Haskell, Scala, OCaml, Go, D, JavaScript and Kotlin.

I don't understand why do you limit the programming languages contestants can use? E.g. why can't I use Rust?

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

    I support you. I myself practice a bit in rust, and there's no reason to exclude it in my humble opinion

    → Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Is Perpetually_Purple suffering from success because now he is not "Perpetually_Purple"?

Spoiler
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Argentina vs France suiii

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

oh no , 1750 points for problem c

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

Hi, I'm new to programming so was wondering, when the contest means it will start at 8:35 AM, does that mean we have to start coding at 8:35? Or can we start anytime after that?

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

    This game is from 8; 35 to 10:35,You can compete at any time during the two hours of the competition, but I suggest you enter at the beginning of the competition, otherwise your competition ranking may be lowered a lot.

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

All the best everyone

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

Good luck to everyone!

→ Reply
»
2 years ago, # |
  Vote: I like it -28 Vote: I do not like it

I think the interactive problem is C 

**Do u agree that ?**
→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hey, Can anyone help me? I am a starter in cp, which div is suitable for me?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +19 Vote: I do not like it

    The higher the Div number, the easier, so Div 4 is the most suitable for a newbie. However, this doesn't mean you should only do Div 4 contests. I encourage you to try ALL contests, but just keep your expectations realistic.

    If you're at a point where you cannot solve even the first problem in Div2 during the contest, try to aim to solve at least the first problem. If you're at a point where you can only solve one problem in Div2 during the contest, then try to aim to solve two problems, or at least try to solve the first problem a little faster and/or with fewer failed attempts. And so on.

    As long as you keep your expectations in check, you should be able to benefit from every contest, as long as you utilize them effectively as a learning experience instead of only trying to hope for a miraculously high ranking.

    But if you have time management concerns, e.g., you can only afford to put aside time for one contest in the next few days due to being busy with other work, then you should probably just stick with the easier contests for now, i.e. join the Div3 in a few days instead.

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

    Div2,3,4 is suitable for you. Participate on those divisions contest regularly.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to get to cyan :(.

→ Reply
»
2 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Interactive problems, the worst thing that happened to Codeforces.

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

    You can't just say it's bad because you are not strong enough to solve it :D.

    → Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

It's better to take a break from prime-factorisation problems this time

→ Reply
»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Good DP in Problem C

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

    As I said good DP, in Problem C

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

      You are not supposed to reveal any information during the contest.

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

        I didn't write this during the contest, it was before;)

        → Reply
»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Yeah binary strings are so fun that I cant stop enjoying them

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It was cursed for me :(

→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

difficult round (•_•)

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping for a color change to cyan :-) Let's see

→ Reply
»
2 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Div.1 + Div.2... Not enjoyed this one tbh...

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Is there randomized solution of D or something else?

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

    I try to use the conclusion that 0 is the only number that leads to distinct gcds when gcding with other numbers, but failed.

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

    You can take three pointers i,j,k (initially 1,2,3) and ask query for i,j and j,k and say u get the input as x and y respectively. If x>y, you can increment k to max(i,j,k)+1, else, if x<y then i = max(i,j,k)+1 else j = max(i,j,k)+1. So in every two queries, you are discarding one element of the array for which you are sure that it isn't equal to 0 and you have to dicard n-2 elements in total, so this will take a total of 2(n-2) queries.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Cannot come up with D and I'm about to get negative delta

any idea?

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

    query for(1,j) where 2<=j<=n and if(p1==0 || p1>=(n+1)/2) we can solve

    let query(i,j)=gcd(pi,pj)

    else we know p1=max(query(1,j)), if p1>1, we can deal with {j|query(1,j)==p1}

    but if p1==1 what can we do next

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

    You can see here.

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

      Oh I see thanks

      I only thought about "how to find a number >=(n+1)/2 in n queries"

      However the answer is "how to find a number !=0 in 2 queries"

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

    also I think interactive problem should appear at least E...

    D is a little bit early

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i don't know why my D is wrong i am so frustated :( debugged for almost an hour but could not find mistake!!

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

    Similar. I have theoretical proof for time limit and correctness of my algorithm which means i made some stupid mistake in code and just could not debug it ;-;

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

      That's because the first number you picked can be 1 in which case the list of potential indices will reduce only by 1 instead of being divided by some number >=2.

      → Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

DEFG are too hard. :(

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hint for Problem D?

The best I could come up with is the observation that 0 will never give the same GCD against two different values (a property that only 0 has), but I couldn't figure out how to hunt 0 down from there...

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 4   Vote: I like it +35 Vote: I do not like it

    you take 3 indices a, b, c:

    if gcd(a, b) == gcd(a, c), it means that a is not 0, thus you remove a.

    if gcd(a, b) > gcd(a, c), it means that c is a "divisor" of a, thus you remove c.

    if gcd(a, b) < gcd(a, c), it means that b is a "divisor" of a, thus you remove b.

    you make 2 queries for removing 1 element, total number of queries equals (n — 2) * 2

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

      Thanks bro

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

      nice solution !! it seems so simple and you explained in 3 lines!

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

      let a=24, b=18 and c=20 then gcd(a,b)>gcd(a,c) but c is not a "divisor" of a. I guess the actual reason is since gcd(a,c)<gcd(a,b), it implies gcd(a,c)< a hence c is not 0 and can be removed.

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

        you're right, I didn't know what to call it. I came with that Idea from the fact that if b is 0, the gcd will always be greater. So the real reason would be if gcd(a, b) > gcd(a, c), it means that c is not 0.

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

    one obsrvation is that for A[i] > (n/2) -->it give gcd = A[i] for two places himself and with 0 two indicies for this can be found in O(n) iteartion

    This only if choosen is >(n/2)

    → Reply
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

whenever, there are too many testers saying the round is one the most interesting rounds. Don't take them seriously.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I really not seeing something, or is C really addition of nC0 + nC1 + ... + nCk, where k is the amount of '0' or '1' depending on the last digit? If that's the case, how can I calculate it in O(n) or O(n log n)?

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

    It's sum of 2^(number of continuous digits in suffix) for every i

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

    I did it using dp. if s[i] == s[i-1] , dp[i] = dp[i-1]*2 else dp[i] = 1.

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

      I also did DP but with memoization

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

      why dp[i]=1,it should be dp[i]=(all possible current arregments)-(dp[i-1]*2)

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

    No, it's a lot simpler.

    Let's say you have a prefix of $$$k$$$ 1s. Then every extension is valid, i.e., there are $$$2^{k - 1}$$$ possibilities. You can watch for the chain and double the number of possibilities at each step. A prefix of $$$k$$$ 0s is symmetric.

    But now, let's say at some point the string changes, e.g., from 1 to 0. Up to the 1, the majority must be 1, so in order for the majority to change to 0, the next value must be 0, and there is only one possibility. This resets the chain. If we follow it up with another 0, we are now back to having the freedom of 0 or 1 in between, so the chain (which we just reset) now grows in the same way as before.

    tl;dr — separate the string into blocks of 0s and 1s. For each block of length $$$k$$$, add $$$2^{k - 1}$$$ to the answer.

    My submission: 185325238

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

      facepalm I read the question wrong and thought that a good substring only need the final median to be good... Then I started to look at Pascal triangle and all those stuff...

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

        Feels good that I am not the only one who did it. :(

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

        I just made the same mistake and misread the problem statement and tunnel visioned... I was also wondering how to solve for nCk sums fast. I guess I should learn to read problem statements more carefully

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

    I also stuck here :)

    → Reply
»
2 years ago, # |
  Vote: I like it +26 Vote: I do not like it

It's too hard. Div.1 + Div.2?

→ Reply
»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

The problems are good, but my condition is not good. I have used more than 1 hour thinking about strange algorithms, which lead to insufficient time to finish F.

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How do you solve D? My idea ( that almost solves it) is to keep track of candidates. Take a random number and check gcd with all the caniddates. The new candidates will be the caniddates with highest gcd because they are the multiples of the inital number (and dont add the inital number to the new candidates), and since zero is a multiple, it will be among the candidates. The number of candidates at worst case decreases by half so the number of queries is n * (1/2 +1/4 +1/8 ...) < 2*n. The only problem is when we happen to start with one. Then we get another n queries and we make 3*n queries.

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

    I found one approach which keeps a track of exactly 3 candidates each time and asks 2 queries to eliminate one; you can use this as a hint or check here.

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    I did this solution and solved the problem with 1 by first picking two indexes and checking them with every one else (in random order) "in parallel" (i.e. gcd(x, 0), gcd(y, 0), gcd(x, 1), gcd(y, 1), gcd(x, 2), gcd(x, 2)). The moment I get the first non-1 I know that this was not "1" and continue as you described.

    By randomizing index order the expected number to get the first non-1 seems to be "quickly enough", though I'm not sure what are the actual odds (i.e. if we happen to randomly pick x = 1, y = 2 and then the ordering happens to try to check it with 2, 4, 8, 10, ... first it can probably break). But it just passed final tests, so I guess it's fine.

    → Reply
»
2 years ago, # |
  Vote: I like it +32 Vote: I do not like it

DDDDDDDDDDDDDDDDDD!!!!!!!!!!!!!!!!!!!read 1 or -1???!!!!!!!what!?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The judges were very kind

→ Reply
»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

→ Reply
»
2 years ago, # |
← Rev. 6   Vote: I like it +18 Vote: I do not like it

Here's my solution for D

Maintain a list of potential index that could be 0, let's call it v, query v[0] against v[1], v[2], ..., v[v.size() — 1], we can see that if query(v[i]) = max(query(v[1...v.size() — 1])), v[i] can either be 0 or multiple of v[i], remove all v[i] != max(query(v[1...v.size() — 1])), repeat

If there is exactly 1 query(v[i]) = max(query(v[0...v.size() — 1])), let's call that v[i] is vmax, then either v[0] or vmax is 0

Run this until size of v is <= 2, we have our answer! Also, if gcd(v[0], v[1]) = gcd(v[0], v[2]) = 1, v[0] couldn't be 0, so remove it

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

    what do you do when v[1] is 1? wont you make n queries without narrowing down the potential indices? couldnt figure out what to do when the first element is 1 :(

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

      you can remove 1 from the first 2 queries

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

        You don't really remove the 1 this way. But it works nevertheless

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

          Why swishy123's exact solution is failing on test case 26. May be some new test cases are added.

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

            wait, so i just got EXTREMELY lucky lol, i think the new test cases is the test people managed to hack others with

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

              I don't get why your idea doesn't work. You keep discarding one element with two queries until you find an element that is not one. Say you have discarded m elements. The total number of queries your code will make is 2*m + 2*(n-m) = 2*n

              I fixed my code with your idea (I didn't know how to get an element that is not 1 during the contest) and it gets AC. 185457951

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

    I did it but got WA on pretest 5. Just could not debug the code the whole contest ;-;. Edit — Actually got query limit exceeded.

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    \worst case, queries = n + n/2 + n/4 + ...

    → Reply
»
2 years ago, # |
  Vote: I like it -17 Vote: I do not like it

A -> D is pretty easy :D but dunno why my F is RTE >:(.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

fast coding forces be like

→ Reply
»
2 years ago, # |
  Vote: I like it +60 Vote: I do not like it

Why not prepare this contest as div.1+div.2? I think it is too difficult for div.2. Or maybe arc is anothor good choice, Uh?

Afterall, problems are nice.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wasted a lot of time trying to solve D before even seeing C, but great round with interesting problems nonetheless.

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

    I found D easier than C and solved it before problem C. Or at least it's more beautiful

    → Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

this guy https://mirror.codeforces.com/profile/jiangly is amazing. Solving problems within 1 minute.

→ Reply
»
2 years ago, # |
  Vote: I like it -7 Vote: I do not like it

A really great round with good problems !

Thanks a lot!

I hope all the upcoming December contests would be like this :)

→ Reply
»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

What? A contest without successful hack? Maybe problems are too hard and no one has extra time for hacking?

→ Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Awesome num theory forces.

→ Reply
»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

What was the idea for problem E? Was there a combinatorics formula or some constructive algorithm?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    For a fixed tree the weights are also fixed. The proof is to just delete the leaves until the whole tree is deleted. In fact, $$$n$$$ has to be even. Otherwise, the tree is impossible and the answer is $$$0$$$.

    Now we are interested to find $$$\sum d(u,v)$$$ over all ordered pairs $$$(u,v)$$$ ($$$u \neq v$$$) for a fixed tree. After rooting the tree you can get a general formula that depends on subtree size of each node and their parities. The formula is easily extended to hold for all trees of size $$$n$$$. (Of course, the final answer has to be divided by $$$n(n-1)$$$ )

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

      What do you mean by a fixed tree?

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

        The tree (a set of currently unweighted edged) is given in the input and the task is to assign weights so it's good. I claim that at most one valid assignment exists.

        → Reply
»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

The key idea of problem D is to delete non-zero but not to find zero. After I saw the accepted code I got the idea immediately but it is difficult to change the direction while the round is running. I tried to delete 1 all the time on the round and thought about many ways including random, but it seemed impossible to make the probability small enough to pass the problem. Has anyone passed this problem with a random method?

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

    This method works with very high probability :

    Notice that if you query(x, y) for all y with a fixed x, either p(x) = 0 or p(x) = maximum answer to a query. If you let k be the maximum answer to a query, you can notice that you only need to look at multiples of k, and multiples of k are exactly the elements that answered k to the query. Thus, you divided the number of elements by k doing that. This is almost enough to solve the problem, except if the first element you pick is one, and you're gonna use almost 2n queries before dividing for the first time. To avoid that, you can just ask random pairs until you find an element > 2 and start dividing with this element.

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

      Interesting, this is way easier, but I thought using randomness in the beginning wouldn't work, especially with small permutations, so once I realized the problem of picking 1 as your first number I followed the approach of comparing the first and second elements with each of the next elements until I got a gcd different than 1, since both can't be 1. Then you apply the normal strategy with the remaining elements and since you eliminated one number for every two operations I'm pretty sure this should work, although I haven't been able to get AC yet.

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

      How do you check if, in any iteration,p(x)=0?

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

        if p(x) = 0 then the maximum gcd is the maximum element left so only two elements are leftover and you are finished.

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

          I was saying if my x is such, that p(x) = 0, and elements left in the array are [0,2,4,10] then my answer for queries will be [x,2,4,10=k], from this how to determine whether p(x) is 0 or not?

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

      I tried this approach (just participated virtually now), and it does not work, instead of choosing a random pair I choose a random Y from all multiples of a X, but pretest-5 is evil. :(

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      I thought about the same method as you described. But in my caculation, valid pairs(gives gcd(a_i,a_j) > 1) only takes about 2/5 in all pairs(C(n,2)) which means we need to do about 20+ times queries to find such a pair with a not-found porbability around 1e-9 and then we need to do at most 2n(n + n/2 + n/4 + ...) times queries in worse case to find the answer. So on the round I thought it is difficult to pass the problem especially for small n like 7 or 8. I cannot give a solid proof of this method but it is true that the real process has a very low probability to enter the worst case(we pick k as 2,4,8,...).

      → Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I spent about ten minutes to figure out that you should read a 1/-1 after each testcase in problem D.

I bet there's people who spent more TAT.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$D$$$ looks like author typed something randomly, then suddenly noticed, that this produces "something meaningful", and created problem, which asks to get strictly that "something meaningul".

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

    Well, just to make it clear initial version was to find the whole permutation using atmost $$$3n$$$ queries, which is quite natural and cool imo.

    Testers found it hard and some unintended solution which uses around than $$$3n+\alpha$$$ (where $$$\alpha$$$ varies from $$$30$$$ to $$$40$$$ depending on implementation) were getting cheesed. That is why we decided to have current version. Most of the testers liked it. So we went with current version.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

My solution to D 185365086 (idea is to take any number and querying it with other valid elements to try to get a higher GCD) shouldn't work but I was able to make it AC through randomization and just running an infinite loop when I am about to exceed total queries so that the system rejudges my submission.

Can anyone try to hack this?

(Edit: Cleaner version 185377734)

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

    Very Clever Solution orz

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

    Errorgorn had warned us about this loophole. That is why we had high number of test cases initially.

    Interaction was taking a lot of time, so we had to reduce the number of test cases.

    Good job btw (:

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

    Wait why the infinite loop does not giving TLE, it's cool hack can you explain lill more about running this infinite loop and system rejudge thing.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what's the idea behind B

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

    an easier provable idea: make each element a power of two. The power of two is always found between n and 2n. And it is obvious that if all the numbers are powers of two, then in each pair someone divides the other

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Mathforces!

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

$$$D$$$ was great. Maintain two possibilies, $$$poss[0]$$$ and $$$poss[1]$$$ as the "possible" indexes where $$$0$$$ can be present. Initially $$$poss[0] = 1$$$, $$$poss[1] = 2$$$. Let $$$ g = gcd(p[poss[0]],p[poss[1]]) $$$. (Use the first query to determine $$$g$$$ initially.

Then, start with index $$$3$$$. (And now we need to update $$$poss[0]$$$ and $$$poss[1]$$$).

Calculate $$$gcd(p[poss[0]],p[3])$$$ and $$$gcd(p[poss[1]],p[3])$$$ and $$$gcd(p[poss[0]],p[poss[1]])$$$ (You have already stored it).

Sort them, lets say sorted values are $$$x$$$ $$$y$$$ and $$$z$$$ where $$$x \le y \le z $$$. It can be shown that if $$$gcd(y,z) = x$$$ and $$$x!=z$$$ and $$$y!=z$$$ then, index $$$p$$$ and $$$q$$$ will be the possible candidates for $$$0$$$ where $$$ p $$$ and $$$ q $$$ are the index among ($$$poss[0], poss[1], p[3])$$$ and no index ($$$p$$$ or $$$q$$$) is common in index corresponding to $$$x$$$ and $$$y$$$. (Index corresponding to, say $$$x$$$ means that the two indexes whose gcd is $$$x$$$.). So update $$$poss[0] = p$$$ and $$$poss[1] = q$$$ if the above conditions are satisfied, otherwise don't update it. Then repeat the process for the next index.

At the end, $$$poss[0]$$$ and $$$poss[1]$$$ are the answers. Link for my submission: https://mirror.codeforces.com/contest/1762/submission/185373278 (Solved it just after contest :( )

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't understand outputs of interactive problem debuging enviroment

https://mirror.codeforces.com/contest/1762/submission/185375790

I manualy checked test1 and test2 and both work hmmm?

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

D has a strong vibe of this problem: https://mirror.codeforces.com/contest/1634/problem/D

Not only it asks to find zero, but solutions are very similar too

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why gcd(x,0)=x,is it a definition?

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

I am so sad，my rating will drop，because I have never solved interactive problem，so I always got idleness limite exceed in D，but it is a interesting round.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem B sort the array and make the i+1th index multiples of previous .

Your code here...

	int n = sc.nextInt();
		
		int arr[] = new int[n];
		int cnt = 0;
		for(int i = 0 ; i < n ; i++)
		{
			arr[i] = sc.nextInt();  
		}
		sort(arr);
		
		int ans[][] = new int[n][2];
		for(int i = 0 ; i < n ; i++)
		{
			ans[i][0] = i+1;
			if(i < n-1)
			{
			if(arr[i+1]%arr[i]!=0)
			{
				ans[i+1][1] =arr[i]- (arr[i+1]%arr[i]);
				arr[i+1] +=  arr[i]-(arr[i+1]%arr[i]);
			
			}
			}
		}
		
		System.out.println(n);
		
		for(int i = 0 ; i < n ; i++)
		{
			System.out.println(ans[i][0]+" "+ans[i][1]);
		}

why is it failing anybody

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

    After sorted the indexes are rearranged but you should output the original index

    To fix it you should use pair<int,int> {a[i],i} to store the original index, or let b[i]=a[i]*N+i where N>max(n), then sort b, we can get original index=b[i]%N.

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

On E, I got the AC formula

$$$\sum\limits_{m=1}^{n-1}(-1)^m m^{m-1}(n-m)^{n-m-1}\binom{n-2}{m-1}$$$

but couldn't prove it; can anyone provide some reasoning as to why this works?

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

    How did you figure out the formula during the contest?

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

      I got the observation that, if we root the tree at 1, the label of the edge of each node to its ancestor is $$$(-1)^{\text{subtree size}}$$$. Then, I attempted counting based on $$$n$$$'s subtree, but couldn't really manage the path from 1 to $$$n$$$. Trying to sum over all nodes was a tough task too. I just resorted to guessing after a while, and surprisingly a simple tweak to Cayley's Formula works.

      → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 4   Vote: I like it +23 Vote: I do not like it

    Pick any edge in the path $$$1 \rightarrow n$$$. It divides the tree in two subtrees (let's say that the left subtree contains $$$1$$$, and the right subtree contains $$$n$$$). Then, you can iterate over the size $$$m$$$ of the left subtree.

    • The weight of the edge is $$$(-1)^m$$$.
    • You have to choose $$$m-1$$$ nodes between $$$2$$$ and $$$n-1$$$ to put on the left.
    • You have to choose the shape of the two subtrees.
    • You have to choose the endpoints of the edge.
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I think you also have to choose the endpoints of the edge. You can do this in $$$m(n-m)$$$ ways and that's why the exponents of $$$m$$$ and $$$n-m$$$ are $$$m-1$$$ and $$$n-m-1$$$ instead of $$$m-2$$$ and $$$n-m-2$$$.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B Video Solution And Code (Hinglish)

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Missed being candidate master just for 10 points :'( Thanks for problem D, exactly my favourite type of problem.

Upd: Reached candidate master the next contest!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

4 th test case in c f([1,3])=1 how, extension of 010 can be 00100,01100,00110 hence f([1,3]) should be equal to 3.

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

    It must satisfy the constraints for all of the previous prefixes too. For example, $$$00100$$$ is not considered an extension as for $$$s_2 = 1$$$, the prefix is $$$b[1, 3] = 001$$$. We can we that the median of this prefix is $$$0$$$, and not $$$1$$$ as it should be.

    → Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Ratings updated preliminary, it will be recalculated after removing the cheaters.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Am I the only one who understood the problem C incorrectly? At first, I thought each prefix is an independent case and later I thought even after surpassing a prefix the elements constructed could be changed with new incoming characters.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Can anyone tell me why am I getting Wrong Answer on testcase 2 for my code of problem A:

include<bits/stdc++.h>

using namespace std;

int main() { int t; cin>>t; while(t--) { long long n,i; cin>>n; long long a[n]; for( i=0;i<n;++i) { cin>>a[i]; } long long EvenCount = 0, OddCount = 0, evenmin=9999999,oddmin=9999999,count=0,sum=0,k; long long Even[n], Odd[n];

for(i = 0; i < n; i ++)
{

if(a[i] % 2 == 0) { Even[EvenCount++] = a[i];

}
else
{
    Odd[OddCount++] = a[i];

}
}
 for(i = 0; i < n; i ++)
{
    sum =sum+a[i];
}

for(i = 0; i < EvenCount; i ++)
{
    if(Even[i]<evenmin)
    {
        evenmin=Even[i];
    }
}
 for(i = 0; i < OddCount; i ++)
{
    if(Odd[i]<oddmin)
    {
        oddmin=Odd[i];
    }
}


if(sum % 2 ==0)
{
    cout<<"0"<<endl;
}

else if(sum % 2 ==1)
{

     if(oddmin < evenmin)
     {


      while(oddmin!=0)
      {
          oddmin=floor(oddmin/2);

          count++;

      }
     cout<<count<<endl;
     }
     else if(oddmin > evenmin)
     {


      while(evenmin!=1)
      {
          evenmin=floor(evenmin/2);

          count++;

      }
     cout<<count<<endl;
     }
}






}


return 0;

}

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

    The value of a number is smaller dose not mean it takes less operations to change it parity, like 8(need 3 operations,8->4->2->1) and 10(need only 1 operation,10->5)

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

as not a tester, round was great!

→ Reply
»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

MikeMirzayanov i had received a mail regarding plag. Both are my accounts, i gave the contest with both of my id's simultaneously.

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

    And those 2 upvotes are from your other ids.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ez div2!

→ Reply