Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

chokudai's blog

By chokudai, history, 3 months ago, In English,

We will hold AtCoder Beginner Contest 162.

In this contest, available languages are different from usual. Please see the bottom of this contest page for details. (Only Japanese)

https://atcoder.jp/contests/language-test-202001

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

We are looking forward to your participation!

UPD: I apologize for the slow grading. The problem has been fixed during the contest. You'll be comfortable at the next contest.

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

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

Had been waiting for this for so long.

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

I recommend that you check whether your code and library work well before the contest. New languages and a new judge server were already tested in Japanese contests (https://atcoder.jp/contests/language-test-202001, https://atcoder.jp/contests/judge-update-202004 ), but some bugs may still exist.

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

Why only Japanese language?

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

    The page detailing the updated languages are Japanese. The actual contest isn't (I hope)

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

      How to solve D ?

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

        Separate all indexes of R,G,B in 3 separate arrays.From all possibles triples of R,G,B subtract those in which middle index is equidistant from other two. To calculate. Iterate over any two array and find the third no. (that may to the left, mid and right of this pair) which makes these three in AP. Check if the third no. is present in third array. If yes subtract 1 from all triples.

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

        Store the indices of 'R' 'G' and 'B' characters in a map.
        Then the maximum possible answer can be size of 'R' * 'G' * 'B'

        Then take two of those colors at a time and check for those pairs of indices which do not satisfy the 2nd condition :-
        j-i != k-j
        i+k != 2j
        If there are any indexes which violate this rule , reduce ans by 1, ans--;
        Look at this submission for clarity :-
        https://atcoder.jp/contests/abc162/submissions/11867131

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

    Ah shit, here we go again.

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

What are the real names of the problem setters??

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

chokudai is there any Editorial of atcoder's contest available written in English?

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

Good luck to everyone O^O

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

That's really great, that structural binding finally compiles on Atcoder.

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

When will the solutions/code for the problems be discussed or shared? I am new to Code Forces. I really need those to improve. Thanks.

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

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

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

How to solve E ?

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

    Think in reverse. Try to answer question to how many sequences we will get if have gcd each from 1 to k.

    So, for:

    gcd = 1. -> We have N places to fill and we can use any number from 1 to k at all places(N places to fill). Number of ways = k^N.

    gcd = 2 -> we will have k/2 numbers as multiples of 2. so we have k/2 options at each place. Number of ways = (k/2)^N.

    And, similiarly for all gcd till k.

    But wait there is overcounting happening here. Consider while calculating gcd = 2, on choosing randomly we can even get gcd = 4, 6, 8 and so on.

    So what we can do is something like this, for removing overcounting,

    1. gcd = 1 -> gcd1 — gcd2 — gcd3 — gcd4 ... — gcdk.
    2. gcd = 2 -> gcd2 — gcd4 — gcd6 — gcd8 ... — gcdk.
    3. gcd = 3 -> gcd3 — gcd6 — gcd9 — gcd12 ... — gcdk, and so on till k — 1 and,
    4. gcd = k -> gcdk. (No overcounting here).

    So we can just iterate from backwards to make our counting easier. My submission

    I hope the explanation helped you. Ignore my english.

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

      Nicely explained buddy.

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

      I understood the solution till choosing the arrays on the basis of multiples of numbers from 1 to k, and removing the overcounting by subtracting the extra arrays counted for a particular number whose multiples are greater than the number itself but less than or equal to k which are are overcounted.

      But on finding the final answer why did you multiply the count of arrays for each GCD from 1 to k with the number itself?

      $$$ans+=a[i]*i$$$

      where

      $$$(1\le i \le k)$$$
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Total Number of arrays with gcd = k be dp[k]. So it's contribution to answer will dp[k] * k(which is what we are asked to calculate in question)

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

          We had to find the total sum, that's why multiplied the count of array with its GCD to get its contribution. Missed the sum part, that's why asked such a question, my bad. By the way the above explanation of the solution to the problem is great. Did you solve the F problem?

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

      Nice explanation, thanks! Why do we go backwards with the calculation?

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

        Because smaller numbers need to minus larger numbers, so we must first ensure the correctness of larger numbers.

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

      If I'm not wrong , when you considered gcd=1, you are actually taking into account the sequences where gcd is either 1 or multiples of 1, same with gcd 2...and so on with gcd k and not exactly 1 or 2 ... or k because we are considering every possible ways.

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

      Nice explanation!

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

      can you please explain how the gcd=2 terms will be k/2

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

    For each $$$i$$$ there are $$$\left\lfloor\frac{k}{i}\right\rfloor^n$$$ sequences with all elements divisible by $$$i$$$. Now for any function $$$f$$$: $$$\sum\limits_{i=1}^k \left\lfloor\frac{k}{i}\right\rfloor^n f(i)$$$ is equal to sum over all arrays of $$$\sum\limits_{i | \gcd(A_1, A_2, \ldots A_N)} f(i)$$$. Now we just need to pick $$$f$$$ such that $$$\sum\limits_{i | k} f(i) = k$$$. We might know, that Euler totient function has such property, or we can fill array $$$f$$$ with intended value of this sum (in this case $$$f(i) = i$$$) and run the following code:


    for (int i = 1; i <= nax; ++i) for (int j = i * 2; j <= nax; j += i) f[j] -= f[i];
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Isn't $$$O(N^2)$$$ too slow? Do you want to increase $$$j$$$ by $$$i$$$ each time?

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

        Ooooops. It should iterate over all multiples of $$$i$$$ and take $$$O(n \log n)$$$ time

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

          I understood what you meant, just making it clear for readers. Best of luck for div1 round!

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

      can we solve E like this.

      for each i we want to find how many subsequences have gcd exactly i. So every value will be multiple of i (1*i,2*i,3*i..etc)

      let x=k/i

      for any such subsequence there should atleast one value which is equal to i otherwise if everyvalue is >=2*i then gcd will be >i.

      so count of such subsequences = total — none of those values is equal to i

      so count=x**n-(x-1)**n

      will this work i'm getting wrong answer for sample testcases , am i overcounting something?

      upd: Found my mistake

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

      Thank you, sir. Now I got it

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

      Can you please explain your solution through Euler totient function a little more I didn't understand it.

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

I was trying bruteforce of F in O(N*N). But it gave me the wrong answer.

Can anyone tell why this solution is giving wrong answer. Link

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

    Wont N^2 give TL?

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

    I use dp to solve F

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

      we can maintain dp[i][j], j = {0,1}

      Initially dp[2][1] = arr[2] and dp[2][0] = arr[1] (Base Case)

      1. dp[i][1] denotes maximum sum when we are at i and we are picking ith element and floor(i / 2) elements(subset of 1...i such that adjacent element are not picked).

      2. dp[i][0] denotes maximum sum when we are at i and we are NOT picking ith element and floor(i / 2) elements (subset of 1...(i — 1) such that adjacent element are not picked)

      With some work we can fill dp upto n.

      Our final answer will be max(dp[n][1],dp[n][0]) My Submission

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

        for odd i

        dp[i][0] may be just dp[i-1][1]

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

          may be!!!! designing transition can be different

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

            I mean for this dp[i][0] = max({arr[i — 1] + dp[i — 2][0], arr[i — 1] + dp[i — 3][1], arr[i — 1] + dp[i — 3][0], arr[i — 2] + dp[i — 3][0]});

            you can just write dp[i][0]=dp[i-1][1]

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

              what about if we can get max answer with arr[i — 1]

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

      too short to understand,can you give some explanation? :D

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

        since we know already how many elements we have to take i.e N/2 so instead of using N^2 dynamic programming solution we can do it in O(N) by maintaining at each i that we have taken i/2 elements upto now and have maximum possible sum till now, since at each i we have two possiblity either pick that element or don't pick it.

        We have two cases to handle when i is odd and i is even

        1. when i is odd and we want to pick ith element we can build a current state from (i — 2)th and (i -3)rd state because we know we have already calculated answer for (i/2) — 1 element up to (i — 2) and (i — 3) so that after adding total elements become i/2.

        And if we don't pick ith element we have to construct answer so that total element chosen is i/2 and sum is maximum we can construct answer by taking arr[i — 1] and help from states (i — 1),(i — 2),(i — 3) (for arr[i — 1] only these are possibility can you see why???) and also by using arr[i — 2] and help from state (i — 3) (for arr[i — 2] only this is possible). You don't have to consider other elements and states because you cannot build current state having i/2 elements.

        1. Similarly for even but possiblity for even i's are less than that of odd i's you can think about it.
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Your solution might underflow, check the testcase where every value is negative.

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

Video tutorials for this contest

Also, F is this JOI task, which helped me a lot to win the contest

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

    Thanks a lot for your regular videos, just one feedback that audio quality is can improve, but still very helpful!

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

      Yeah, I didn't expect to record now, so my audio quality wasn't the best due to circumstances not under my control.

      But I'll take that in account from now on.

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

        Can you share your solution idea to the JOI problem you mentioned(Candies) ?

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

          I figured out an O(N^2) solution, but I guess it would probably TLE since N <= 200000.

          dp[i][j] means we take j of candies up to index i (1 <= i <= n, 1 <= j <= ceil(i / 2))


          #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; long long a[n + 1]; for (int i = 1; i <= n; ++i) cin >> a[i]; int m = (n + 1) / 2; long long dp[n+1][m+1] = {}; dp[1][1] = a[1]; for (int i = 2; i <= n; ++i) { for (int j = 1; j <= (i + 1) / 2; ++j) { // not choose a[i], choose a[i] dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + a[i]); } } for (int i = 1; i <= m; ++i) cout << dp[n][i] << '\n'; return 0; }
»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

how to E ?

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

    I used Mobius Inversion, don't know if there was an easier solution using symmetry.

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

      wdym by modbius can your share your AC code?

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

      [user:The _Dark_Knight_Rises] Can you please share your idea?

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

I solved problem D in last 2 minutes. Spent almost 1 hour debugging it and found there was an overflow error in my $$$nC2$$$ and $$$nC3$$$ functions. I got huge rush when I saw AC on it!! Wonderful questions!!

https://atcoder.jp/contests/abc162/submissions/11854513

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

    How did you solve D? I put on a naive O(n^3) solution, but i got TLE in 3 testcases.

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

      Naive will fail yes. It's a simple combinatorics/counting question: Instead of asking how many ways there are to find the triplets, ask how many there ways there AREN'T triplets and subtract this number from the total possible set of triplets.

      The total set is $$$\binom{n}{3}$$$ ways since we are just choosing 3 indices from a set of n chars. Then subtract from the total all the ways to make 3 in a row reds, green, and blues which is $$$\binom{nR}{3}$$$ + $$$\binom{nG}{3}$$$ + $$$\binom{nB}{3}$$$. Then subtract the ways to make a double which is $$$\binom{nR}{2}(nG + nB)$$$ ie the ways of selecting two of the same color, and multiply it with any other color. DO this for the other two colors. Then finally we can do a simple nested loop in $$$O(n^2)$$$ time to determine which triples have same width, but we have to make sure that none of these triples have the same color because we already subtracted those (principle of inclusion exclusion).

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

    Did you really need combinatorics for D? I would say, there was easy and simpler solution. Iterate over $$$i$$$ and $$$k$$$ ( such that $$$s[i] != s[k]$$$ ) and find number of $$$j$$$ between them such that ( $$$s[j] = \{'R','G','B'\} \setminus \{s[i],s[k]\}$$$ ).

    Link — My solution.

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

      Agreed, no combinatorics needed. Just needed to precompute prefixes to answer the "number of j between them" queries.

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

    I solved it in O(n^2) using prefix sums of the number of chars

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

How to solve E and F? In E I had an idea to check all possible gcds and find answer, in F I have a dp approach but it works in O(n^2).

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

    Read these:

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

      gupta_samarth I just went through your solution for E, phi[i] gives the count of numbers from 1 to i which are coprime with i. now = expo( k/g, n ) means inserting all the multiples of g in the array of size n . What I don't understand is that why did you do phi[g]*now ?

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

        Read the blogs ( the mobius inversion one, the other is pre requisite ), they explain the problem for $$$2$$$ numbers taking values upto $$$n$$$.

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

    for each possible gcd try to maintain the number of possible arrays , dp[k+1] such that dp[i] means number of arrays which produce gcd=i, now if you try to find dp[i] means each number must be divisible by i(as this should be the gcd), so each number can be [i*1, i*2,i*3.....i*(k/i)] number of possibilities are k/i but these possibilities may also produce GCDs which are multiple of i (for eg if you took each element as i*2) so to get the exact number of sequences which produce 'i' as gcd you mustremove the count of sequences which exactly produce i*2, i*3 and so on. you can do this using dp just iterate the dp backwards

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

    you can optimize O(N^2) solution to O(N*sqrt(N))....

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

    A problem similiar to E. The only difference is we have one array here and not $$$k$$$$$$n$$$.

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

    You can refer this link for a solution on F.

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

I tried to do C in O(n) but failed , can someone tell how to do C in O(N). My logic was if we fix smallest element say i and then account for it's multiple which will be k/i. That will always give gcd as i. and for rest cases it will contribute only 1.

Can someone point out cases which i missed. Code : https://hastebin.com/manoyebudu.m

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

any one able to solve D,E part of todays contest?what approach has been used

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

Solutions : D : Iterate on the L,R boundaries of the sequence, maintaining the count of each character in the boundary and if s[L] != s[R], add number of indices that have characters different from both of them to the answer and subtract 1 from it if(L == R(mod 2) and s[(L+R)]/2 == required character ). Time Complexity : (N^2)

E : Simple implementation of sieve. For each i, say number of sequences of length n is f(i) that has gcd = i, then f(i) = (floor(k/i))^n — (f(2*i) + f(3*i) + f(4*i) .... f(i*(floor(k/i))), calculate it from backwards.Time Complexity : O(KlogK)

F : It is easy to observe that gap between consecutive elements cannot exceed 2 or 3, but to be on safe side, lets make it 10. So we can make a dp[i][j] denoting the maximum answer if the sequence ends at index i(taking it) and (ceil(i+1)/2 — j) is the length of the sequence for this answer.It is easy to calculate it via contribution technique.Say before i we take j (j>i-11), and at j we take state k, then a possible transition is dp[i][ceil(i/2) — (ceil(j/2) -k)+(i-j-1)] = max(dp[i][ceil(i/2) — (ceil(j/2) -k)+(i-j-1)] ,dp[j][k] + arr[i]).Don't forget to initialize a possible starting state for each i, ie, dp[i][i] = arr[i] for all possible i. Time Complexity : (n*fac*fac), where fac is around 3-4 for optimized solutions.

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

    In problem E, does it make a difference if we calculate it from backwards? I was not able to get the right answer by summing from 1 to k.

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

      Yes because for f(i) we already need to know f(2*i) and so on already.If you get confused at any time about iteration, just do memoization dp.

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

I am new at Atcoder, after what time of the contest are the ratings shown?

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

my solution for F, don't know what is wrong , for me this should work, could anyone help me in figuring out where i am wrong https://atcoder.jp/contests/abc162/submissions/11855696

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

Instant editorial:

A: Just implement. I scanned in as a string to make it easier B: Implement . Use the modulo operator to check for divisibility, a % b == 0 if a is divisible by b C: Implement, just brute force using a triple nested for loop, using Euclid's algorithm to find gcd(i,gcd(j,k)) in O(n^3 logn) time D: Keep a prefix sum of the number of appearances of 'R' in subarray [1,i] for all 1<=i<=n. Do the same for 'G' and 'B'. Now brute force over all (j,k), and one can easily calculate all triples.

E: Let a[i] be the number of tuples with gcd i. Observe that if a tuple has gcd a multiple of i, then all elements of the tuple must also be multiples of i. Let p(i) = number of multiples of i that are <= k. The number of tuples with gcd i can be simply calculated by p(i)^n — a[i*2] — a[i*3]...

We can calculate each a[i] from i = k to 1 in that order.

Calculating each a[i] takes O(k/i) time. Via the harmonic series upper bound, this means that across all i from 1 to k, this method will take O(klogk) time.

F: This is some nasty case bash. First we should calculate a prefix sum for all odd indexed numbers and even indexed numbers.

If n is a even: then either you take all odd indexed numbers, even indexed numbers, or there is a single gap of two. It is enough to consider these cases and to brute force all possible gaps.

If n is odd, then you either don't take either endpoint, you take both endpoints, or you take one of them.

If you don't take either endpoint then there is only one choice: all the "middle" elements.

If you take exactly one of the endpoints, there will be one gap of two or three. Brute force over all the O(n) possible gaps

If you take both endpoints, then you may have two gaps of two or one gap of three. Brute forcing over the O(n) possible gaps of 3 is fine, but there are O(n^2) possible configurations of two gaps of two. However, suppose our gaps are at location i and j, writing down the expression for the resulting sum f(i,j) will look something like f(i,j) = g(i) + h(j) + c for some constant c, and some functions g and h. The exact details depend on implementation details I won't bore you with. By looping over it in a specific way, you can keep a running max of f(i) for some prefix i as you iterate over j, keeping in mind whatever precise restrictions you have on i and j.

Thus, an O(n) algorithm is achieved.

More details upon request.

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

Problem in Q.D what is the problem with this code in QUESTION D ? I am getting WA in 2 test cases

int n;
   cin>>n;
   string s;
   cin>>s;
   if(n==1)
   {cout<<0<<endl;continue;}
   if(n==2)
    {cout<<0<<endl;continue;}

   int a[3]={0};
   for(int i=0;i<n;i++)
   {
       if(s[i]=='R')
        a[0]++;
       else if(s[i]=='G')
        a[1]++;
       else
        a[2]++;
   }
   ll s1=0;
   s1=a[0]*a[1]*a[2];
   for(int i=0;i<n;i++)
   {
       for(int j=1;j<=min(i,n-i-1);j++)
       {
           if(s[i]!=s[i-j] && s[i]!=s[i+j] && s[i-j]!=s[i+j])
           {
               s1--;
           }
       }
   }
   cout<<s1<<endl;
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check out the code below and watch out for mathematical overflow.

    s1=a[0]*a[1]*a[2];
    
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E, can someone help me find the bug in my logic? for i : 1 -> k

i = 1,

number of array such that there is at least one 1. -> k^n — (k-1)^n for all such arrays, gcd will be 1.

Now our Integer set reduced to {2,3,4...k}

i = 2,

number of array such that there is at least one 2 out of our Integer set {2,3,4...k} -> T = (k-1)^n — (k-2)^n. for all such arrays, gcd can be either 1 or 2. Number of arrays such that gcd is 2 will be where all elements are power of 2, -> C2 = (k/i)^n-(k/i — 1)^n : Gcd contribution = 2 All the other arrays will have gcd 1 and number of such array is = T-C2.

Continue like this . .

i = k

in the last iteration our integer set will {k}. then number of arrays with this is 1 and gcd contribution is k.

Unable to find my mistake. :( Please help!!

ll fans = 0;
for(int i = 1; i <= k; ++i) 
{
    ll cnt = (pwr(k-i+1,n) - pwr(k-i,n) + mod) % mod; 
    ll a = (k/i);
    ll cnt2 = pwr(a,n) - pwr(a-1,n); // i
    ll cnt3 = (cnt-cnt2+mod)%mod; // 1
    ll tans = (i*cnt2 + 1*cnt3) % mod;
    fans = (fans + tans) % mod;
}
  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I was thinking in a similar way but look

    consider i=2 case according to your formula count of such subseq which give gcd=2 is (k-1)^n-(k-2)^n.

    consider this subsequence {2,2,...,2,3} all 2's except the last one being 3 , this will be counted under (k-1)^n and this subseq won't be counted under (k-2)^n as it won't consider 2 as it's element now is the gcd of {2,2,...,2,3} equal to 2? no right it's 1 so you are counting some extra subseq whose gcd isn't i.

    read my previous comment.

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

      For i=2 case, the total number of arrays possible are T = (k-1)^n -(k-2)^n, out of which some arrays will have gcd 1 and some 2. Your example will be counted in case where gcd is 1 for i=2. Out of T arrays, gcd will be 2 if we have an array with multiples of 2. (2,2,...3) will fall in case where all are not multiple of 2 hence gcd 1.

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

        Sorry I haven't fully read your comment. In your statement u have written that numbe r of subseq whose GCD is 2 is (k/i)^n -(k/i-1)^n its wrong I have done same mistake.think about it write a brute force code to check it and you will know the reason.

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

I have a solution for D using prefix array which may take less than O(n^2) time(I cannot figure out what exactly the time complexity is because I am a beginner now ..) If there is any problem, please let me know, thanks!! Your text to link here...

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

can someone explain dp solution of Problem F.

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

    Here is the explanation of the 1-D dp approach for problem F.

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

For problem F.....

Why is this solution wrong ? I considered that if the number of terms is even, answer is just sum of odd numbered terms or even numbered terms but if the number of terms is odd, we have to skip one extra element i.e. we need to skip two consecutive elements once. Here, dp[i][0] stores if we haven't performed a move where we have skipped two consecutive terms, dp[i][1] stores if we have performed a move where we have skipped two adjacent terms.

    ll dp[n+1][2];mem(dp,0);
    for(int i=1;i<n+1;i++)dp[i][0]=dp[i][1]=-INF;
    dp[1][0]=a[1];dp[1][1]=0;
    dp[2][0]=a[2];dp[2][1]=0;
    for(int i=3;i<n+1;i++)
    {
        dp[i][0]=max(dp[i-2][0]+a[i],dp[i][0]);
        dp[i][1]=max(dp[i-3][0]+a[i],max(dp[i-2][1]+a[i],dp[i][1]));
    }
    if(i&1)
    cout<<max(dp[n][1],dp[n][0]);
    else cout<<max(dp[n-1][0],dp[n][0]);

Please help gazelle camypaper tempura0224 chokudai

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

    nvm found out my mistake, If you had same doubt. Take a look here

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

test cases for f were too weak

7 1 1 1 1 1 1 1 my program was giving output 4 instead of 3 and yet it got accepted

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

FOR JAVA: I can't understand question no. C. I know how to determine the gcd via Euclid's algorithm (I planned to use BigInteger's method gcd(BigInteger a, BigInteger b);

But I am confused about how one determines the number of times you do the sum. Ie. when do you increment by 1, a or b or c? I'm just getting confused by the sequence of adding 1 to a/b/c.

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

    The editorial only explained how to determine gcd of 3 numbers which was not really helpful. To explain further, I do not understand the following pattern:

    gcd(1,1,1) + gcd(1,1,2) + gcd(1,2,1) + gcd(1,2,2) + gcd(2,1,1)+gcd(2,1,2)+ gcd(2,2,1) + gcd(2,2,2)

    For instance, I don't get why you wouldn't just go from gcd(1,2,1) to gcd(2,1,1) rather than (1,2,1) to (1,2,2) first then (2,1,1). I just don't see this pattern. I also don't quite understand how I would implement this.

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

      Hey Athena,

      This pattern you noticed is a clue that nested loops can / should be used. For example:

      for(int i = 1; i<=2; i++){
          for(int j = 1; j<]2; j++){
              println(i,j);
          }
      }
      

      would print out: 1,1 1,2 2,1 2,2

      So, that is why the example goes from 1,2,1 to 2,1,1. Because the loop finished and j goes back to 1.

      As for an implementation, we can use this observation to now loop for 3 values instead of 2. Just add another loop!

      sum = 0
      for i=1...n
          for j=1...n
              for k=1...n
                  sum += gcd(i,gcd(j,k))
      print sum
      

      This loop will generate every possible permutation of our set!

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

Supplementary editorial and sample codes for last 4 problems. More notes "Number Theory for Programming" for problem 5, based on Nisiyama Suzune's blogs and with some extensions.

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

Can Anyone Explain Problem F? In Very Easy Explanation. Like How We Got To This Solution. What is the approach? It Would Be Really Appreciated IF You......

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

Why not give the editorial for English version this time? There is only Japanese editorial

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

Please anyone can explain problem E solution through Euler totient function.

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

Why is O(N^3) TLE for problem D when N~10^3? Shouldn't finding triplets run in <2 seconds?

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

    Why is this solution WA?

    #include <bits/stdc++.h>
    using namespace std;
    #define xfor(i, a, b) for (int i = a; i < b; i++)
    #define ifor(i, a, b) for (int i = a; i <= b; i++)
    #define rxfor(i, b, a) for (int i = b; i > a; i--)
    #define rifor(i, b, a) for (int i = b; i >= a; i--)
    #define foreach(v, c) for (typeof((c).begin()) v = (c).begin(); v != (c).end(); ++v)
    #define all(a) a.begin(), a.end()
    #define in(a, b) ((b).find(a) != (b).end())
    typedef pair<int, int> PII;
    typedef vector<int> VI;
    typedef vector<string> VS;
    typedef vector<PII> VII;
    typedef vector<VI> VVI;
    typedef map<int, int> MPII;
    typedef set<int> SETI;
    
    int main()
    {
        int n;
        string s;
        cin >> n >> s;
        map<char, set<int>> mp;
        long long count = 1;
        xfor(i, 0, n)
        {
            mp[s[i]].insert(i);
        }
        count = (int)mp['R'].size() * (int)mp['G'].size() * (int)mp['B'].size();
        for (auto i : mp['R']) {
            for (auto j : mp['G']) {
                int diff = abs(j - i);
                if (diff % 2 == 0) {
                    count -= mp['B'].count(min(i, j) + diff / 2);
                }
                count -= mp['B'].count(max(i, j) + diff);
                count -= mp['B'].count(min(i, j) - diff);
            }
        }
        cout << count << endl;
    }
    
    
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$10^8$$$ operations take $$$1$$$ second, hence your code is roughly going to take $$$10$$$ seconds!!!