chokudai's blog

AtCoder Beginner Contest 206（Sponsored by Panasonic） Announcement

By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 206（Sponsored by Panasonic）.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

Comments Comments (27)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do F ?

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

    We can assign Grundy values to each game. Let's denote $$$g(x, y)$$$ as the Grundy value corresponding to the game where all intervals lying entirely in $$$[x, y)$$$ are considered. We find:

    $$$ g(x, y) = \text{mex over all values }g(x, l_i) \oplus g(r_i, y) \text{ where }r_i \leq y\text{ and }l_i \geq x. $$$

    Alice wins if $$$g(1, 100) > 0$$$ otherwise Bob wins.

    Code

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

      Hey, just a small request...

      I tried to solve F (https://atcoder.jp/contests/abc206/tasks/abc206_f) by DP.

      This is what I tried.

      My understanding for intersecting is, Two intervals A, B are said to intersect if there is atleast one real number x such that x belongs to both A and B. (i.e. intervals which lie completely within each other do intersect).

      With this definition, I tried the following logic. First for each position from 1 to 100 note the end positions of the interval starting from that position. Similarly find the minimum end position of all the intervals starting at or after the current position.

      Then do a reverse dp (states 0, 1 : 0 -> considering all the intervals starting from >= current position, whether the 1st player can win. 1 -> considering all the intervals starting from current position (only this current position), whether the 1st player can win).

      The transition is for all the intervals starting from current position, dp[i][1] = dp[i][1] | !dp[end_position][0]. Then For j from i until the minimum end position -1, dp[i][0] = dp[i][0] | dp[j][1]

      https://atcoder.jp/contests/abc206/submissions/23636854

      I could not think of a case where it fails. Could you please suggest a case where it does not work ?

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

How to use Mobius inversion to find the number of coprime pairs in [L,R] ?

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

    The idea is from this problem, instead of taking input make a array with element [L,R]

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

    You can also use the idea stated here : https://math.stackexchange.com/questions/218890/how-many-numbers-in-a-given-range-are-coprime-to-n

    I implemented this and it works well within time-limits

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

      Btw, what is the upper bound on the number of distinct prime factors of any integer N (something that we can generally assume while solving problems)?

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

    for finding coprime pairs between [L,R] you can iterate over i=[L,R] range and get all factors of i use principle of inclusion and exclusion to get number of coprime with i which lies in range [1,R] and subtract coprime which lies in range [1,L].

    Finding coprime in range using inclusion and exclusion principle link

    Atcoder Solution Link

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

      But how would $$$(R - L + 1) * 7 * 2^7$$$ fit in the constraints. As integer $$$i$$$ at worst case could be a product of at max $$$7$$$ primes.??

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

        it is 10^6*max(2^7,sqrt(10^6)/2) = 5*10^8 which passes in 1.5 sec for me. Definitely it is tight solution.

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

        I guess on average, there are not that many numbers with 7 distinct primes, for instance, the smallest number that is a product of 7 distinct primes is 2*3*5*7*11*13*17 = 510510, so the amortized analysis of the time complexity would be less than that.

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

What's the Idea behind D ?

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

    The idea was to find the sum of depths of all connected components.

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

    Create edges between all $$$s_{i}$$$ not equal to $$$s_{n - i - 1}$$$. The answer is the sum of $$$size - 1$$$ for each connected component.

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

D : Observation + Graph

Make all a graph on all pairs of numbers which are not equal in a string palindromically. i.e. all pairs s.t. : s[i]!=s[n-1-i]

Now find size of connected component and add sz — 1 to answer because we pick a number, and make atleast sz — 1 operations to make all other numbers in that component equal to that number.

Code

E using Mobius :

Idea : Tot pairs — (pairs with atleast one element = gcd) — coprime pairs(apply mobius here)

Corner case : When L = 1 we subtract it twice so we need to add 2*R — 2 once to ans.

Code :

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

For E what I did

Ans=Total Pairs- pairsHavingGcd1- 2*(pairs(x,y)having gcd=x)

  • n=r-l+1

  • Total Pairs = n*(n-1)

  • pairs having gcd1=https://www.geeksforgeeks.org/find-the-number-of-pairs-such-that-their-gcd-is-equals-to-1/

  • pairs(x,y)having gcd=x, iterate for every number(i) from max(2,l) to r-1 keep on adding r/i — 1

  • 1 is subtracted for the pairs having same no. like (2,2)

  • max(2,l) because if we use 1 then it will be subtracted twice as we have already counted it while calculating gcd==1

  • since (x,y) and (y,x) needs to be counted therefore multiply by 2

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

In the last 3 ABCs, the problem F are very educational which is great.

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

Educational screencast. Slow, detailed explanations. Three different solutions for B, two different solutions for D. AC on F during the last minute. HD soon

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

physics0523 when you write a contest, do you try to include physics problems whenever possible? Just curious because I'd love to solve some physics (kinematics based geometry) problems.

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

https://atcoder.jp/contests/abc206/submissions/23628260

pls tell what is wrong in this D sol?

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

    if(find(arr[i] != find(arr[n-i+1])))

    Is this intentional?

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

      Just to check whether they have same parent or not?

      Is there something wrong in it? Can u provide any test case?

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

        Seems like a syntax error. Read carefully. Maybe you wanted if( find(arr[i]) != find(arr[n-i+1]) ) instead of if(find(arr[i] != find(arr[n-i+1])))

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

          Sums up my rating graph... Thank u so much tho...

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

Hey Could someone help me on why i am getting wrong answer on F ? I tried thinking for case on where it would fail but cannot seem to fine.

My understanding for intersecting is, Two intervals A, B are said to intersect if there is atleast one real number x such that x belongs to A and B.

With this definition, I tried the following logic. First for each position from 1 to 100 note the end position of the interval starting from that position. Similarly find the minimum end position of all the intervals starting at or after the current position.

Then do a reverse dp (states 0, 1 : 0 -> considering all the intervals starting from >= current position, whether the 1st player can win. 1 -> considering all the intervals starting from current position (only this current position), whether the 1st player can win).

The transition is for all the intervals starting from current position, dp[i][1] = dp[i][1] | !dp[end_position][0]. Then For j from i until the minimum end position -1, dp[i][0] = dp[i][0] | dp[j][1]

https://atcoder.jp/contests/abc206/submissions/23636854

Could you please suggest a case where it does not work ?

→ Reply