chokudai's blog

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

We will hold AtCoder Beginner Contest 167.

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

We are looking forward to your participation!

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

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

No Comments on this blog . This is strange I guess

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

The contest will start in 2 mins!

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

I wonder where I can find the tutorial after this contest. I am a beginner this is my first time to participate in this atcoder contest

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

    In the Contest Page itself , after the contest AtCoder provides Tutorials for each problem in well descriptive way.

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

      Sometimes editorial in English is not provided promptly after the contest. It is better to have a look in this discussion post after it ends. Many people will share their ideas.

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

        can u send me the link to the atcoder tutorial (at least the Japanese one so that I can use google translate).

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

          In the contest page you will get a tab called "Editorial" whenever its available.

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

Finally!

Full sweep of the problem set (after some annoying debugging on F).

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

F is interesting! get AC at the very last minute!

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

How to solve D? I was getting WA for last 4 test cases.

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

    you have to get length of cycle in component containing 1

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

    find the beginning of the cycle in the created graph (or linked list), as well as the length of the cycle. Then, roughly speaking, take K % (cycle of length) and just traverse the list one more to find the final index.

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

    Do it for 2 different cases k<=n and k>n. Check manually for k<=n and use the idea of cycle for k> n!

    Here is the code

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

      I didn't consider the case where k <= n, so WA on test37. What a pity.

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

    Overflow prob in mod. Was getting same bug until I switched to long longs.

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

    You have to see what steps are repeating, and how many steps are non repeating. store both these kinds of steps. if k<nonrepeating steps just print kth value. if its more than that mod k with repeating steps size and the print the modded kth value. my submission

    my solution is a little messy.

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

    Hint : After a point towns start to repeat themselves periodically and king starts travelling in a cycle. https://atcoder.jp/contests/abc167/submissions/13059179

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

    Simulate the teleportation until you find repetition. Then go and find the first occurrence of the repeated value. The answer will be to travel to the first occurrence and then going in a loop from the first occurrence to last occurrence, for which the answer can be calculated using modulo.

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

    Let $$$f_k(i)$$$ be the town we end up at if we start at town $$$i$$$ and teleport $$$k$$$ times. Then note that for positive $$$p$$$,

    $$$f_{2^p}(i) = f_{2^{p-1}}(f_{2^{p-1}}(i))$$$

    The input corresponds to $f_1$. So compute $$$f_2, f_4, f_8, \dots$$$ using this DP. Then divide $$$k$$$ into powers of 2 and apply the $$$f_i$$$ that correspond to those powers.

    Here's a short implemenation.

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

    I did it using binary lifting...as it was what i got in my mind first but finding cycle length is a great idea(and easier i guess).

    Here is my submission: Code

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

    I have observed most people used std::set and messy implementations to find the starting point of the cycle but you can use a very easy floyd warshall cycle detection algorithm to find it. you can learn about it on the internet it very easy to understand

    Here is my implementation I have heavily commented it at so that you can understand easily

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

    Because there are n towns, accoriding to pigen hole theroy, after n moves, there must be repeated visited towns. So the solutions is: (1) if k <= n, just simulate k moves; (2) if k > n, simulate n moves. If the n-th visited town is x, then the cycle length is n-last[x]. last[x] is the last time x is visited before the n-th move. Decompose k moves into three parts. First n moves, then (k-n)/(n-last[x]) cycles, then (k-n)%(n-last[x]) moves. After the cycles part the king returns to x. So the answer is move from x for (k-n)%(n-last[x]) moves.

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

      For 2nd case(k>n) why I have to simulate n moves? I have to simulate just till I got a city(say X) which has already appeared. so just find previous occurrence of X say it's I. so I should subtract I from k. k=k-i; now take mod. k=k%length_of_cycle; and then traverse from i till k.

      What is wrong with idea?? Can you please point out. I am getting RE for some case because of zero length_of_cycle. Because when i am taking separate case i.e. return if cycle_length is zero then i getting wrong answer instead of RE. But length of cycle can never be zero. I am

      I have been stuck. Please help anyone.my submission

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

        There must be some of by one error... What if k==l.length()?

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

          For k>= l.length()

          You can see in the code{line 45,46,47} I am finding previous occurrence of X (since this is the town which got repeated for the 1st time). say it's index is 'i' then cycle_length= l.length()-i-1; Since cycle/looping start from i so we should subtract the steps before i so k=k-i; and now we will take the mod with cycle_length and then traverse from i till k.

          If I am wrong somewhere please tell.

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

    first find the length of cycle then using bisection you can get the solution one think you have to consider when cycle length is 2e5 overflow can occure because 2e5*1e18 cross long long range ..

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

How to Solve E ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it
    loop k1=0 to k:
       ans+=c(n-1,k1)*m*(m-1)^(n-1-k1)
    
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Why?

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

      c(n-1,k1) part is straight forward: find k1 points to split the whole row.

      In each of k1 + 1 segments, colors must be different. The 2 blocks at either side of each splitting point have same color.

      m is for the first block of first segment, it can choose from all m colors. for the rest blocks of first segment, each one can only choose from m-1 colors since its color must be different from adjacent blocks.

      for the first block of other segment, it has only 1 choice: the same as the last one of previous segment. the rest blocks of other segment are like that in the first segment, each has m-1 choices.

      Hence the algorithm.

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

        why c(n-1,k1)?? ... why not c(n,k1)??

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

          We are looking for the number of ways to choose k1 pairs of adjacent/consecutive blocks out of the total number of n-1 such pairs.

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

          LazyMist is right about it below.

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

          Initially, we want to split the array into (k1+ 1) non-empty segments, so we are selecting elements from first n-1 elements and each selected element represents right borderline of the segment. We will get an empty segment if we allow n elements. See the problem with c(n,k1) :

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

            Bhai ye picture kaise banai?

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

              Online Ms paint, then upload that picture on some image hosting website and finally link that in the comment.

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

        I understand the idea but keep hitting TLEs. How can you computer "n-1 choose k1" efficiently?

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

          use c(n,m)=n!/m!/(n-m)! and precompute and cache x!.

          don't use c(n,m)=c(n-1,m)+c(n-1,m-1)

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

      shouldn't it be (m — 1)^(k -1) instead ??

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

        After choosing k1 pairs, merge them and the problem reduce to: paint these segments such that adjacent segments having a different color. click here

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

          merge with next element

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

            I am sorry i still don't get why are you merging the two things. Dont they need to have different colors. So like first 2 will have same colors m ways and rest 2 will have m — 1 choices , so m*(m — 1)*(m — 1)

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

            Sorry ignore my doubts , i misread the statement, i thought only k should be differently colored. Thanks for the help tho.

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

      Can you please explain what's wrong with my submission, I have done exactly the same thing https://atcoder.jp/contests/abc167/submissions/13111548

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

        count /= x -> WA

        count *= inv(x) -> AC

        where inv(x) is modular inverse of x

        And consider the case when x = 0

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

      (m-1)^(n-1-k1) bro why you do this ans how do you know say you have done k partitions then the multiplications in each block ?

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

        for certain k1, the total ways of coloring equals to the multiplication of ways of coloring in each segment.

        Denote b[i] be the number of blocks in ith segment, thus sum(b[i])=n. 1<=i<=k1+1.

        As I mentioned above, for the first segment, the first block has m colors to choose and each of rest blocks has m-1 colors to choose. thus for the first segment the total ways of coloring is s[1]=m*(m-1)^(b[1]-1).

        for the second segment, the first block has only 1 choice, which is the same as the last block of previous segment. each of rest block in second segment has m-1 colors to choose. Thus for the second segment the total ways of coloring is s[2]=1*(m-1)^(b[2]-1).

        Similarly, s[3]=1*(m-1)^(b[3]-1)...s[k1+1]=1*(m-1)^(b[k1+1]-1).

        So the total ways of coloring for k1 is:

        s[1]*s[2]*s[3]*...*s[k1+1]
        =m*(m-1)^(b[1]-1)*1*(m-1)^(b[2]-1)*...*1*(m-1)^(b[k1+1]-1)
        =m*(m-1)^(b[1]+b[2]+...+b[k1+1]-(k1+1))
        =m*(m-1)^(n-1-k1)
        
  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it +53 Vote: I do not like it

    Here is my approach: Consider we divide the n blocks into p sets of partitions and label them as n1,n2,n3,...,np. We could do it in (n-1)c(p-1) ways.

    Another constraint is the total pairs of contiguous blocks with same color <=k. It means that (n1-1)+(n2-1)+....+(np-1)<=k which implies n1+n2+...+np-p<=k which implies n-p<=k thus we get p>=n-k

    Now for coloring part of p sets can be done in m*((m-1)^(p-1)) ways.

    So simply iterate p from n-k to n and add ((n-1)c(p-1)) * (m*((m-1)^(p-1))) to the answer.

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

      Thanks Ajit.. Nicely explained. Now I am feeling sad that I was not able to solve it during contest .

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

      could you explain why (n1-1)+(n2-1)+....+(np-1)<=k more?:)

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

        Because a set(subarray) of x elements of same color have x-1 pairs of contiguous elements of same color like if [1,2,...x] is a set of elements of same color then we have the pairs (1,2) (2,3) ... (x-1,x) to count which in total is x-1

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

          I have a small doubt in problem statement

          For n=6 m=2 k=2

          2 2 2 1 2 2

          Is this a valid combination?

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

            No, because we have 3 pairs of contiguous blocks of same colour with indices (1,2) (2,3) (5,6) which is greater than k=2

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

        now I got it, Thank you for your help

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

      Can you please explain the m*((m-1)^(p-1)) part ?

      Also ,since we are choosing p segments out of total n-1 segments then shouldn't it be c(n-1,p) ?

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

        We have 'p' partitions where the blocks inside each partition are colored the same with some color. For eg: 1 1 1 | 2 2 | 3 3 (3 partitions and 3 colors with n=7). First partition can be colored with 'm' colors and remaining (p-1) partitions can be colored with (m-1) colors each, as colors between adjacent partitions must be different.

        Also, it's C(n-1,p-1) as we have to choose (p-1) bars (to get 'p' segments) from a total of (n-1) bars .

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

      Nicely explained,can you please explain, (n-1)C(p-1) part like how you get this relation. UPD: Got it.

      1. We are using (p-1) because to get p partitions we have to put (p-1) bars between the n blocks.
      1. We will not do the mistake to choose n because there is no point on putting the bars at the beginning ie behind the first block.
»
3 months ago, # |
  Vote: I like it +77 Vote: I do not like it
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What sorting method works for F?

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

    difference of opening and closing brackets in non-decreasing order

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

      how are you taking care of these cases

      )(

      (

      )

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

        Put all the Open braces at first, and closing braces at last. For )( cases, sort them by https://codeforces.com/blog/entry/77148?#comment-619238 and put in between open and closed braces. If everything works out, put Yes.

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

          Can we re arrange some string ? where is it written in statement?

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

            No, we can't re-arrange a particular string.

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

          can someone explain why this works?

          My idea was to sort according to the minimum of opening-closing bracket at any point for each string. Then to use segment tree to get the string which gives maximum opening-closing brackets in a certain range. I don't know why this code doesn't work. Is the idea correct?

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

            Try this.

            3

            (((((

            ))

            ))))(

            Your method gives No. But the answer is Yes

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

            Every string has a balance of open/close, and a min value, which is the minimum balance where the string can be used.

            ie it looks like '))((((....', then the balance must be 2 before we can use it. We need to consider both properties.

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

          I think this algo is wrong. Consider the following case:

          4
          (
          )((
          ))(((((
          )))))
          

          Here your algo will give answer "No", but the correct answer is "Yes".

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

            Right! That's why we need some hacking phase (and crowdsource some more test cases) :D Thanks for pointing out.

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

            My solution gives wrong answer in few test cases for the same problem. help me. Solution

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

      n00bPanda Can you please tell how did you think of this approach. I mean what was your intuition? Is it a well known problem? And madlad how did you know that this problem requires sorting for sure?

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

    (A.openCount-A.closeCount) - (B.openCount-B.closeCount)

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

What are the difficulties of todays' problems in terms of codeforces ratings?

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

    A,B,C < 1000

    D : 1200/1300

    E : 1500/1600

    F : 2000/2100

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

    My best estimate:

    A — 600 B — 900 C — 1100 D — 1400 E — 1700 F — 2000

    Roughly, the gap in difficulty between the problems was the same.

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

How to solve E?

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

    At most K adjacent pairs can be same. So at least n-1-k pairs have to be different. Let we need to make p pairs different. So it can be done in C(n-1,p)*M*(M-1)^p. Do this for all p from n-1-k to n-1.

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

      Can you explain, how you got the formula?

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

        Choosing p pairs from n-1 is C(n-1,p). If p adjacent pairs are different,there are p+1 parts,where each part has same color. Now,there are M ways to color the first part, all other parts have (M-1) ways.

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

          Hey! Am still not clear with your intuition. Choosing p pairs is fine. But how did you arrive at them being adjacent? Can you please explain your idea?

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

            I try to break it down

            C(n-1,p) => number of ways to pick p items so that it has the same color as the item left to it

            Consider the case of p = 0, all items are distinct then there are N blocks with different color When p = 1, one item has same color with block on left, so number of continuous block with same color becomes N-1. ... go on until p = k so there can be N-p number of continuous block with the same color

            Now to choose the color: First continuous block can be any color M Second until last continuous block segment can only be one of the M-1 color

            Thus, total ways to color block segment = M*(M-1)^(N-p-1)

            Putting it together=> total of ways to color * total of ways to select p items = C(n-1,p)*M*(M-1)^(N-p-1)

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

How to solve E ? Can someone hint me ?

My approach with MLE
My approach with WA
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain approach for problem C.

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

    You can bruteforce for all 2^n possibilies since n<=12.

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

    recursion approch. check all posibilities, cauz constraint is very less(2^12)*12.

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

      do it look like 2d knapsack?

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

        its just all subsequences problem; its rucursion approch u can solve by iterative method using bitmask;

        here is two possibilities either i can take that book or i can leave that book, if i take then dp[j(0 to m]]-=ar[i][j] (after subtracting dp[j] would be the required value).if all required value <=0 that mean we have achieved the question requirment so i just compare with ans in base case

            static int ans=Integer.MAX_VALUE;
            static void solve(int id,int sum) {
               if(id<0) {
                 boolean f=true;;
                 for(int i=0;i<ar[0].length;i++) {
                     if(dp[i]>0)return;
                 }
                 ans=Math.min(ans, sum);
                 return;
        
               }
               for(int i=0;i<ar[0].length;i++) {
                 dp[i]-=ar[id][i];
               }
        
                 solve(id-1,sum+c[id]);
                 for(int i=0;i<ar[0].length;i++) {
                  dp[i]+=ar[id][i];
                 }
                 solve(id-1,sum);
        
            }
        
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the help Ritesh but if the constraint were big then should we use knapsack

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

            no bro cauz this problem does not depend only on x and n, it depend on value of every book algorithm and cost of book and x and k value.so so i think we cant fill dp like knapsack;

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

    M and N were very small, so you were able to brute force and test every possible combination of books bought vs cost.

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

    Use bitmask to consider all possibilities and update the minimum cost if it's valid.

    Submission

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

    With only $$$N = 12$$$ books, you can brute force all possible sets of them ($$$2^N = 4096$$$) and find the minimal cost. An easy way to work with it is to have an integer where $$$i$$$-th bit is set if you take $$$i$$$-th book.

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

    Just use brute force recursion. solution

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

      Hey, thank you for posting your solution. I was going through it. On line 57 you have declared the size of 'cost' (M+1): vector<ll> cost(M+1,0);. Why you have not declared it of N or N+1?

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

        Apologies for not replying soon! The idea of cost vector was to represent the state that recursion tree is in after completing i iterations. So during the ith iteration we have 2 choices

        1. Add the ith row to the cost array

        2. Don't add it

        Now what should be the size of cost? Since we are adding a row to the cost vector, the cost vector should have the same size as the row i.e. no of columns in a row.

        What are the number of columns?

        -> M+1

        Remember that N is the no of rows.

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

          Hey! I was up-solving some other problems so, couldn't find time to go through your comment. Now I understood what you're saying, thank you!

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

    Just a brute force for all 2^N combinations. My solution

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

    I used bf to find all possible combinations of books and printed the valid combination with least price.

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

    The idea is that you can select a certain number of books from n books in power(2,n) ways. Lets say you choose a certain set of books from those n books, then you have to check if those n books satisfy your criteria. The criteria is that those set of books must be able to increase your skill levels in each of those m algorithms above X. Also you store the total cost of buying those set of books. you repeat this for all such combinations and then simply output the least cost

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

    I just used brute force. Try all possible subset of rows using bitmasks. The constraints imply this will fit within time.

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

by when will the editorials of contest be available?

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

    English Tutorials could take up to a week. Japanese tutorial should be available soon. Use use Google Translate, otherwise check here for solution.

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

    english editorial takes usually 2-3 days.

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

    Thanks for your solution but can I solve E with dp ?

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

      There is a O(nk) DP solution but it's not fast enough.

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

        Can u please explain the O(n*k) solution?? I tried solving using dp with segment tree but got WA. I used dp[i] =(i<=k+1?power(m,i):(m-1)* summation(dp[i-k-1] to dp[i-1])

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

          Hey! ujju_sucks I used the similar approach. But instead of using segment tree. I stored sum of previous k+1 elements. But couldn't get it working. Can you please check the approach

          https://codeforces.com/blog/entry/77148?#comment-619369

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

            Hey! I think we misunderstood the problem. The question is asking for adjacent colour pairs across the entire colouring to be less than K. And not for any segment.

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

              Holy shit!!!! I am such a fool

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

                The reaction to realization of truth ..

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

              Hey can you please explain in brief what is wrong with this dp? I am unable to follow your conclusion.

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

                N=8 K=1 aabccdee This is invalid. As total pairs are 3.

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

              I'd been losing my mind for over a day trying to find an example that didn't work.. thank you for posting this lmao

              just as a curiosity, here's an O(n) dp solution to the way we initially understood the problem. I'm not fully confident it's correct, but hey it might be!

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

        Hey! stefdasca You can optimised the DP solution by storing previous k+1 sums. Can you please check the approach

        https://codeforces.com/blog/entry/77148?#comment-619369

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

      I tried to do it with dp but could not reduce states. If somebody has done it using dp, please share the approach. Thanks

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

        My dp complexity is O(n ^ 3), how about you ?

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

    Hey, for choosing x components from n elements, there should be (n-1)C(x-1) ways, right? Then why did you multiply each m*(m-1)^(x-1) element by (n-1)C(x)? UPD: I understood my mistake.

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

When are the editorials posted for these contests?

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

    The Japanese tutorials are usually posted quite early after the contest ends. You might have to wait a day maybe for the english editorial sometimes. But you can always use Google Translate :).

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

A difficult version of D is here: https://cses.fi/problemset/task/1750

Instead of starting at 1, start at a given X and solve the problem.

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

Why doesn't the relative sorting of strings work?

Solution (Wrong on only 1 case)

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

    (

    )((

    ()))

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

    If a string looks like '))(((((...' you cannot use it everywhere. Each string has a balance and a min value of needed balance before that string.

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

Lol, read k adjacent pairs will have the same colors in E.

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

How did you generate all the permutations for C? What I did is, I looped from 0-2^n-1, convert the value to binary, Wherever the bit is set, I push it to a temporary vector and send that vector to fun for solve. Here is what I did. Overcomplicated code How to simplify this?

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

    To check if a bit is set or not, you don't need to convert it to string.

    For example to check if jth bit in X is set or not, you can simple check the value of (x & (1<<j))

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

For F: let's say some blocks have been placed giving total sum ( by total sum, I mean number of '(' minus number of ')' ), equal to prev. Now for all the blocks left, which have a minimum value of prefix sum greater than or equal to prev , select a block having a maximum total sum.This can be done by using binary search and seg-tree.

Is it wrong ? since I am getting WA verdict , not sure if the implementation is wrong or the logic is wrong.

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

    My ideas was also exactly this. It doesn't work for me too :( Can someone give a counter example for this idea?

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

    Try the following test case :

    ["(((", ")", ")))("]

    The correct answer is yes

    EDIT : Formatting

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

    This approach will fail for the following case:

    3
    (((
    ())
    )))(
    

    After taking first string, you should take the third one, but according to your algo, you will take the second one.

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

      My solution gives wrong answer in few test cases for the same problem. help me. Solution

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

    Why "equal to prev"?

    We can use a string at a position if the current balance of open/close is bigger than the needed open brackets before that string.

    To greedyly find a seq we can use all strings with above property, and would use the one with the biggest balance. Since that one gives most oportunities for the next step.

    On each step we need to check if balance is smaller/bigger than needed open brackets.

    But I do not get how to implement this in O(n logn)

    Edit: Ok, did not see that: Every string has a third property, the number of closing brackets which must occour after it. We need to consider this, too.

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

How to solve $$$C$$$ when $$$N$$$ is large?

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

Three test cases are not possible for ques2? what is wrong in my code...

include <bits/stdc++.h>

using namespace std;

define int long long

int32_t main() { int a,b,c,k; cin>>a>>b>>c>>k;

int ans=0;
ans+=a*1;
int x=k-a;
if(x>0){
    ans+=b*0;
    x=x-b;
}
if(x>0){
    ans+=x*(-1);
}


cout<<ans<<endl;
return 0;

}

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

    you missed the case when k<a. In that case answer is just 'k' but your code prints 'a'

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

    Very nicely written pls make of codeforces as well.

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

Can someOne explain me this solution for D

https://atcoder.jp/contests/abc167/submissions/13028277

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

Can anyone told me the problem in this code(Dth Problem), Only partial test cases are working in it

13092124

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

How to do problem C (Skill Up) using DP if the constraints are slightly bigger(like n,m<=50).. Any kind of suggestion is appreciated. Link to the problem is -> https://atcoder.jp/contests/abc167/tasks/abc167_c

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

    Using min-cost max-flow, take n nodes to the left side ( represents books), m nodes to the right side ( represents algorithms), connect a source to all the n nodes in the left with capacity = total understanding it provides for all algorithms, and cost = cost of the ith book. connect sink with all the m nodes to the right with capacity x and cost 0, also for all the n nodes in the left, connect to each of the m nodes with a capacity equal to a[i][j] and cost 0. Now perform min cost maxflow algorithm and for the maximum flow calculate the minimum cost, if the maximum flow is not equal to m*x, then the answer is -1.(maximum flow cannot be greater than m*x since the capacity of all the edges to sink is x).

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

Is there a way to see test cases for Atcoder? My F submission failed on two test cases only, and I wanted to check what the case is. Here is my submission. Algorithm described in short:

  1. Make Pair of elements for each string, (required, total), required saying how many opening brackets are required before this string (based on the minimum of the running total), and total telling what the end total is. Each opening bracket is +1, closing is -1.

  2. Sort the Pairs based on required in ascending order.

  3. In a loop, pick all the pairs which have their required less than the current_sum (initally 0), put it in the priority queue, sorted by decreasing total.

  4. if queue was empty, print "No" else poll one element from the queue.

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

It was my first contest in ATcoder, In the telporter problem I had 51 AC testcases and wondering if I can access the failed testcases? sub1_21.txt and files like that!

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

Can anyone help me with problem C (Skill Up). Problem

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

For problem E, am using following dp approach. Need help in finding the issue with it.

dp[N] = dp[N-0] * nWays + ... dp[n-i] * nWays + ... dp[n-(k+1)] * nWays

- if n-i > 0 then nWays = m-1
- if n-i = 0 then nWays = m
- else nWays = 0

So at any point, I need to maintain sum of previous k+1 dp elements.

Here's the code

#define LL long long

int mod = 998244353;
LL dp[200005];

int main() {
	LL n,m,k;
	cin >> n >> m >> k;

	dp[1] = m;
	dp[2] = (dp[1] * (m-1))%mod;
	if(k > 0)
		dp[2] = (dp[2] + m)%mod;

	LL sum = dp[2];
	int st = 2;
	int cnt = 1;
	for(int i=3;i<=n;i++) {
		LL ways = (m-1)%mod;
		dp[i] = (sum * ways)%mod;
		if(cnt < k+1)
			dp[i] = (dp[i] + m)%mod;

		sum = sum + dp[i];
		cnt++;
		if(cnt > k+1) {
			sum = (sum - dp[st])%mod;
			sum = (sum + mod)%mod;
			st++;
			cnt--;
		}
	}

	cout << dp[n] << endl;

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

    Can someone please point out where am I going wrong?

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

      Did you misunderstand the question? your dp formula seems to be implying that for each contiguous block there can not be more than K adjacent colors. The question is asking for adjacent color pairs across the entire coloring to be less than K.

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

        So as far as I understood the question, maximum amount of contiguous blocks having same colour can not be more than K+1? Am I still interpreting it wrong?

        For Ex: N = 4, M = 3, K = 2
        aaabc, abbbc, aabbc, ababc... are valid sequences
        aaaab, bbbbc are not valid sequences as it contains contagious block of length 4 (>3).
        
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for pointing out. I think misunderstood the problem.

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

I am very new to atcoder (given only 4 contests). Can someone give me an estimate as to what are the equivalent atcoder ratings wrt codeforces ratings??

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

Hello. Can anyone give ideas on how to write a choose function that computes large values of C(c,r)%m quickly? Thanks.

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

What is wrong with my approach? Here is my submission link: https://atcoder.jp/contests/abc167/submissions/13095279. I divide both the strings into pos(total difference positive) and neg(total difference negative). In a greedy approach you place all pos strings before neg strings. Moreover in pos strings you place all strings in non-increasing order of minimal difference. You place all neg strings non-decreasing order of minimal difference. In case of ties you take the one with larger total difference.

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

Most of the times the E or the F problem of the ABC is always related to combinatorics and I am not good at it.So can anyone suggest where can I find problems related to Combinatorics for practice.

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

Can someone explain me what is wrong in my D code?

#include<bits/stdc++.h>
using namespace std;
#define forr(i,a,n)	for(long long int i=a; i<n; i++)
#define loop(i,a,n)	for(long long int i=a; i>=n; i--)

vector<int> v(300000), ans, ans2,ans3;
int vis[300000], vis2[300000];

int main() 
{
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(0);
	
	long long int a,b;
	cin>>a>>b;
	forr(i,1,a+1)
	{
		long long int x;
		cin>>x;
		v[i]=x;
	}
	int k=1,flag=0;
	ans.push_back(1);
	vis[1]++;
	while(1)
	{
		
		if(flag)
			vis[k]++;
		if(vis[k]==3)
			break;
		ans.push_back(v[k]);
		k=v[k];
		flag=1;
	}
	forr(i,0,ans.size())
	{
		if((vis[ans[i]]==2 or vis[ans[i]]==3) and !vis2[ans[i]])
			ans3.push_back(ans[i]), vis2[ans[i]]=1;
		else if(vis[ans[i]]==1 and !vis2[ans[i]])
			ans2.push_back(ans[i]), vis2[ans[i]]=1;
	}
	if(ans2.size()>=b)
		cout<<ans2[b-1];
	else
	{
		long long int x=(b-ans2.size())%ans3.size();
		cout<<ans3[x];
	}
	return 0;
}

This is what I did: I just detected cycle and this is what I did,,,,.. if(k<=nonpartofcycle) cout<<nonpartofcycle[k-1]; .....else{ x=(k-nonpartofcycle)%cycle; cout<<cycle[x]; }

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

please explain what is the error in my code for problem F? https://atcoder.jp/contests/abc167/submissions/13096927

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

    what I did is I remove all the perfect strings such as (()),()(). now if the sum of all the string +1 for ( and -1 for ) is not equal to zero the answer is No. else sorted it according to the difference of (open-close) in decreasing order and then traverse the whole string if the sum gets negative at any point then I output NO else yes.

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

https://atcoder.jp/contests/abc167/submissions/13098882

Can anybody please tell me the error in my code. A test case would be better.

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

My solution for F: is to separate strings into 3 categories that resultant is (,),)(. Then putting all opening at front, all closing in end, and sorting )( according to open_count-close_count in decreasing order and putting in middle. My solution got AC on atcoder but failing on following testcase by giving answer No but it's actual answer is Yes. Here is my solution.

4  
((((( 

)))))(((((((( 

))))))(((((((((( 

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

    r*ndi rona mat kar. AC mil gya na toh khush reh.

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

    Each one of those strings has a property 'leading opening brakets'. It cannot be used at positions where the balance is less than that number.

    So, we cannot simply sort by open_count-close_count, but we need to build a subset of strings with the leading opening brakets less than current balance, and then choose the one from those by using the sorting.

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

how to solve A ?

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

Testcase for F was very weak. AC code: https://atcoder.jp/contests/abc167/submissions/13063944 which fails on the TC:

5

(

)((

)((

))((((

)))))

Answer should be Yes but AC solution gives No.

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

can anybody tell me what is wrong in my submission of d . It is just failing for some testcases

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

for problem B: I cant get the idea why he use it:

if((bit >> i) & 1) {
            price += c[i];
            for(int j = 0; j < m; j++) {
                understood[j] += a[i][j];
            }
        }

I understand that we check all 2^n combination. but how this code helps here? here is the full code: https://ideone.com/9DsLpo

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

My approach for problem F:

  1. Find for each string the final sum(SUM) and the minimal sum(MIN) in that string. Minimum is restrained by zero.
  2. Then divide the strings into four groups. First, those with SUM > 0 & MIN == 0, second those with SUM > 0 && MIN < 0, third with SUM < 0 and fourth with SUM == 0.
  3. Next, we place the strings one after another and maintain CURSUM.
  4. Place the first category in the beginning in any order.
  5. Then we place the second category in order of decreasing MIN. This is because these strings still increase the CURSUM. If at any time CURSUM + MN < 0, we return no.
  6. Then we place all strings of the fourth category. If at any time CURSUM + MN < 0, we return no.
  7. Lastly, we place the strings of the third category in order of increasing MN as these strings decrease CURSUM. If at any time CURSUM + MN < 0, we return no.
    If after this CURSUM is not 0 we return no else return yes.

This gives WA. Can any one give a counter test?
My code

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

Edit : My solution got AC but is not correct (see example below) . I have modified the approach little bit (see my comment below) and now it is giving correct answer for the example below as well.

solution for F : We need to assign each string a weight , sort them in descending order according to the weight and finally combine the strings in that order . Now how to assign the weight ? Let us call number of occurrences of $$$($$$ as $$$O$$$ and number of occurrences of $$$)$$$ as $$$c$$$ . We calculate these numbers for each string individually and then we do following :

code snippet

Reason :we want as may characters of type $$$($$$ in initial part of final string and as many character of type $$$)$$$ in final part. we want strings of type $$$((((($$$ to occur first and strings of type $$$))))$$$ to occur last. Now for string in which $$$o>c$$$ , we put that string first which has least number of $$$c$$$ .Example : we will put $$$))(((((($$$ before $$$)))(((((((((($$$ because let $$$(($$$ occurs before both of them then if we put $$$)))(((((((((($$$ just after it , then there will be unbalance .

Case for strings in which $$$c>o$$$ is symmetric to the case $$$o>c$$$ if we look from right side .

Now for strings in which $$$o==c$$$ , they don't contribute any extra '(' or ')' and thus we put them in the middle . Else they can cause problem . We can build the final string by combining all other strings after sorting and check if it is balanced .

submission : link

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

    Shouldn't the following test case output "Yes"? (by arranging them in the given order)

    4
    (
    )(((())
    ))(((
    )))
    

    I got "No" from your code

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

      Thanks for providing counter example . I have redefined the weights as following : we find number of '$$$($$$' not balanced by '$$$)$$$' and call it o1 and number of '$$$)$$$' not balanced by '$$$($$$' as c1 .For example in $$$)((())))$$$ c1 = 2 .

      code snippet

      Now we want the strings having more number of unbalanced '(' on the left part of final string and the strings having more number of unbalanced ')' on the right part of the final string .The idea is similar to the above comment ,except o1 and o2 are calculated differently.Also for the case in which unbalanced '$$$($$$' are more than unbalanced '$$$)$$$' , we will put those first in which number of unbalanced '$$$)$$$' are less . For example $$$))(((($$$ will be placed before $$$))))(((((((((($$$ . Also $$$))((((($$$ will be placed before $$$))((($$$ . All other cases are symmetric if we see from right side.

      We do that and we check if final string is balanced or not.

      submission

      It got AC as well as it is working on above example given by geeky.ass . I will be very happy if some one provides further any counter example .It also got accepted in almost same problem with better test cases .

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

problem F , need a counter example why my code fails=>https://atcoder.jp/contests/abc167/submissions/13105666

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

Detail explanation and code for C D and E

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

Solution for F.

There are no good explanation in the comments. Also some of the wrong solution are getting accepted with some heuristics link . So I thought I would explain how I did it after 3 hours of struggling. And if anyone can counter my solution you are welcome. I will try to explain form the basics.

Let us first see the representation

For a single String i 1 ≤ i ≤ N

Let an a[N][2] array representing count of -

For String i a[i][0] denotes the maximum value count) in count ) - count ( brackets can reach while we are sweeping from left to right and a[i][1] denote the same for maximum ( while sweeping form right to left that is max count ( - count )

For example (()) -> a[i][0] and a[i][1] will both be 0 , ()) -> a[i][0] will be 1 and a[i][1] will be 0. ((( -> a[i][0] will be 0 and a[i][1] will be 3

If the final string formed after rearranging is T then for it to be perfect for any pos 1 ≤ pos ≤ N we should never encounter difference of count ( and count ) less than zero

Then make two sets of a[N][2]

First set containing a[i][1]-a[i][0] ≥ 0 let us denote it as S1

Second set containing the remaining elements that is a[i][1] - a[i][0] < 0 let us denote it as S2

Sort S1 according to the value of a[i][0] in increasing order Sort S2 according to the value of a[i][1] in decreasing order

Append the second set at the back of the first set

Initial let us denote the difference of ( and ) bracket by S then initially S=0 Sweep right form 1 to N

Subtract a[i][0]form S

check if S is less than zero then print No and return

add a[i][1] to S

If finally S is zero print Yes

Now why this works ?? I'm not sorting according to some difference of value of a[i][0] - a[i][1].

Explanation.

1 ) As you can see in the sorting order of S1 the value of S keeps on increasing it never decreases. This proves the fact that at any point we are using the maximum possible S - a[i][0] to be checked as less than 0 . Because a[i][0] is sorted in increasing order.

2 ) The second part is not that intuitive like why to sort S2 based on a[i][1] in decreasing order. To get the feel of it try imagining doing the same thing we did in the first part form backwards like taking the mirror image of the string we will have to do the same thing we did in the first part for S1. That is why it is sorted in decreasing order of arr[i][1]. I don't have any other way to explain what's going on in my mind other than this for the second part.

3) The S value should be equal to zero I mean that is but obvious .

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

Can anyone explain why this code works for problem F?

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

can Anyone please explain to me the 2nd condition of problem E using an Example?. (adjacent pairs blah blah) I find it confusing.

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

what is the solution for D?

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

    For D,you got to find a cycle(the cycle may not start from town 1) For example, if the given array is 6 5 2 5 3 2, then the cycle starts from town 2 ( 5-->3-->2). So first of all find the starting point of the cycle, and subtract the required number of steps to reach this starting point from k. Now you'll only move within the cycle. Since k can be large, take (k modulo cycle length). Lets say k modulo cycle length is x. Then obviously x<cycle length. So simply perform x steps. The town you land on is your answer.

    Here's my code!

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

For F, I have taken array of pair and for each string given I keep in the array count of left and right braces which are unbalanced , and Then I sort the array considering the count of opening bracket and then considering the closing bracket. And then i took two variables l and r keeping track of opening bracket from starting and closing bracket from ending respectively. I started two fill the l and r from respective two sorted arrays and I think the approach is right because I Have tried almost all the test cases available in this blog for that question but not a single one has failed and also I am getting RE in few cases only not WA so the problem might be of implementation.. Can any one help.. Submission

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

Can anyone please help me in finding the bug in my approach for solving problem D?

https://atcoder.jp/contests/abc167/submissions/13089636

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

Can someone give me a counterexample to problem F? I tried all the counter examples in the comments, but they were all correct, thank you very much! https://atcoder.jp/contests/abc167/submissions/13121322

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

    I still can't find a counter example, I've tried all the cases the comments gave that could be wrong

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

I think the test data is weak in problem F, many solutions got accepted are printing "No" in this case while the answer is "Yes". The test case:

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

    This is problem F with stronger tests: 101341A - Streets of Working Lanterns - 2, enjoy

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

      my code got AC on atcoder

      But WA on test 71 in this problem

      any idea what test 71 looks like ?

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

        Test 71

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

          Thanks got AC now on both

          it turns out that what I have commented was the right xD

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

          Is it possible to allow access to all cases?
          I already got AC, but I have a code that fails on case 45 and I couldn't figure out the bug in that code.

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

            Test 45

            BTW, the generator is very stupid for this problem:

            void GenerateSequence(std::string &out, int len)
            {
                if (len <= 0) {
                    return;
                }
                if (rnd.next() < PARTITION_PROBABILITY) {
                    int position = (rnd.next(0, len >> 1) << 1);
                    GenerateSequence(out, position);
                    GenerateSequence(out, len - position);
                } else {
                    out.push_back(OPENINIG_BRACKET);
                    GenerateSequence(out, len - 2);
                    out.push_back(CLOSING_BRACKET);
                }
            }
            

            then swap / don't swap two random characters, then randomly cut the string to pieces.

            So you can easily stress it locally.

            If someone needs other tests, tell me your Polygon account.

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

              Thanks for the generator, I tried stress testing too, my generator couldn't find the case. Now I will try with this one.

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

      I got AC in both versions with the following wrong greedy: repeatedly append to the whole string the unused string which doesn't make the whole string irrecoverably unbalanced (too many unmatched closed parens), and with the highest number of unmatched open parens among all valid choices.

      The counter case:
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I added your test and some more against your solution

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

i am not able to find what is wrong with my code 4. Teleporter link of my soln is: https://atcoder.jp/contests/abc167/submissions/13078515 please mention testcase at which my code is wrong

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

    First of all you exceed the limited size of your array by one.

    ll a[n];
    for(ll i=1;i<=n;i++) {
      cin >> a[i];
    }
    
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hello

I have a couple questions on Task C and Task D Can anyone please help me with my code by showing me a counter-case?

here is my code for Task C (Skill Up): https://www.ideone.com/dXAF93 I am getting WA for this. I don't understand why...I am sorry.

here is my code for Task D (Teleporter): https://www.ideone.com/83lldq I am getting TLE for this. I thought the longest pattern would be 2*10^5, and maybe I could get to the final destination in time..

Much appreciated in advance.

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

when will the editorial be published?

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

https://atcoder.jp/contests/abc167/submissions/13005847 Can anyone help me to understand what he did in the line 25 to 27??

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

chokudai, is there any chance some day there is different time for any of the AtCoder contest? That is so sad that in our time zone atcoder contests starts at 5am. AtCoder is becoming more popular with the community, so some time rotation would be amazing.

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

For those who is struggling on Teleporter, here's my solution with explanation: https://github.com/wingkwong/atcoder/blob/master/abc167/D.cpp

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

Too weak pretests in problem F, you can solve this problem by len(s) ^ 2.

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

can someone please explain problem statement of E, specifically this line "We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways."

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

Guys urgent...I think 168 clashes with kickstart!!!

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

Atcoder Beginner Contest 168 is clashing with Google kickstart Round C. Please look into this matter.

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

https://atcoder.jp/contests/abc167/submissions/13258356 whats wrong with this solution?? F-Bracket sequencing