satyam343's blog

By satyam343, 15 months ago, In English

Thank you for participation! I hope you liked atleast one problem from the set (:

We tried hard to have an interesting problemset.

It is sad to see people disliking the round only because some problems were hard. Please read the intended solutions to know why we decided to put the problems(especially D) at current positions.

1762A - Divide and Conquer

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762B - Make Array Good

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762C - Binary Strings are Fun

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762D - GCD Queries

Idea:amurto Prepared by:errorgorn

Hint 1
Hint 2
Hint 3
Solution
Code

1762E - Tree Sum

Idea:satyam343 Improved by:TheScrasse

Hint 1
Hint 2
Hint 3
Solution
Code

1762F - Good Pairs

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762G - Unequal Adjacent Elements

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code
  • Vote: I like it
  • +240
  • Vote: I do not like it

| Write comment?
»
15 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Great Round!! Indeed, problems were quite hard but doable, but overall a v.good experience!

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

So I solved the problem D a little differently, I tried to make use of the fact that we can always take multible of some number x > 1 and dump all the other elements in the array and zero will always be multiple,

this give n + n / 2 + n / 4 — = 2n queries in total. There is a lot of case handling but You can look at my code to understand it a little better for e.g. if x == 2, than we can just dump all elements except 0 — 4 — 6 — 8 — 10

now the next smallest multiple we can take is 4 than we have 0 — 8 — 12 -16 If we take zero, than all the elements in gcd(pi, 0) will be different hence we can just use zero or pi that gives largest value

LINK FOR THE SOLUTION : https://codeforces.com/contest/1762/submission/185393565

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

    The first step to find a not-1 position costs $$$\lfloor \frac{n}{2} \rfloor$$$ querys. The second step cost about $$$n(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots)$$$ querys. Why the total cost can be limited to $$$2n$$$?

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

      I think we can use a simple idea to deal with the first not-1 position, that is to eliminate not-0 positions as well. You can query (i,i+1), (i,i+2), (i+1,i+2). If they are all ones, you can be sure they are not 0, so remove them from the possible answers, otherwise, you found your first not-1 position. Lmk if I missed anth.

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

        Yeah, as I have done that using vector p2,

        for each i, if gcd(i, i — 1) and gcd(i, i + 1) is 1 than this number can not be 1, reason being,

        x, 0, y, now if zero was in the middle, gcd(x. 0) = x and gcd(0, y) = y so max(x, y) > 1 because distinct elements in permutaion, there is this case where 0 was first or last element and you never find any element in middle just use that as edge case and print 1 n

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

          Also the idea that half of numbers are even can be employed. One can query pairs (1, 2), (3, 4), ... until gcd is 1. If there's no such index encountered we can also query (1, 4) and (1, 3) to finally find the index of a number that is not 1 or that is even. Then we put it at first place and find all gcds of it and with all the other numbers, collect stat and leave only those indices that have the greatest gcd encountered. Repeat until we have two numbers left.

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

    i did exact same apprroach but got WA on test 5 can u please help https://codeforces.com/contest/1762/submission/185370228

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

    I used a similar approach and stress-tested it on all permutations of size 10, it passed them all. Not sure what the problem is.

    Here is my approach, I maintain a list of possible indexes which are initially all indexes. In each round, I query the gcd of the first element with all other elements. Now the maximum result I get must be the value of the first element and all of its multiples including 0 must give the same value. I repeat rounds till the number of possible elements becomes 1. If the number of elements giving maximum gcd is 1, then my first element must either be a co-prime to all elements with the maximum gcd element being 0, or the first element must be 0. So I answer with the first element and the element giving maximum gcd.

    Submission link Stress test code

    Edit- I found the error thanks to propane. I am exceeding query limit when the first element is 1

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

      i had exactly same approach and for the exceeding query limit when the first element is 1 i used the fact that if for an index on the first 2 queries it got gcd 1 it cant be 0 so i terminated the process there and deleted this index and moved forward but still query limit exceeded came :(

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

    I also came up with this solution! But sadly i couldn't participate in the contest

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

Problem A can use __builtin_ctz(x) for even numbers or __builtin_ctz(x+1) for odd numbers. link: https://codeforces.com/contest/1762/submission/185402449

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

    can you explain it more?

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

      __builtin_ctz counts the number of trailing zeros of the number in binary form. To change parity is to change the least significant bit (LSB) from 0 to 1 or vice versa. For example, say we have 11100 (with 2 trailing zeros), two divisions/right-shift operations are needed to change the LSB. +1 for odd numbers to convert trailing ones to trailing zeroes.

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

I really enjoyed this round.

The implementation of the first four problems is quite easy. In this way the problems become purely observational.

Keep up with the good rounds!

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

Intended solution for D is genious.

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

My solution for problem C was a bit different from the editorial. Did that after processing each character I found the number of spaces or free positions where 0/1 may be put that is we have two options for that position. Now we can every time add the 2^spaces to the answer and take respective modulo as well.

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

Can't believe I'm doing this , but alright — I have Idea for D: 1) First we ask n — 1 queries of format ? 1 i, 2 <= i <= n . We will remember all the answers we get

Maximum of all those gcds = a[1], right? Unless all the answers are distinct and are from 1..n-1 — in this case a[1] == 0, and then we can output ! 1 2

Okay, so we know the value of a[1] and we know all the positions j , that gcd(a[1], a[j])==x, for each x

2) Let's take all positions where gcd(a[j], a[1])==a[1] ( we could've remembered this from step 1). For example we have 2, 3, 7 9( it means that a[2] = a[1] * k1, a[3] = a[1] * k2, a[7] = a[1] * k3 ... k[i] is obviously from 0 to (n-1) / a[1]

Now we can just ask another set of questions: ? 2 3 | ? 2 7 | ? 2 9

If any of those gcd(a[2], a[j]) != a[1] then it means either a[2] or a[j] == 0.

As always with guys of green profiles , my code is having WA2 lmao, here it is. Tell me if you can spot a mistake

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

Fast editorial (wtf about #837)

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

Can anyone tell whats wrong with my Submission in D https://codeforces.com/contest/1762/submission/185370228 it would be great help

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

    1 2 4 6 8 7 3 5 0 calculate number of queries for this case.

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

      15 brother with is less than 2*(9) where 9 is the size of array

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

        Actually, in my case, it took 19 queries. `` First I queried the first position with every other element, which took 8 queries. Then I updated the array to [2,4,6,8,7,3,5,0]. Then I queried the first element of the current array (which has value 2) with every other element. This took another 7 queries for me. So the total is 15 queries. I took the elements which gave maximum gcd. So updated array looks like [4,6,8,0]. Then following the same procedure I will query again another 3 times. So the total number of queries is 18. The resultant subarray is [8,0]. So I queried last time before giving an answer which totals up to 19. Maybe you can relate to your code. The idea is just to avoid position 1 when querying with other elements.

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

          ya i avoided the first position actually and moreover I got a wa actually but I checked for many a times but not able to found wa test case

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

Very beautiful problem F! I stand up and applause!

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

I solved F with a different approach.

I made a directed graph such that there is an edge from $$$i$$$ and $$$j$$$ if $$$A_i \geq A_j$$$ and all $$$A_k$$$ between $$$A_i$$$ and $$$A_j$$$ are less greater than $$$A_i$$$. Similarly, I add an edge between $$$A_i$$$ and $$$A_i$$$ such that $$$A_i \leq A_j$$$ and all $$$A_k$$$ between $$$A_i$$$ and $$$A_j$$$ are greater than $$$A_i$$$. So, there are atmost $$$2$$$ outgoing edges from each $$$i$$$.

Now, $$$DP_i$$$ = $$$DP_j$$$ + $$$DP_k$$$ — $$$DP_l$$$ where there is a directed edge from $$$i$$$ to $$$j$$$ and $$$i$$$ to $$$k$$$. But to avoid double calculations, we need to subtract $$$DP_l$$$ where $$$l$$$ is the smallest position that can be reached by both $$$i$$$ and $$$j$$$ using some directed edges.

Now, to find this position $$$l$$$, we use binary lifting technique with binary search. Since $$$l$$$ is the smallest position, you have $$$2$$$ nodes $$$u$$$ and $$$v$$$ such that $$$A_u \leq A_v$$$ and $$$A_u \leq A_l \leq A_v$$$. Hence it is always optimal for $$$A_u$$$ to take the edge such that $$$A_{p_u} \geq A_u$$$ and for $$$A_v$$$ to take $$$A_{p_v} \leq A_v$$$.

Now, we can binary search and find the largest node which is less than or equal to mid and check if - they are same - $$$A_u > A_v$$$ - $$$A_u < A_v$$$ This maximum node can be found by binary lifting technique.

Time complexity — $$$O(N log^2N)$$$ and works fine within $$$3$$$ seconds.

My code

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

What will be the expected rating of the 2nd question?

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

Nice editorial , hints are available for every problem.

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

Can someone explain C? Why suffix though?

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

    Example:

    s = 1_0_1_0_0_0
    f(s) = 8
    how?

    try to find what binary digits can occupy empty places.

    1st empty space : 0
    2nd empty space : 1
    3rd empty space : 0/1
    4th empty space : 0/1
    5th empty space : 0/1

    So the longest suffix with the same digits in the original string only accounts for the number of ways to fill the binary digits in empty places.

    Also, try to work out for this case:
    s = 1_0_1_0_0_0_1

    You will observe that, because of the last one in the string, all the 2 possibilities (0 / 1) in previous empty places change to 1.

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

      Wow! Good Explanation. Thanks man

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

      but why longest suffix and not any other idea

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

        try working out the examples , you will get an idea

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

I am not getting Problem C solution can someone explain it.

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

Satyam_343 is legend!

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

Problem B solution is so nice!

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

Explanation for the observation about suffixes for C

  • forget about prefixes of s. Lets see how many good-extensions exist for a string $$$x$$$.
  • For any extension (say) $$$x'$$$ of $$$x$$$ to be good, every odd-length-prefix of $$$x'$$$ must also be good.
  • Any odd length prefix, will have the frequency of median character = $$$1/3/5/7/ \dots$$$ more than the frequency of the other charcter. I mean, frequency difference has to be odd. (because, again, odd-length-prefix and a binary string).
  • Noticed that if the odd-length prefix $$$x'$$$ is "good" and the last character of the next odd-length prefix is the same as this "good" one, then there are $$$two$$$ options to fill that intervening position between them. (There's a single intervening position between two consecutive odd-lengthed-prefixes.)
  • Most imp: one way of filling this intervening position will end up increasing the frequency-difference by 2 and the other way will not alter the frequency-difference at all.
  • If the relative frequency gets altered, the absolute frequency of the median character will become atleast $$$3$$$ more than the other character's absolute frequency.
  • Notice the situation once there is a absolute frequency difference of $$$3/5/7/\ldots$$$ and the next odd-lengthed prefix ends at an "unlike" character.
    The "single-intervening-element" between the current and next odd-lengthed prefix will not be able to salvage the situation and cover-up a gap of $$$3/5/7..\dots$$$. It can only cover frequency gap of $$$1$$$.

Finally: This means you can use both two options of filling the intervening position only when you can trust that you don't have any upcoming odd-lengthed prefix that ends at an unlike character. In all other cases, there is actually only one way of filling up the intervening position.
Only when, you know that the entire suffix of $$$s$$$ from this point on contains "like" characters, can you start using the other "second" way of filling up the intervening position.