Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

chokudai's blog

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

We will hold AtCoder Beginner Contest 144.

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

We are looking forward to your participation!

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

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

problem D is hard for beginer contest.

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

    Strong dislike for problem D, not because it is difficult, but because it is no fun to calculate stupid trigonometric stuff.

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

      Problem D is weird I found the formula but it's not working for last two cases.

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

        You need to take care for two cases, nearly full and nearly empty. The nearly full case is the simpler one.

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

      Yeah, I don't think that D is worth doing.

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

    D is not that hard imo

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

    problem D is not hard mean it's ok just take angle = tan-1(2*(a*a*b-x)/a^3) but due to some error I don't know why it got wrong on 2-3 cases if any one can point out?

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

      bro there are two scenarios.. this formula corresponds to one scenario other scenario have different formula.. scenerio corresponds to amount of water filled whether it is greater or lesser than HALF of volume of vessel.. i also got the same formula for one scenario..

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

why geometry !!!

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

Doing all tricks to somehow get the equation, but still cannot solve D. I am still wondering how I cleared physics and maths in higher secondary :\

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

Does anyone else also feel that loading standing page on Atcoder(so not only on current contest) takes a lot time?

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

    Yes I dont know why but It is bad

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

    Me too. Reported the issue during the contest, and here is the reply:

    We don't think we have a major technical issue now, but sorry, it seems the new feature on the standings table is a bit heavy... could you try a different browser? (You are now 40th overall and 19th among rated users... sorry for being slow.)

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

Can anyone explain problem D ??

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

    yes, please! someone who explain it

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

    So, we can actually flatten our bottle into 2D. Lets do that.

    We get 2 cases.

    We can find the angle of the 2 cases using arctan.

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

    Divide the problem into two cases:- Quantity of water is more than half of the capacity or less than half. This would result into 2 equations, one for each case,which can be derived using pretty simple trignometry.

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

    Basically there will be two cases: 1)When x is more than or equal to half of volume of container. For this you have to equate volumes like:- x=Total volume-volume of upper triangle formed. x=(a*a*b) — ( (a*a*a*tan(theta))/2 ) 2)When x is less than half of volume of container For this case you have to equate volume of lower triangle with x. x=(a*b*b*tan(PI-theta))/2 you will get theta from here, print it by converting to degrees

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

How do you solve F?

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

    My solution for F uses dynamic programming.

    First, we define dp(i) as the expected path length from node i to node N. Now, we can see a recurrence relationship for dp(i): dp(i) = (sum of dp(j) for all j such that there is an edge i -> j) / (number of edges that start from i) + 1.

    For each node, we consider the value dp'(i), which is defined as the maximum dp(i) with one outgoing edge from i not considered. By finding the largest dp(j), we can easily find dp'(i) in O(N). Then, we replace dp(i) with dp'(i) for each i, finding dp(1) each time. The minimum of dp(1) in all of these scenarios is the answer (take into account that if i has only one outgoing edge, dp'(i) can be skipped over, and we must also consider the case where no dp'(i) is used).

    Code: https://atcoder.jp/contests/abc144/submissions/8171347

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

5th place! Happy about that :)

Here are my solutions and thoughts:

A) Check if a < 10 and b < 10.

Solution: https://atcoder.jp/contests/abc144/submissions/8148768

B) Simple loop through possible values of a and b. Solution: https://atcoder.jp/contests/abc144/submissions/8150815

C) Consider a divisor $$$d$$$ of $$$n$$$. Then we can go from $$$(1, 1)$$$ to $$$(d, n/d)$$$ which will cost $$$d + \frac{n}{d} - 2$$$. So we just find the minimum of this expression for all divisors of $$$n$$$. Solution: https://atcoder.jp/contests/abc144/submissions/8153886

D) We can ignore the depth, so let $$$y = \frac{x}{a}$$$, then we essentially have a square with sides $$$a \ \text{cm}$$$ and $$$b \ \text{cm}$$$ that is filled with $$$y \ \text{cm}^2$$$ liquid. Now there are two cases:

(1) $$$y \le \frac{ab}{2}$$$. When we reach the angle $$$v$$$ where the liquid starts pouring out it will form a triangle with sides $$$c$$$ and $$$b$$$ such that the area is $$$y$$$. That is, $$$c = \frac{2y}{b}$$$. The angle in this triangle closest to the side $$$b$$$ will have an angle $$$90 - v$$$ so we see that $$$\tan(90 - v) = \frac{c}{b}$$$. That is, $$$v = 90 - \text{atan} \left ( \frac{c}{b} \right )$$$.

(2) $$$y \ge \frac{ab}{2}$$$. Let $$$z = ab - y$$$. Similarly, there will be a triangle with sides $$$a$$$ and $$$d$$$ such with area $$$z$$$ — but this time everything but to triangle is liquid. We can calculate the angle similarly.

The time used is $$$O(1)$$$.

Solution: https://atcoder.jp/contests/abc144/submissions/8165013

E) We first make an observation: If no training is allowed ($$$K = 0$$$) it always gives the optimal result of we let the members with the lowest consumption coefficient ($$$A_i$$$) eat the most difficult food (highest $$$F_i$$$). So we start sorting $$$A_i$$$ and $$$F_i$$$ such that:

$$$A_1 \ge A_2 \ge \ldots \ge A_n$$$

$$$F_1 \le F_2 \le \ldots \le F_n$$$

So with no training the answer is $$$\alpha = \max_i A_i F_i$$$. Now we do a binary search. It is clearly possible to obtain a score of $$$\alpha$$$ and impossible to obtain $$$-1$$$. To see if it is possible to obtain $$$x$$$ we do the following: For each $$$i$$$ we will replace $$$A_i$$$ with $$$A_i'$$$ such that $$$A_i' F_i \le x$$$. So $$$A_i' = \min \left (A_i, \left \lfloor \frac{x}{F_i} \right \rfloor \right)$$$. Hence we need to train $$$\sum_i \max \left (0, A_i - \left \lfloor \frac{x}{F_i} \right \rfloor \right)$$$ in total. If this is $$$\le K$$$ it is possible and otherwise it is not.

We will need $$$O \left ( \log \left ( \max_i A_i F_i \right ) \right )$$$ steps in the binary search and each step takes $$$O(n)$$$ time.

Solution: https://atcoder.jp/contests/abc144/submissions/8159504

F) This is a DAG where $$$1, 2, \ldots, n$$$ is a topological sorting of the nodes. Let's consider the case where we remove no edges. Then we can calculate the expected number of jumps from each edge in $$$O(m)$$$ time: It is $$$1$$$ larger than the average of it's outgoing children. With a formula:

$$$dist_i = 1 + \frac{1}{\left | \text{adj_list}[i] \right |} \sum_{j \in \text{adj_list}[i]} dist_j$$$

So we start by doing this. Naively, we could try to remove every edge and do the calculations which would lead to a running time of $$$O \left ( m^2 \right )$$$ since there are $$$m$$$ edges to remove and each calculation would take $$$O(m)$$$ time. We can improve this by noting the following: If we remove an edge going out from $$$u$$$ then we want to remove the edge going to the child $$$v$$$ with the largest number of expected jumps to $$$n$$$. Hence we only need to check $$$n$$$ cases instead of $$$m$$$ which leads to a running time of $$$O(mn)$$$ instead.

Solution: https://atcoder.jp/contests/abc144/submissions/8163431

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

    In problem "D" I am not getting the part "The angle in this triangle closest to the side b will have an angle 90−v". Isn't that supposed to be v instead of 90-v?

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

    why the ans is high??in solution E.

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

    In problem E, as you say it is optimal to sort $$$A$$$ and $$$F$$$ like above. So I want to ask Will the array $$$A'$$$ remain sorted with every value of binary search? And could you prove it? If it won't be sorted then how to prove that it is still optimal?

    Thanks in advance <3.

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

      $$$F_i$$$ is monotonically non-decreasing. So $$$ \lfloor \frac{x}{F_i} \rfloor$$$ is monotonically non-increasing. And $$$A$$$ is monotonically non-increasing. Thus $$$A'_i = \min(A_i, \lfloor \frac{m}{F_i} \rfloor)$$$ is monotonically non-increasing.

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

My solutions to all of the problems can be found at this link.

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

    Thanks a lot for providing a lucid explanation of all the problems ! :)

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

I had a binary search idea for D but hadn't got enough time to code it out. Did anyone solve the problem using binary search?

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

    what is your idea bro?

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

      Check the solution of others. Basically it's a deduction of formula for an O(1) solution

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

        When you will calculate tan() the value will exceed the limits of long double or long long integer as tan() approaches 90 degree. Binary search wont work I think.

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

          I see. However the official editorial did include binary search as one of its method though.

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

    EDIT: actually I just need to rearrange my equation and solve for theta. I got the same formula as discussed.

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

please clarify me why my ans is wrong for C,&D for C

ans=ceil(-2+(2*sqrt(n)));

and for D

{ y=((2*x)-(a*a*b))/(a*a);

ans=(180/PI)*(atan((b-y)/a)) ; }

but still it shows wrong answer .... why???

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

    problem C and D seems like very basic math problem ... still i got incorrect ,please publish editorials fast

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

      For D you missed a case when y is negative in that case ans will be c = (2*x)/(a*b) angle will be atan(b/c)*180/pi

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

    Doesnt your code for C fail the sample test case of 10000000019?

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

      yes it failed there ...but dont understand why .... even i tried to make a square root function by myself instead of library function so that it can accept larger value of n .... i used long float data type in Square root function... how to find square root of such large numbers??

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

        In the sample the answer was 10000000018. This is alot bigger than $$$-2+(2\sqrt{10000000019})$$$.

        So Its definitely not your squareroot function failing.

        Instead your formula is wrong for most $$$n$$$

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

          my logic:

          suppose we move x times along horizontal and y vertical in table ,in order to obtain a product resulting N; we get following eq, — (1+x)*(1+y)=N; {1+x+y+xy=N} now we know (x+y)/2>=sqrt(xy) ; so if let x+y=M ;

          then we get M^2/4>=xy .... now let us substitute in above equation and solve ;;;;

          we get M^2/4 +M =N-1 ; now solve it and find condition M>=(-2+2*sqrt(n));

          ans=ceil(M); i think here it will work for all numbers , if not why??

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

            (x+y)/2>=sqrt(xy)

            Can you please elaborate on how you derive this? I cant follow

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

              arithmetic mean>= geometric mean for all positive integers

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

                Ah, i see.

                Anyways, your logic is not wrong anywhere. M>=(-2+2*sqrt(n)) is true. But this does not imply that M=ceil(-2+2*sqrt(n)).

                One simple counterexample of your claim is for a prime number N. Where you can only go to point (1,N) and (N,1). Here we can see that M=N-1.

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

                  ohkk , thanks for your help

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

    For C, we can only move to integer points, so this will not work for any values that aren't perfect squares.

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

      why so, actually i have written ans=ceil(-2+(2*squareRoot(n)))

      i forgot to mention here ....

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

      how did you solve it , can you please give me a little hint

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

As a junior high student, I think Problem D is unfair because we haven't learnt the arcsin function before the contest. But I conquered it so I'm not very unhappy. :D

PS: I cannot browse the standings page. Maybe my location(in China) matters?

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

Problem D ruined my contest

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

Brute force (with randomize and optimization) can pass problem F.

Code

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

Why was this contest not shown in clist.by ?

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

    yes apparently it has stopped showing atcoder contests. I missed a contest because of this :(

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

https://atcoder.jp/contests/abc144/submissions/8178663

I've been doing binary search on Problem D, but I just couldn't get an AC. I cannot understand. Any help will be appreciated! Please Help

BTW I didn't miss the case when half of the capacity is tilted.

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

can anyone help what is the testcase no 9 , i.e. , 01-handmade-08 ? I keep getting WA on it.

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

I was stuck at F, as my answer was "-nan" in C++, to only realize later that the graph is actually an acyclic graph, need to read problems more clearly from now on, otherwise I did Infinite GP sum of a matrix, which may indeed sound absurd for this question.....

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

Can someone please explain to me problem E in simple terms? Thanks in advance.

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

    -->First you have to find the highest score let it is H. -->binary search in the range from -1 to H. -->for every mid value we have to check whether we can distribute training properly -->if you see this link now : https://atcoder.jp/contests/abc144/submissions/8159504 -->I think you understand this problem solution

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

Problem D have two conditions 1、 water is so much x*2 >= a*a*b

2、 water is so little x*2 < a*a*b

I picture it in my blog https://www.cnblogs.com/163467wyj/p/11753015.html

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

After solving this contest, I have realized that I actually can solve all of problems without lack of any knowledge. Before, I even didn't read statement problem F because I believe I didn't having sufficient knowledge to solve it.

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

Can anyone please explain first two test case more details of problem F? Thanks in advance.

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

may anyone explain me how is the minimum steps required to do it is a+b-2

and how are we getting aa and from 1. a*b = n equation

C: walk on multiplication table

The number of moves needed to reach (a, b) from (1, 1) is a + b − 2. Therefore, the problem can be rephrased as ”find the minimum value of a + b − 2 for all (a, b) such that a × b = N.” By symmetry you can assume that a ≤ b, so by performing brute-force searching for all a ≤ √ N, the problem can be solved in a total of O(√N) time.