chokudai's blog

By chokudai, history, 2 years ago, In English

We will hold AtCoder Beginner Contest 242.

We are looking forward to your participation!

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Cpp20 when D:

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What happened to the judge? It's so slow.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Long queue!

»
2 years ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

for Problem C:

10,11,12

21,22,23

32,33,34

43,44,45

54,55,56

65,66,67

76,77,78

87,88,89

98,99

for n=2, shouldn't the answer be 26 instead of 25(given in question)?

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

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

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve D?

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

    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

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

      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.

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

    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 $$$B$$$. 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 $$$B$$$.

    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 $$$B$$$.

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

»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Today I used Mo's algorithm for the first time.

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

    Same dude, I was able to solve $$$G$$$ because of that, but not $$$F$$$.

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

      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).

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

    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.

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

      +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.

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

    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...

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

      Probably because the time limit was 5 seconds lol

»
2 years ago, # |
  Vote: I like it +32 Vote: I do not like it

How to solve H?

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

    you can write $$$E[X] = P(X> 0) + P(X>1) + P(X>2) + \cdots $$$

    $$$P(X > k)$$$ is just the probability that the process is not completed in $$$k$$$ steps.

    To calculate probability that the process isn't completed in $$$k$$$ steps, We can use inclusion-exclusion. That is P({1} isn't covered in $$$k$$$ steps) + P({2} isn't covered in $$$k$$$ steps) +...- P({1,2} isnt covered in $$$k$$$ steps)-P({1,3} isn't covered in K steps)-... + P({1,2,3} isnt covered in $$$k$$$ steps) + ...

    You can formally write it as : For each nontrivial subset $$$S \subseteq [1,\cdots,n]$$$ , let $$$j$$$ be the number of segments which don't intersect with $$$S$$$, add ($$$(-1)^{i+1}(\frac{j}{m})^k$$$ to the answer. Summing over all $$$k$$$ , we only need to calculate $$$(\sum_{k=1}^{k=\infty} (\frac{j}{m})^k)$$$ for every subset $$$S \subseteq [1,\cdots,n]$$$, You can use a dp to calculate number of ways to select a subset of $$$[1,\cdots,n]$$$ with size $$$i$$$ which have $$$j$$$ segments not intersecting with it.Solution

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

$$$G$$$-Range Pairing Query There is no editorial yet

$$$:/$$$

How to solve $$$G$$$? I wanted to come up with a Segment Tree solution but I failed when I wanted to find all the distinct numbers in range $$$l...r$$$.

PS : Did anyone solved it with Segment Tree? Or it has different algorithm to solve it?

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

    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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E I use digit DP on string. The states are dp[length][prefix_same][suffix_bigger]. Submission

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Does anyone think that F was way harder than G?? I almost took half of my time solving F, but solved G in a few minutes as I knew Mo's algorithm(which was very lucky). Looking at the number of people who solved F and G I guess most people would have felt similarly. Or, is there a simpler solution to F?

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

    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[r_b][c_b][b] \times dp[r_w][c_w][w] \times {n \choose {r_b}} \times {n-r_b \choose {r_w}} \times {m \choose {c_b}} \times {m-c_b \choose {c_w}}$$$ for each $$$r_w, r_b, c_w, c_b$$$.

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

      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

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

        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\times c} \choose k}$$$ and then $$$\forall 1 \leq i \leq r, 1 \leq j \leq c$$$ (excluding (i, j) = (r, c)) subtract $$$dp[i][j][k] \times {r \choose i} \times {c \choose j}$$$ from dp[r][c][k]. Hope this makes sense

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

          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.

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

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

»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

It didn't count for the contest. Makes me so sad, that was the most clutch. It was a last second debugging and panic-submission. [May I get an F?]

But also it was way to complicatly implemented from my side. I though at first this has to be digit DP with some kind of state for the second half of the palindrome. But it was more like the simplest form of Digit DP (means, interpret the first half of the string as a number) plus checking whether the palindrome created by using the first half of the string is valid. If I had just thought about E more, then I guess I wouldn't have had this time problem.

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

    Wow, that must've felt like an achievement and hurt at the same time! Definitely something to talk about, for sure.

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

It seems official solution of Ex is not min-max inclusion and exclusion?

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

hello, I was getting a runtime error when I was running code on vs code for n>=10^5, submssion I didn't submit the code because of this and after that contest when I submitted It got accepted but still got a runtime error for n>=10^5 on vs code. can someone explain why?

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

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve E ?? Please Explain in detail ... ;_;

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why can't I see rankings by country?

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

    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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really nice problems. For me the problems difficulty were F > D > E > G. Did anyone else felt the same way?

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

does anyone know what problem E test case for hack_01.txt is like?

nvm, i forgot to MOD before printing