chokudai's blog

By chokudai, history, 2 months ago, In English

We will hold AtCoder Beginner Contest 192.

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

We are looking forward to your participation!

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

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

11 minutes to go All The Best!!

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

My screencast with commentary will be here once the contest is over.

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

I'm planning to explain the solutions live on stream after the contest. I'm trying something new and doing it on Youtube — https://youtu.be/XTvl-idpAwc (you can watch the recording here too)

My screencast without commentary is at https://youtu.be/JeiFbb1RKjI (will publish at end of contest).

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

were most solutions failing in D due to overflow / precision issues ? I thought we can binary search but gave wrong answer in 13 cases even after handling the overflow. submission

UPD : it worked after handling the case where x has length 1 . I handled the case but incorrectly , probably overflow took away all the focus.

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

    I did have to try quite a few times :( but eventually it passed after handling the overflow (using binary search: https://atcoder.jp/contests/abc192/submissions/20332818).

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

    You need to consider case where $$$x$$$ has length 1 as special case.

    I hope AtCoder will learn me at one moment long long r = 1e18 + 10 is equal to 1e18 duo double precision error. This is the third (known) time I made the same mistake

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

    Same situation with me

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

      first i tried to handle the overflow with signed long long but result can have undefined in that case.

      Later i fixed that , but for case where $$$x$$$ has length equal to 1, i wrote :

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

    There a "few" corner cases as well. Also, yes you have to handle overflow.Submission

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

    For x="1", the value of x is allways 1, independent of base n. So, why is there 0 or 1 solutions (as tutorial states). It should be m-1 possible values for n.

    Can somebody explain?

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

      value of $$$x$$$ in that case will be not $$$1$$$ , it will be always $$$x$$$ . for $$$x = 5 , m = 7$$$ answer will be $$$1$$$ , for $$$x = 5 , m = 4$$$ answer will be $$$0$$$.

      Thus if $$$x$$$ has length $$$1$$$ , it will remain always $$$x$$$ for any base . Hence if $$$M>=x$$$ answer will be $$$0$$$ else answer will be $$$1$$$.

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

        Ah... I understand. It is not asked for count possible different values of n, but possible different values of x. Thanks.

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

      Take the case x=9 and m=1.

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

      Because we need to find different values, all of them will be same and equal to x if x has length=1.

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

      I think you can only generate one distinct number(1), so the answer is 1,

      it's very tricky

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

    You can fix overflow by not thinking of overflow ft. (__int128) My Submission

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

It seems that E was easier than D.

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

how to solve E

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

    You can use Dijkstra’s shortest path algorithm.

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

Is D Binary Search or something else ?

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

    I think so. I manage to solve most of the cases with Binary Search. But I got some RE on some cases :-(

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

Anyone D??

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

Is D not a simple binsearch? I ended up changing to python to avoid overflow but still did not manage to solve it

Submission: https://atcoder.jp/contests/abc192/submissions/20328749

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

    consider the case when The length of $$$X$$$ is 1, The answer is $$$1$$$ if $$$X <= m$$$ or $$$0$$$ otherwise

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

      Yeahh. I too bricked here and couldn't solve D as I misread the problem and was trying to find the number of possible bases $$$n$$$ instead of the number of distinct values of $$$X$$$ (which turns out to be the same except for the case when the length of $$$X$$$ = 1). Missed yet another chance to AK T_T.

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

      Ahh i see, i misread the problem. Thanks

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

Why nowadays Atcoder ask a lot of precision error or something similar

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

Fixed the issue.

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

I would be really grateful if someone can look into my D submission why it is wrong ? I am doing binary search and dont really seem to have overflow issues My Code

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

    if (sz(s) == 1) {cout << 1; return;}

    The answer isn't always 1 in this case. For example: X = 9, M = 1

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

    Replace if (sz(s) == 1) {cout << 1; return;} with

    if (sz(s) == 1) {
    	if (s[0]-'0'<=m) 
    	{cout << 1;return;}
    	else {cout<<0; return;}
    }
    
»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Problems!

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

    How could you say that??

    It was one of the worst problemset that I have ever seen.

    Problem A and B was easy, as always in atcoder.Problem C was tooo easy. Problem D was also really easy, just you should know about precision error. And problem E was just a dijkstra. (And I didn't read problem F)

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

      But D seemed interesting to me!

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

        Not sure what is the interesting part in D. The main source of error here is to miss the edgecase x.length==1. That edgecase was mainly hidden by unclear statement and no such example case.

        This is usually considered to be low quality of problem.

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

      It was one of the worst problemset that I have ever seen.

      If you had participated in last ABC , you will appreciate this round. This contest is for beginners so easy problems does make sense.

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

.

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

    Can you tell me why are you using Val variable as long double in your AC solution , It is meant to have only integer values I think. One thing more , Why aren't you considering the situation when Val overflows?.

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

Nice Problems! I like this round. Problem A and B are quite easy for me, as usual. I think C is just simulation, I used sprintf and sscanf to deal with strings. I didn't manage to solve D, but I was able to work out problem E using the Dijkstra shortest-path algorithm.

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

Nice contest.

I think the problems are really good and I enjoy it, what's more, the editorial is available once the contest is over.

If you got wrong answers in D and don't know what's wrong, the bugs might be:

  • The upper value of your binary search is too small.
  • You didn't specially deal with the case when X's length is 1.

I made the second mistake while solving the problem, so I got a lot of wrong attempt, what a pity! :(

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

For people facing problems with D, try the following : 1. Handle the case when string's length is 1. 2. During binary search, store the sum in double or long double, and whenever it exceeds M, break the summation loop. Long double is capable of storing large exponents. So it won't cause precision errors.

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

    Thanks...It worked..

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

    I am unable to get my code work around handmade case #2.

    On putting certain asserts I also found out the my binary search is not working as expected.

    // ok returns true when for a given base, value exceeds m
    // l is maximum_digit_in_x + 1 whereas r is 1e18
    	while (l < r) {
    		ll mid = l + ((r - l) / 2);
    		if (ok(mid)) {
    			r = mid;
    		} else {
    			l = mid + 1;
    		}
    	}
    	assert(l == r);
    

    If I am using mid = (l + r) / 2 and then putting asserts, then it is not giving Runtime error on Handmade #1 Link

    Can anyone have a look at my submission and tell me what am I doing wrong.

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

    So does it mean , that there won't be overflow for sum in long double? , and one more silly question why was c++ boost created when Long Double can handle cases. sorry if you feel it is way too stupid.

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

      There will not be overflow but loss of precision of number as it gets larger while using long double I believe.

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

My solutions, along with explanations, can be found here :)

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

I solved D without binary search. More than that, I did not consider binary search at all!! What I did was separately handle cases where length of $$$X$$$ is $$$1, 2, 3$$$ and bruteforce+stopping early the other cases.

  • For case length of $$$X$$$ is $$$1$$$, print $$$1$$$ if value of $$$X$$$ is not greater than $$$M$$$, otherwise, print $$$0$$$.
  • For case length of $$$X$$$ is $$$2$$$, write the base-10 representation of $$$X$$$ as: $$$X_0 * b + X_1$$$ where $$$b$$$ is its base. I solve the equation $$$X_0 * b + X_1 \leq M$$$ to find upper bound of $$$b$$$.
  • Similar for case length of $$$X$$$ is $$$3$$$, I solve the equation $$$X_0*b^2 + X_1*b + X_2 \leq M$$$ using the quadratic formular.

Because the $$$b^3$$$ increases rather fast, $$$b$$$ only need to reach $$$10^6+1$$$ to surpass value $$$M\leq10^{18}$$$, so I don't need to manually handle further on.

I use Python to code, so It feels like I cheated because I don't have to worry about overflow.. Link to submission

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

would've been much more convenient if the editorial was one-paged instead of having to open different tabs

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

Can some one tell me why my sol is wrong for D? My solution I don't understand what I missed and it has been so much painful trying to find the mistake. T_T IGNORE I figured it out. It was an obvious dumb mistake :(

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

https://atcoder.jp/contests/abc192/submissions/20312845

Why my code is giving WA?? Can someone help me ??

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

    Assign f = n initially . For k = 0 your code might output some random value

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

      Thank you and yes it was the error that you told.

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

Why dijkstra's algorithm works for problem E? i solved it using dijkstra but i don't have a proof why it works.

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

    The idea is that there is no point of arriving later than you can, because you can always wait at the destination, so it's better to find the shortest path. And I believe that with this fact you can just repeat a proof for dijkstra algorithm, maybe with some small fixes.

    You can also replace each vertex with infinitely many vertices, one for each moment of time. Then you have some directed edges between vertices, and also directed edges of weight 1 between copies of the same vertex. Then you can just run dijkstra on this graph, and it will work because this is just a directed graph (infinite graph, but whatever). I don't know your exact algorithm, but it should be easy to prove that what you do is more or less equal to running dijkstra on this graph, thus it is correct.

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

How to solve F ?

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

    Let the sum of elements you will mix be S.

    Brute force over the value of K from 1 to N (the number of elements you will mix), suppose you want to check K = 3, then you should take 3 elements from the array such that the sum of these elements is S and the following conditions holds:

    1. S%3 = X%3 (because this sum will be increased by K each second until reach X).

    2. Their sum S is maximum (because this will decrease the time we need to reach X).

    The last part (choosing K elements such that S%k = X%K and their sum S is maximum) can be done using dynamic programming, let dp[i][rem][mod] represents the maximum sum you can get when you are at index i and has to take rem elements and the sum of elements you taken so far modulus K equals mod, then you try to take or leave each element and return the optimal answer.

    Note that the value returned from dp will never exceed X, Because the max value you can get is 1e9 and X is at least 1e9.

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

      Thanks for the solution. I have one more confusion. Will it be fitted in the specified time limit?

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

        You will iterate over elements from 1 to N, at each iteration you will run dp of time N^3, so the total complixity is O(N^4) and N is at most 100, so it can fit the time limit.

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

          Actually my confusion was exactly there to run a nested loop of four layer which approximately preforming 10^8 operations.

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

Submission to D. Can someone help me with this submission? It fails only in one test case for problem D.

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

How to apply Binary search in the problem D. Please Explain the logic.

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

https://atcoder.jp/contests/abc192/submissions/20515314 Could someone tell me what my mistake is in my submission to problem D?