chokudai's blog

By chokudai, history, 7 weeks ago, In English,

We will hold AtCoder Beginner Contest 155.

We are looking forward to your participation!

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope this one can be a little easier.

»
7 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

E is similar to this problem.

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

    wish ,i had visited this comment before the contest ended ...

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

      Sakhiya07 You should wait for contest to end before pasting source of problem. Its just ABC and I expect repeated problems for educational purpose.

      wish ,i had visited this comment before the contest ended ...

      forget_it What would you get by copy pasting? I challenge you to copy paste one of that GYM's AC submission now and get AC. If you have access to that problem's submissions.

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

        What type of challenge you want me too complete? I didn't understand...

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

          Open one of AC submission of this problem (made before start of today's atcoder contest) and submit it on atcoder.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it -35 Vote: I do not like it

      Stop Disliking my comment

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

    Same Problem. Same code got accepted for me

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E and F ?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve D ?

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

    Binary search (from -1e18 to 1e18). Then, once you set the guess for K, do another binary search to find out how many pairs are less than the guess.

    Final runtime: O(N * (logN)^2)

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

      You can do the checking process by two pointers, I think it is easier to code and faster.

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

        How can you solve it with two pointers?

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

            This is a beautiful solution thank you. However, I can't seem to understand why the pos and neg arrays need to be reversed when solving negative case. The way I see it is if you keep neg array non-decreasing and make pos array decreasing, then the product should be non-decreasing as well so it shouldn't affect the total count. So I removed the line where the negative array is reversed and got WA on about 1/3 of the tests.

            EDIT: Nvm, I read a bit more about the two-pointers. Reversing the arrays is the correct way to make the two-pointer loop work.

»
7 weeks ago, # |
  Vote: I like it +67 Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Contest is over!

Difficulty on D was misplaced. Implementation wise, it was much harder than E.

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

This round really made me autistic(cross out) self-close

»
7 weeks ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

I guess this is one of the difficult ABC to me. (even though I got better rank than other contests just by solving A-B-C ).

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

Can anyone tell me the mistake I did in D, the first two samples are working and out of 72 TCs, almost half of them are working. I did a Binary Search from -10^18 to 10^18 and found out how many products will be less than the mid, and accordingly shift the high and low by comparing with k. https://atcoder.jp/contests/abc155/submissions/10161880 Also, do we require BigInt in E or is it doable without them? If yes, then can anyone tell me how?

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

    We can do E without using BigInt too.

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

    E doesn't need BigInt. In fact, I recommend you solve the problem by turning the String into an array of integers, then doing an O(N) sweep from right to left).

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

    I didn't find the bug but I have some suggestions.

    • You don't need long doubles. If a is a integer, a <= x is the same as a <= floor(x) and a >= x is the same as a >= ceil(x). You just have to be careful with negative values.
    • I found it easier to compute 2*(the number of pairs) and then divide it by 2 instead of just compute it directly.
    • I didn't understand why you count the number pairs with equal and smaller products in two different variables and use them differently. Shouldn't you always use their sum?

    I coded the same solution. https://atcoder.jp/contests/abc155/submissions/10145988

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

      Thank you for these suggestions, and for having a look at my code. I was coding it without using doubles but I was having a difficulty as some point so I thought it would be easier using doubles. I thought of calculating both values because I thought that if kth product was not unique then I might miss it because if I calculate all the products lesser than mid, it would be less than k and all the products less than and equal to mid would be greater than k. I couldn't come up with a justification why their sum would be used, can you help me with that too?

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

        Let f(x) = number of pairs with product <= x. The answer is the smallest X such that f(X) >= k.

        To have a intuition I think its enough to look at the first sample. $$$f(-13) = 0, f(-12) = 2$$$. So the answer for $$$k = 1$$$ is the same as $$$k = 2$$$ (-12).

        $$$f(-7) = 2, f(-6) = 4$$$, so the answer for $$$k = 3$$$ is the same as $$$k = 4$$$(-6).

        $$$f(7) = 4, f(8) = 5$$$, so the answer for $$$k = 5$$$ is 8.

        There is no need to compute < x and = x, just <= x.

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

          Thank you so much for this clear explanation, I would incorporate these changes in my code, and will try to get an AC.

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

      Hi Nson, could you please explain the div_floor and div_ceil functions as well as why do you need them?

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

        div_floor($$$a$$$, $$$b$$$) = $$$\lfloor \frac{a}{b} \rfloor$$$ and div_ceil($$$a$$$, $$$b$$$) = $$$\lceil \frac{a}{b} \rceil$$$.

        I wanted to count the number of elements $$$x$$$ such that $$$a_i * x \leq lim$$$, this is:

        • $$$x \leq \frac{lim}{a_i}$$$, if $$$a_i > 0$$$
        • $$$x \geq \frac{lim}{a_i}$$$, if $$$a_i < 0$$$

        And then I used floor and ceil to only work with integers.

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

          I see! Any particular reason why you coded these functions (floor, ceil) yourself and not used the ones from std?

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

            To use the floor or ceil I would have to compute $$$\frac{lim}{a_i}$$$ using doubles and that's what I was trying to avoid.

            I always don't use floating-point numbers when I can to avoid any precision issues.

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

        Also could you please explain where does the -1 come from in the following two lines:

        if(i < id) ans += id - 1;
        else ans += id;
        

        and

        if(i >= id) ans += n - id - 1;
        else ans += n - id;
        
        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          For $$$a_i > 0$$$ I want to count the number of $$$a_j$$$ such that $$$a_j \leq \frac{lim}{a_i}$$$.

          As the array $$$a$$$ is sorted, this is a prefix of it and with upper_bound I can find the size of this prefix. There is just one problem, if $$$i$$$ is in this prefix then I don't want to count the pair $$$(i, i)$$$ at the answer, but its enough to just remove 1 element(the $$$i$$$) from this prefix.

          For $$$a_i < 0$$$ it's basically the same thing, but the answer is a suffix of $$$a$$$.

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

            Got it! Thanks a lot for the clear explanations and for your patience :D

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

            Thanks, your approach taught me the implementation of two new functions — ceil div and floor div!!

            Your solution is neat, while I was coding, I wasn't able to tackle edges but when I saw your code, you nicely used floor and cell for the purpose!

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

Can E be solved using DP? If yes DP transitions, please :)

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

    The solution for E is greedy.

    Technically you could use DP, but there is no point. At every state there is only one move you should do.

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

    Hint:"Simulate the subtraction process"

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

    Yes, a simple N*2 digit dp would do

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    dp[idx][carry] is the minimum number of banknotes we (you and the cashier) used after processing all numbers starting from 0 to idx-1, such that we have carry = 1 or 0

    So, we start from the right, and decrease the idx as we go through the number N, the transition will look like this:

    dp[idx][carry] = min( dp[idx-1][0] + N[idx] , dp[idx-1][1] + (10 — N[idx]) )

    corner case: the first option can't be done when N[idx]==9 and carry==1

    in the base case we should return carry value

    submission: https://atcoder.jp/contests/abc155/submissions/10167311

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please give a solution for D and E??

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me the exact solution of D?

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

    Binary search from -1e18 to +1e18. Then you take a guess of k and perform binary search for the number of numbers below that number. I would say this question was harder than E. ;_;

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

      Are those, wordings of Agnimandur ?

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

        yeah, i haven't solved it myself yet but the solution makes sense to me.

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

        For those Who still Didn't uunderstand D.Agnimandur Explained in CPC

        basically split the input into the positive numbers and the negative numbers, and then sort them. call the positive array POS, and the negative array array NEG.

        then binary search from -1e18 to 1e18. let the "guess" of the binary search be G. if (G < 0), then iterate over all of the negative numbers. For each negative number, do a binary search over all the positive numbers, and find the largest positive number such that the product is <= G.

        If G > 0, then all of the negative * positives work. Then, iterate over NEG and at each index i do another binary search from i+1 to the end to find the number of pairs of negative numbers that have a product less than G. Do the same thing over POS.

        In total, after you iterate over the lists, if you've found X pairs less than G, and X is less than K, then G must be too small. Otherwise it works, and you transition the binary search accordingly

        https://atcoder.jp/contests/abc155/submissions/10157539

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

          thx, well explained!

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

          Why for G -ve we have to check product<=G and for +ve we want product<G

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

Why doesn't ABC get updated on Atcoder calendar anymore? I rely on the calendar for contest participations and I've missed like all the ABCs recently because of it.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone post your code for problem B?

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

How to solve F?

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

    Sort the A_i, so every operation concerns a subsegment of indices. Let D_i be the xor between B_i and B_{i-1}, where we consider that B_0 = 0. Our objective is to make D[] = 0. Notice that now every operation amounts to flipping the state of at most two elements of D.

    Build a graph on 1..n where indices i and j have an edge between them if an operation affects both. Notice that if we have a simple cycle x_1, x_2, ..., x_k then flipping the edge from x_1 to x_k has the same effect as flipping the other k-1 edges, so it's enough to take a spanning tree of each component. Now we can root each tree arbitrarily and greedily go from leaf to root, doing the correct operations to do everything except possibly the root equal to 0. If at the end the root is 0 we have to flip a single element in the tree in order to fix it. If no operation does that then it is impossible.

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

Was this streamed yesterday ? They are solutions to today's contest . It shows to be streamed on 15th Feb 2020 https://www.youtube.com/watch?v=SG60Cp9pSog is this Scam ?

»
7 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Why cant they provide editorial in english when the majority is not from japan :/

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

    maybe the majority of the problem writers are japanese

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

https://atcoder.jp/contests/abc155/submissions/10169630

Can anybody explain what's wrong with this submission for problem E?

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

    In the case 955 I believe the answer is 10(955, 956, 957, 958, 959, 960, 970, 980, 990, 1000, 0) but your code outputs 11.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm much weaker than you all, could you tell me how to solve Problem C?

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

    Count the occurrence of each string then output all those strings which have highest number of occurrences. For counting I used map, and in order to output in lexicographical order I sort them using vector of string.

    Here is my solution

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

      Thank you very much.

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

      Why do you need to sort in lexicographical order..? Map sorts the strings and stores the count of each string right? You do not need any vector to sort again...

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

        YES. I know that, but in the moment I couldn't think of it. I was in hurry.

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

when will the English Solution be published?`\

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

https://atcoder.jp/contests/abc155/submissions/10152047

I appreciate if someone tells me what is wrong with this submission. It works fine with small tests, but gives wrong answer for the long one:

For the test 314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170 it returns 249 instead of 243.

the code is this:

int main()
{
    string s;
    cin >> s;
    
    int sum = 0;
    int last = 0;
    for(int i = s.length() - 1; i >= 0; i--) {
        int current = s[i] - '0';
        if(last)
            current++;

        if(current > 5) {
            current = 10 - current;
            last = 1;
        }
        else
            last = 0;

        sum += current;
    }
    sum += last;
 
    cout << sum << endl;
 
    return 0;
}
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Your solution for test '555' gives answer 15 instead of 14 (1000 — 400 — 40 — 5)

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

    Greedy approach does not work for this problem, for example if N=555, your program outputs 15, but you can obtain 14 (1*1000 — 4*100 — 4*10 -5*1) wish comments would auto refresh, so this does not happen when I try to answer someone.

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

      Thank both of you. Great example which shows where I was wrong.

      Would you bother telling the dp recursive function for this problem?

      Am I going the right path with this: dp[i, 0] is the minimum answer for the first i digits, if we pay s[i] bills,

      dp[i, 1] is the minimum answer for the first i digits, if we get back 10 - s[i] bills, and:

      dp[0,0] = s[0]
      dp[0,1] = 10 - s[0]
      dp[i, 0] = min(dp[i - 1, 0], dp[i - 1, 1]) + s[i])
      dp[i, 1] = min(dp[i - 1, 0], dp[i - 1, 1]) + 10 - s[i])
      

      the answer will be the min between two last dps.

      * I should also consider the carry bit.

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

        The code does a lot of preparation. The signature of the greedy method is to add something to the final answer, in each step. Indeed there may be data preparation before. IMHO, with this definitions, one may get a dp solution wrongly as greedy.

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

      can you help me out here

      https://atcoder.jp/contests/abc155/submissions/10174005 For E I took a greedy approach of taking max subarray which contains digits >=5 for eg-(9658) 231 (96) 321. For each container , I subtracted 9-int(s[i]) for all except last member of that container. The last one is subtracted by 10. digits <5 are not inside any container.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please write the solutions in English too and provide setters/editorial writers code along with it. giving contests without having access to proper editorials is kinda frustrating.

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

    "For International Readers: English editorial will be published in a few days" They're doing a great work, give them some time. Also often you can understand the solution if you copy-paste the editorial into an automatic translator and read that.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Publish Editorials in english also ,so that non Japanese can understand....

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

English editorial is out!