chokudai's blog

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

We will hold AtCoder Beginner Contest 135.

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

We are looking forward to your participation!

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

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

LOVE AtCoder's problems! They are always of good quality! :D

UPD: and great difficulty

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

    Free contribution

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

    Another good thing about atcoder is short and to the point problems.

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

How do AtCoder beginner contests compare in difficulty to Div2/Div3?

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

    It's easier than Div3 on problems A and B, but sometimes as difficult as Div3 on problems E and F, the overall difficulty is slightly lower than Div3, personally, I believe it's going to be a interesting contest for people with rating below $$$1450$$$ on CF.

    UPD:I was wrong.

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

    The early problems on Atcoder are much easier than any problems on CF.

    However, in my opinion, the last problem (F) on ABCs is typically substantially harder than the last problem on CF Div3. I think it's harder for me to solve all problems on an ABC (I frequently don't) than all problems on a CF Div3 (I typically do, small sample size though), and since the earlier problems are harder on CF, that implies the later problems are harder on Atcoder.

    In summary, ABCs are definitely easier than CF Div2, but overall harder than a CF Div3 (if you aim to solve all problems). If you're only aiming to do the first few problems, ABCs are easier than CF Div2 and Div3 both (the first problem on last week's ABC was "input X and output 3X^2").

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

      How would you compare ABC's E/F problems to that of CF DIV2 ?

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

        Much easier, though there's been a good amount of variability. I've solved everything on multiple ABCs, but only done that once on a Div2.

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

          I think ABC E is comparable DIV2C — DIV2D

          while F is in between Div2D & DIv2E

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

Where to see the number of people who solved a particular problem during the contest?

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

    on the standing page, the last row called Accepted / Tried
    total # Ac over the overall submissions

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

How to solve F?

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

    Concatenate $$$S$$$ with itself until it has a greater length than $$$S+T$$$. Then, using a string matching algorithm, check which positions in the first $$$S$$$ could be the start of an instance of $$$T$$$. For each of these positions, use the length of $$$T$$$ to figure out which position, modulo the size of $$$S$$$, you'd reach in the concatenated $$$S$$$ after placing a copy of $$$T$$$ starting here.

    Afterwards, the problem reduces to longest paths in a directed graph. Our nodes are the positions in $$$S$$$ and our edges connect each valid position at which we can place a copy of $$$T$$$ to the position at which the next copy of $$$T$$$ would start. If this graph contains a cycle, the answer is $$$-1$$$. Otherwise, we have longest paths in a DAG, which is a relatively standard problem.

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

This is absolutely the most difficult ABC problem I've ever seen...

Do any one know how to solve D? I tried to use a dp but failed.

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

    DP states are idx and current remainder. When idx th character of string is equal to '?' then try all digit from 0 to 9.

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

    We have to use the divisibility rule of 13 i.e the difference of alternate chunks of 3-digit numbers from the unit place if divisible by 13 than the number is divisible by 13. so we have the form of (A*100 + B*10 + C)%13 = 5. Here A,B,C consist of sum and difference of ? which can take values from 0-9. Sorry this is what I was thinking during the contest but the idea was too tough to implement.

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

    Submission

    According to the above explanation.

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

    Let $$$dp[i][j]$$$ be the number of length-$$$i$$$ numbers that match the pattern's first $$$i$$$ digits and are $$$j$$$ mod $$$13$$$. Then, we can transition by iterating over every possible digit in the $$$i+1$$$'st position, noting that appending a digit $$$k$$$ to state $$$(i, j)$$$ gives a remainder of $$$10j+k$$$ mod $$$13$$$.

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

    Actually this was a simple digit dp problem. You should explore some problems like that.

    If you think this problem was difficult, then look into this codechef problem. During contest time I implemented it and got it accepted, I had to use 6-7 parameters to define a dp state. And surprisingly the editorial also used same no. of parameters.

    Another example of digit dp problem: Atcoder Educational dp contest, problem S

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

How did you solve F(if solved)?

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

How to solve problem E?

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

I have solve 58 test cases of Problem F out of 73. Than will i get Partial Score or Not. Means at Atcoder there is any concept of partial Score.

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

I think problem E and F are put in a wrong order. I can solve F but can't E.

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

How to solve problem D ?

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

    DP. States are position and remainder.

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

    Go index wise in the string starting from the left end. Think what will be the contribution of the current number formed till now in the modulo 13. DP[i][j] — stores the number of numbers that can be formed using length up to i and have modulo j with 13.

    Obviously, i -> (0..n-1) and j (0..12) Since mod 13 only 12 values are possible.

    Now If at S[i] there is no question mark then the transition is simple. the new number formed is just the previous * 10 + (s[i]), And we have 12 possible previous so check for all of that. Now do % 13 of this and increase the count of the new mod in i. Otherwise, if there is a question mark just do this for all digits from 0 to 9. And update.

    Finally, the answer is dp[n-1][5]

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

Geothermal please save us

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

I want anand.oza or Geothermal to put up an English editorial.

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

    I won't be posting an editorial today--I was working on one after I finished the contest, but I accidentally hit my backspace key just before I finished, causing me to leave the page and lose all of my work. Unfortunately, I don't have time to write it up again.

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

      No editorial any more?!

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

      It seems that the editorial is already accessible (albeit in Japanese at the moment)!

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

    I didn't participate in the contest this morning, but I'm working on the problems for practice now and might write an editorial (if nobody else has and I actually solve all the problems, haha, but I heard today was a hard round!).

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

Any ideas for E. How to solve it?

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

    Just recursive dp(dp[i][j])

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

      dp[i][j] ?? what dp[i][j] ??

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

        If it is impossible to reach i,j then dp[i][j] will be someting like -1. if not, it will be the minimal number of score needed to reach i,j and the point from witch we went to i,j

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

          what is i what is j. can you give me your submission link.

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

            i and j are coordinates. I think you do not know dp. I have not submited this problem, I can not wrote the code before ending the contest

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

              i and j are coordinates? i and j can be upto 10^5.

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

                Use map for this(with key pair <int, int>)

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

      This will TLE, as $$$X$$$ and $$$Y$$$ can be up to $$$10^5$$$ and your efficiency is at least $$$O(XY)$$$ (or perhaps $$$O(XYK)$$$, factoring in transitions).

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

Is this game included in rating?

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

500 and 600 problems were more difficult this time than general.

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

Geothermal How to solve problem E?

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

    Just recursive dp(dp[i][j])

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

      Anything?

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

        dp[i][j] is if it is impossible to reach i,j(point with coordinates (i;j) then dp[i][j] will be someting like -1. if not, it will be the minimal number of score needed to reach i,j and the point from witch we went to i,j.

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

Can someone tell me why my F is wrong https://atcoder.jp/contests/abc135/submissions/6580972

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

Will you disqualification a user from the contest if he copy pasted other's code Geothermal? rng_58? chokudai? sigma425? I am asking this because I copyed the code from someone and want to know, will you disqualification me?

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

    Dont know about disqualification, but they will tell to improve your english for sure..

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

What is the topic of problem E? It is computational geometry? I would like to know a lot of about this kind of problem.

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

    I solved this with recursive dp: dp[i][j] is if it is impossible to reach i,j(point with coordinates (i;j) then dp[i][j] will be someting like -1. if not, it will be the minimal number of score needed to reach i,j and the point from witch we went to i,j. this may fail in time, so I used rands and probalities and my solution worked with a big chance correct and with a big chance to be fast at test.

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

How to solve C?

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

    I store the total number of monsters in a variable say res.Then I check for each i if B[i]>A[i] then we update A[i+1] with A[i+1]-min(A[i+1],(B[i]-A[i])) because ith hero can defeat some of the (i+1)th position monsters. and for each i we have to update final A[i] value.that is max(0,A[i]-B[i]). Finally we calculate the sum of total number of monsters left say res1. So our answer is (res-res1).

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

      Hi, I know it's been 3 weeks but I've just tried the question today. About the problem, is it a greedy approach? The ith hero attacks the monsters in the ith city as many as possible, then attack the monsters in (i + 1)th city if possible.

      If that's what you meant, then my approach is just the same as you. However, my code got WA on submission. Here's the link: https://atcoder.jp/contests/abc135/submissions/6933616. Can you help me figure out what's wrong? I will try to code as what you stated above as well and see the difference.

      UPD: I figured it out! Integer overflow is gonna trigger me a lot...

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

      hey, I have tried similar approach but I counted number of monster that were defeated. I got wa. can you provide any testcase for your solution ? thanks

      UPD: apparently my solution was correct but I needed long long for counter.

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

I have one bad solution for F. (Very slow and naive)
At first, like everyone, concatenate $$$S$$$ with itself until its length greater than $$$|S|+|T|$$$. Then, we want to find the greatest number of copy of $$$T$$$ which is substring of current $$$S$$$. There are many ways to do, but to be more naive, I did binary search and $$$KMP$$$ to find it. How to know if the answer is not $$$-1$$$? There are a lot of better ways to do, but I concatenate $$$S$$$ with itself one more time and did the same thing as previous $$$S$$$.

If the answer is greater than the previous one, then the answer is $$$-1$$$. Otherwise it's our answer.

Time complexity: $$$O((|S|+|T|)log(|S|+|T|))$$$ (with a very big constant)

Not recommend to do this solution. I have to optimize lots of things to make this naive brute force get AC. Submission link:https://atcoder.jp/contests/abc135/submissions/6585502

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

    I also thought of the same idea but did not implement it as I thought it will TLE :|

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

    What is the reason for concatenating s with itself until it's length is greater than |S|+|T|?

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

      If $$$|S|<|T|$$$, it will never contain $$$T$$$ as its substring. When $$$|S|>|T|$$$, it has a chance that concatenating it again can make more copies of T as its substring. So we will concatenate it one more time although its length is now greater than $$$|T|$$$. Of course, concatenating doesn’t reduce the number of copies of $$$T$$$ nor get rid of $$$T$$$ in its substring, but cause bigger constant factor.

      Not related to your question, but I have more optimized submission.(Cutting out log factor) Execution time is not that bad.(65 ms)

      Link: https://atcoder.jp/contests/abc135/submissions/6593400

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

I changed my mind and decided to rewrite and post my solutions. Feel free to check them out at this link!

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

Screenshot-from-2019-07-27-17-32-21-Latest
Why are Atcoder servers so slow at the start of the contest ? The tasks doesn't load for me for the start of 2 — 3 minutes of contest :((. Am I only one facing such situation or anybody else too ?

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

    you can use Atcoder's old server https://abc135.contest.atcoder.jp/ it's kinda fast

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

      Thanks, I wasn't aware of such link. :)

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

Can anyone tell me what's the mistake in my solution. it's an iterative one. https://atcoder.jp/contests/abc135/submissions/6591877

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

Can somebody give me the data of problem F? I debug for so long but WA four tests

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

    I also want the data of problem F. I got WA on seven tests and I don't know what my mistake is.

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

Only Kotlin 1.0.0 supported? Sheesh, that's tough to work with; all the deprecations and missing features...

Though I guess the veterans here would tell me to use a "real" language like ^C(\+\+)?$ or Rust...

edit: fixed the regex

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

Can someone please explain the D problem with examples or something like that ?

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

How to solve E-GOLF problem ?? Is it a dp problem?

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

    Please provide editorial for the contest

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

can anyone tell me what's wrong about my solution for problem D pls: https://atcoder.jp/contests/abc135/submissions/7196379