AtCoder Beginner Contest 144 Announcement

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

5 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

frost_

5 years ago, # ^ |

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.

→ Reply

Noob_Noob_

5 years ago, # ^ |

← Rev. 4 →

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

→ Reply

yeeeet

5 years ago, # |

How do you solve F?

→ Reply

shenxy13

5 years ago, # ^ |

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).

→ Reply

Tejs

5 years ago, # |

← Rev. 2 →

+28

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

→ Reply

HynDuf

5 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

en30

5 years ago, # ^ |

$$$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.

→ Reply

Geothermal

5 years ago, # |

+12

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

→ Reply

ghoshsai5000

5 years ago, # ^ |

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

→ Reply

5 years ago, # |

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?

→ Reply

grg124

5 years ago, # ^ |

what is your idea bro?

→ Reply

5 years ago, # ^ |

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

→ Reply

dalip_patra

5 years ago, # ^ |

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.

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # |

← Rev. 2 →

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???

→ Reply

5 years ago, # ^ |

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

→ Reply

shivang_garg99

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

← Rev. 2 →

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??

→ Reply

5 years ago, # ^ |

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$$$

→ Reply

5 years ago, # ^ |

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??

→ Reply

5 years ago, # ^ |

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

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

→ Reply

5 years ago, # ^ |

arithmetic mean>= geometric mean for all positive integers

→ Reply