chokudai's blog

By chokudai, history, 11 months ago, In English

We will hold AtCoder Beginner Contest 151.

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

We are looking forward to your participation!

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

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hope that it's rated!!

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hope that it's rated!!

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

How to solve F?

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

Hi, alex9801. You solved F in 2 minutes and 30 seconds!

Also, I just want to say that your code was written by me! :)

submission: https://atcoder.jp/contests/abc151/submissions/9442898

github: https://github.com/koosaga/DeobureoMinkyuParty/blob/master/teamnote.tex#L1535

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

    Someone told me to check out atcoder for some quality problems lol

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

      ABCs contain classical most of the time. Try ARC and AGC.

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

    Strongly disliked this problem. You either copy-paste the solution or spend all the time googling formulas and end up far behind.

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

      I agree, but let's look at the bright side : We got to learn something new and possibly useful

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

        Agreed. I actually happened to know the O(n^4) algorithm (who didn't?), but this contest helped me find simple closed formula for the circumcenter.

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

F-Enclose All seemed to be binary search on real numbers, but I could not figure out how to solve keeping both x and y co-ordinate into account. Can anyone explain his/her approach towards the problem?

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

    I copied this. Explanation

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

    Smallest enclosing circle is either one of followings:

    • having two points as diameter.

    • circumcircle of three points.

    So, checking all possiblity, you can get O(n^4) solution.

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

      Is there a mathematical approach towards validating this assumption?

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

      My solution is $$$O(n)$$$: link(tbh i forgot proof)

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

      Can u please give the proof of above. How do the two conditions lead to the smallest enclosing circle.

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

        If either two points not diameter, or one point is on a circle, you can adjust center little bit, resulting larger circle.

        More explicitly, denote center as $$$C$$$, points as $$$P_i$$$

        • one point on circle: move $$$C$$$ toward $$$P_1$$$, and keep radius $$$CP_1$$$ until your circle meet other point.

        • two points on circle: move $$$C$$$ along line perpendicular with $$$P_1P_2$$$, keep radius $$$CP_1 = CP_2$$$ until it cannot be moved further or meet other point.

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

    I used two ternary searches. Take two potential x-coordinates on outer ternary search and for each of them calculate the best radius using nested ternary search over y-coordinates.

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

      I didn't go for this method because I thought the circle might not be unique, just found I was wrong about the uniqueness of the circle.

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

      Can you please explain your idea, of how two ternary search would work ?

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

How to solve E?

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

    you can count the contribution of each element as 1. minimum and 2. maximum.

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

    Sort all the values and calculate contribution of each element in the final sum. If the position is $$$i$$$, then contribution is $$$a[i]*(C_{k-1}^{i} - C_{k - 1}^{n-i-1})$$$

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

    It can be solved by just fixing the min and max elements and rest can be chosen arbitrarily from elements having values in between them. 1. Sort the array. 2. Calculate prefix sums. 3. After fixing the min and max elements in the array, there can be k-2 to n-2 elements in between the min and max elements. So loop over them and multiply the value with (no. of elements in between)C(k-2). Note: - C means Combination. - Keep % 1e9 + 7 into account as well.

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

    Check the contribution of each element in each combination. Sort the array, for min iterate from the beginning and for max iterate from the end till we can get k-1 elements from the right and left side respectively.

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

    Sort the array, now notice that, you can choose all elements from k to n as the maximum number. Now if you choose i th number as the maximum, then you can take k — 1 numbers which are smaller or equal to i th number. so i th number will appear ncr(i — 1, k — 1) times as maximum.

    For minimum, we can choose numbers from 1 to n — k + 1, suppose you choose i th number as minimum, the you can take k — 1 numbers which are greater or equal to i th element. So i th number will appear ncr(n — i, k — 1) times as minimum.

    Then our answer is max_sum — min_sum

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

Why does this TLE in D. I did bfs from all the points. https://atcoder.jp/contests/abc151/submissions/9478877

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

    I think that you have to set vis[ x ][ y ]=true right after you push it into the queue, not when you pop it.

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

      what, i set x and y true before i pop not after.

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

    You should calculate all distances using floyd-warshal, which runs in O(n^3).

    example solution

    Edit: Turns out that a BFS from all points is actually faster. Since complexity is O(N^2 * N*V) there should be cases where it is slower indeed. However, not for the testcases given in this contest.

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

      I guess bfs from all vertixes has O(n^2) complexity, because we have linear number of total edges. (Each vertex has no more than 4 edges, so there are no more than 2*n edges)

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

        I think the BFS has to be done N^2 times, and each time we have to travel at most all edges.

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

    You can also just use bfs instead of dfs.

    Maybe due to recurssive calls you are getting TLE.

    My submission

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

      Lol no i just named it dfs it's bfs only i didn't write vis[nx][ny] = true in the solution which made it exponential .

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

        Yeah, that has happened with me before.

        It's a good practice to write vis = true when we are pushing into the queue, not when we are popping from the queue.

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

    BFS for all points will give TLE because of the case 20 20 with all points. A way to make it run faster is to save distances. This way if you compute bfs for u->w passing through u->v, there is no need to compute again the distance u,v. This way for me runs way below the time limit. Code: https://atcoder.jp/contests/abc151/submissions/9460670

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

Can someone help in telling the DFS approach to problem D? Why this is wrong

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

    Why are you doing dfs, we need to find minimum distance from each point

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

      yes but dfs approach also gonna work. TLE is because of recursion?

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

        dfs will not give u shortest distance thus your answer will be wrong anyway. Tho my bfs is also Tleing no idea why

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

          yes but answer is right and also dfs can give shortest distance but worst time complexity

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

        dfs is really slow for shortest paths (in worst case, it is exponential in complexity). You should use bfs instead.

        However, problem complexity is low enough that it can be cheesed with FW.

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

          DFS is EXPONENTIAL in worst case.. Seriously dude??

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

            Allow me to correct myself: in the problem of finding shortest paths, if you want a correct answer, DFS is exponential in worst case.

            As a graph traversal algorithm, it is not exponential, but this is specifically in context of the shortest-path problem, where it does indeed either give WA or is exponential in worst case, and I apologise for the unclear statement.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it
    for(int j = 0;j < h; ++j)
    

    Shouldn't it be j < w?

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

How to solve D? I used FloydWarshall and kept the max distance for every pair of routes and give me WA :( Submission

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

    Constraints were very low. Do bfs from each non-block point and get the max.

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

    I got it... I was assigning the edges to the nodes badly, F for me xd Code

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

What in #16 test in problem D? For each vertex calculate min distance to another vertex. And in all distances I chose max Code

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

weak test cases for problem C and wrong answer in editorial

it not cover the case when WA for that question is present but contestant not submit any problem show "AC".

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

    What do u mean by weak test cases ? I forgot to check for case when WA is present and AC not present and got wrong answer . After I check that case I got AC. Also the editorial to the problem covers that case . Don't spread wrong information for no reason.

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

      Brother , there is case like

      8 5 1 WA 1 WA 1 WA 1 WA 1 WA

      try this...it is not covered

      i think answer shoud be 5

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

        Answer should be 0,0 since no problem solved, no penalties.

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

          panalty should be 5 ,i guess...for 5 wrong questions

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

Geothermal Please make the editorial for this contest, like you always do.

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

Can someone tell me why this has WA for Problem E in a few cases? https://atcoder.jp/contests/abc151/submissions/9466294

I sum the contribution of elements that can be max, and the contribution of elements that can be min, and then subtract them in the end (S_max - S_min)

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

    Well I figured out what was wrong with it, and it turns out it could be one of those differences in compilers/configuration and handling of data types and so? In my code, I had #define mod 1000000007, when I change it to a declaration of a long long variable ll mod = 1000000007; the same exact code passes, here.

    It's weird, I've used this in many problems before without problem, so I am suspecting, something is off with AtCoder's settings, I could be wrong though. BTW, I did try declaring it as an int variable, but that doesn't pass. In either case, can anyone clarify or shed some light on this issue?

    RaunaqRoxx This looks like it's what's wrong with your code as well.

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

      If you use #define mod 1000000007 or int mod = 1000000007, you will get an integer overflow in cout << (mxS - mnS + mod) % mod << '\n'; if mxS = 10^9 and mnS = -10^9. So you have to use #define mod 1000000007ll or ll mod = 1000000007.

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

        Yes, that is correct, but in my code mnS is always 0 or positive, so this expression cout << (mxS - mnS + mod) % mod << '\n'; shouldn't overflow.

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

          mnS is not always 0 or positive. a[i] can be negative, according to problem constraint.

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

            Oh, that's true .. my bad. I stand corrected, Thanks!

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

      Really nice observation but this is not the problem with my code, I made that change and submitted, still the verdict hasn't changed, I have stress tested my solution on very large test cases and could not find a fault, does anybody have any idea how can we view the test cases?

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

Here is my submission for problem D why it is getting TLE. I have seen similar soln passing

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

I will be really glad if someone can provide a test case where my submission for E is going wrong. https://atcoder.jp/contests/abc151/submissions/9484300 It's getting WA at 4/18 test cases but I cannot find any counter cases. I am doing close to what is given in the editorial.

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

    You have to take care while taking mod of negative values. In this case array can have negative values.

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

      Thank you so much. I didn't read the constraints properly.

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

I tried this gradient descent-like approach basically I check 8 directions of current point and go to the one with minimum radius (centered on that point) and break when the current point is smaller than all the 8 directions. I loop this several times with increased accuracy (double dumb). Can anyone explain why I get WA? I think its precision problem but I looped a lot of times. Any suggestions of improvements are also appreciated.

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

Can anyone explain me the problem D with the given sample example. I didnt get the output. :)

ThankYou :)

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

My Solution for problem D

Explanation : I used 2 BFS to calculate the longest path in the matrix. The first BFS (function name bfs1) gives me the coordinates of the road block farthest away from the start coordinates. The second BFS (function name bfs2) takes those coordinates (which we got from bfs1) and calculates the max distance.

More info. about this double-BFS method : Longest path in an undirected tree

Result : I passed all the test cases except for one (i.e. hand_04 test file). I don't know where I went wrong. Guys please help finding me this corner case or if my approach is wrong please let me know.

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

    It works only for tree

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

      Thank you Mip182, I figured out the solution by doing BFS for each free path but can you tell me an efficient approach if the same problem had huge constraints because in that case this multiple BFS approach will fail.

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

        The question "find longest path between any two nodes" has complexity n^3.

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

          Can you please explain or attach some links?

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

            In fact you can solve this in $$$O(n^ 2)$$$. All you need is iterate over vertex and calculate distances to all other vertices using BFS and then relax answer with maximum of distances.

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

            Floyd-Warshal would be a useful start point.

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

Anyone explain E? how to approach this question

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

fpr E,why do i get WA when i calculate maxium but get accepted when I calculate minus first?

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

for E,why do i get WA when i calculate maxim but get accepted when I calculate minus first?

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

my solution Why do i get WA on C. I increment penalty for each WA for a problem untill it gets AC. Can someone please give me a sample case where it fails.

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

    Penalties for a problem don't count if it hasn't been ACed.

    A sample:

    $$$2$$$ $$$1$$$

    $$$1$$$ $$$\text{WA}$$$

    Answer should be $$$0$$$ $$$0$$$.

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

Can sb tell me why I am getting 4 WA for problem D My submission

I have used dijkstra for every (x,y) such that a[x][y]='.'