AtCoder Beginner Contest 242 Announcement - Codeforces

We will hold AtCoder Beginner Contest 242.

We are looking forward to your participation!

Comments (47)

• 26 hours ago, # ^ |

  You can't take 00 as a digit in the number.

  • 26 hours ago, # ^ |

    Thanks

• 26 hours ago, # ^ |

  ← Rev. 2 →  

  +3

  For t <= 62, you can imagine finding value on a binary tree. It the ith bit of k is 0, go left, else go right; For t > 62, since we have a tons of leading zeros in k (0000...), we can do binary lifting. Submission

  • 26 hours ago, # ^ |

    You don't even need to do binary lifting for t > 62. I think you can just convert the first character of string s (t — 62) % 3 times, taking the first character after the operation, and then do the procedure you described for t <= 62.

    • 26 hours ago, # ^ |

      Yeah, I over-killed it.

• 25 hours ago, # ^ |

  What I did:

  First find out, which is the letter from the original string, that creates the block in which the char from the query will lie. This is realpos = pos / (1ull << it). Then determine the position inside this block, where the query will be. This is innerpos = pos % (1ull << it). (Special case for more than 63 iterations has to be implemented.)

  Now we know the letter from the original string. We take that as a base BB. Instead of "A->BC, B->CA, C->AB." I will use "A->AB, B->BC, C->CA." now. To account for this change we add the number of iterations to BB.

  Now we need to consider the innerpos. Which letter will be at this position? This hapens to be the count of set bits in innerpos in binary. So we just need to add __builtin_popcountll(innerpos) to BB.

  Then BB is the answer. https://atcoder.jp/contests/abc242/submissions/29884835

• 26 hours ago, # ^ |

  Same dude, I was able to solve GG because of that, but not FF.

  • 26 hours ago, # ^ |

    I noticed that dush1729 solved it quite quickly, so decided to do G before F (which turned out to be not that difficult as well, just some combinatorics and inclusion-exclusion).

    • 26 hours ago, # ^ |

      ← Rev. 2 →  

      0

      Not being lazy paid off. I decided to finish my mo's template after I failed to solve abc238g

      • 26 hours ago, # ^ |

        Wait, it was Mo as well? I used a lazy segment tree from the AtCoder library: 28946126

        • 26 hours ago, # ^ |

          Sorry my bad. I meant 238g.

• 26 hours ago, # ^ |

  ← Rev. 2 →  

  +8

  Yes, that was also exactly my experience! Didn't want E, couldn't F, saw G. Never did Mo before but it so much looked like Mo, so I had to do it.

  • 26 hours ago, # ^ |

    +1, E is such an overused type of problem. I guess it makes sense in a Beginner contest, but still makes me :meh: every time.

• 26 hours ago, # ^ |

  I forgot to change the block size in my first submission in problem G but in fact, block size of 32 ran faster than 750. I don't know the reason why the solution was accepted...

  • 26 hours ago, # ^ |

    Probably because the time limit was 5 seconds lol

    • 26 hours ago, # ^ |

      with block size 32 it ran in 1381 ms and with 750 it ran in 1618 ms

• 26 hours ago, # ^ |

  Just use mo's algorithm. Whenever you add a number to a range, check if the count of the number is odd, and if so add one to the answer. Similarly, whenever you erase a number from a range, check if the count of the number is even, and if so remove one from the answer.

• 26 hours ago, # ^ |

  ← Rev. 5 →  

  0

  You can also do dp[index]dp[index], where dp[i]dp[i] denotes the number of lexicographically smaller strings for index i,1≤i≤(n+1)2i,1≤i≤(n+1)2. Finally, define tt as follow:

      string t = s;
      for(int i=1; i<=(n+1)/2; i++)
        t[n-i] = s[i-1];
  

  If the string tt is lexicographically smaller than ss, or with c++ you can just check if t<=st<=s, add 1 to the answer. submission

• 26 hours ago, # ^ |

  My solution involves two steps, first calculating dp[r][c][k], which represents the number of possible covering of r x c with k rooks of a same color without leaving a row nor column empty, and then the second step was just simply iterating through number of rows and columns for black rooks and white rooks, and adding the value dp[rb][cb][b]×dp[rw][cw][w]×(nrb)×(n−rbrw)×(mcb)×(m−cbcw)dp[rb][cb][b]×dp[rw][cw][w]×(nrb)×(n−rbrw)×(mcb)×(m−cbcw) for each rw,rb,cw,cbrw,rb,cw,cb.

  • 25 hours ago, # ^ |

    I also had a similar solution, but the process of calculating dp[r][c][k] was very complex. I guess it was what made the problem so hard

    • 25 hours ago, # ^ |

      Ah, there was a fairly simple transition between dp states. All you had to do for calculating dp[r][c][k] is to first add (r×ck)(r×ck) and then ∀1≤i≤r,1≤j≤c∀1≤i≤r,1≤j≤c (excluding (i, j) = (r, c)) subtract dp[i][j][k]×(ri)×(cj)dp[i][j][k]×(ri)×(cj) from dp[r][c][k]. Hope this makes sense

      • 11 hours ago, # ^ |

        Thanks a lot for your hints. I didn't find out how to compute dp[r][c][k] during the last 20 minutes, but with your hints, I finally get it accepted after the contest.

• 25 hours ago, # ^ |

  Simple problems of advanced tricks are often easier if you already know the technique.

• 23 hours ago, # ^ |

  You should modify stack size on your local device. Recursion sometimes give RE with not enough stack size.

• 25 hours ago, # ^ |

  Try enumerating the first half of the palindrome.

• 9 hours ago, # ^ |

  Since the last heuristic contest they've experienced server overload (or something like that) so sometimes they disabled ranking page. There also has been postponed contest around last week or two. I assume this functionality is temporarily disabled to cut performance cost, tho I'm not sure.