Блог пользователя Geothermal

Автор Geothermal, история, 5 лет назад, По-английски

A — 9x9

We can simply directly implement the procedure given in the problem. Print $$$AB$$$ if $$$A$$$ and $$$B$$$ are less than $$$10$$$ and $$$-1$$$ otherwise. One particularly fast way to do this is to use the ternary operator, which takes a boolean expression and two values as inputs and returns the first value if the expression is true and the second value otherwise. In C++, this looks like

$$$\texttt{A < 10 && B < 10 ? A*B : -1}$$$.

Runtime: $$$O(1)$$$. Click here for my submission.


B — 81

Since we're only considering pairs of numbers from one through nine, we can simply iterate over every pair of numbers from one to nine and check if each pair multiplies to $$$N$$$. As soon as we find such a pair, we output Yes and exit the program. If we reach the end of the loop, we can then print No, since we've checked every possible pair and found that none of them work.

Notice that we could also iterate over all numbers from $$$1$$$ to $$$9$$$, and for each number $$$i$$$, check if $$$N$$$ is divisible by $$$i$$$ and, if so, whether $$$N / i$$$ is between $$$1$$$ and $$$9$$$. However, this would take longer to implement, and with so few values to check, the above approach is efficient enough anyway. This is a good example of a problem where it's better to quickly implement a trivial solution than to waste time coming up with a more efficient idea.

Runtime: Technically $$$O(1)$$$, though our loop will iterate $$$81$$$ times (or $$$45$$$, if you only iterate over pairs $$$(i, j)$$$ with $$$j \geq i$$$). Either way, it will run very quickly. Click here for my submission.


C — Walk in Multiplication Table

Note that we can walk to any pair $$$(i, j)$$$ in $$$i+j-2$$$ steps. Thus, we simply need to find the pair $$$(i, j)$$$ with $$$ij = N$$$ that minimizes $$$i+j$$$. Luckily, we can enumerate all possible pairs $$$(i, j)$$$ and check them in $$$O(\sqrt{N})$$$. To do this, without loss of generality, we can assume $$$i \leq j$$$, and we must have $$$i \leq \sqrt{N}$$$ since $$$N = ij \geq i^2$$$, so $$$\sqrt{N}^2 \geq i^2$$$, so $$$\sqrt{N} \geq i$$$. Thus, we can iterate over all possible values of $$$i$$$ from $$$1$$$ to $$$\sqrt{N}$$$ and, among all working pairs $$$(i, j)$$$, we pick the lowest value of $$$i+j-2$$$ and print it.

Runtime: $$$O(\sqrt{N})$$$. Click here for my submission.


D — Water Bottle

First, note that when we take an $$$A$$$-by-$$$B$$$ rectangular cross-section, tilting it counterclockwise at an angle of $$$\theta$$$, the water will be at the height of the top-left corner. (Draw the picture yourself if it's hard to visualize this in your head.) Then, we want $$$A$$$ times the area within this rectangle at or below this height to equal $$$X$$$.

We perform casework on whether the water bottle is at least half full.

Suppose that it is not half-full. Then, examining the figure, we can observe the wet area will be a right triangle with one side of length $$$B$$$ and adjacent angle $$$90^circ - \theta$$$. We can thus express the area of this triangle as $$$\frac{B^2 \tan 90^\circ - \theta}{2}$$$, and the total volume of the water will be $$$\frac{AB^2 \tan 90^\circ - \theta}{2}$$$. Thus, we have $$$X = \frac{AB^2 \tan 90^\circ - \theta}{2}$$$, which gives $$$\tan 90^\circ - \theta = \frac{2X}{AB^2}$$$, so $$$90^\circ - \theta = \arctan \frac{2X}{AB^2}$$$ and $$$\theta = 90^\circ - \arctan \frac{2X}{AB^2}$$$.

Now, suppose that the bottle is at least half-full. Then, we can observe that the part of the rectangle not filled with water is a right triangle with one side of length $$$A$$$ and adjacent angle $$$\theta$$$. This triangle has area $$$\frac{A^2 \tan \theta}{2}$$$, so the volume of the box not filled with water is $$$\frac{A^3 \tan \theta}{2}$$$. Therefore, we have $$$A^2B - X = \frac{A^3 \tan \theta}{2}$$$, so $$$\tan \theta = \frac{2A^2B - 2X}{A^3}$$$, so $$$\theta = \arctan \frac{2A^2B - 2X}{A^3}.$$$

Now, we can simply implement these formulas. Make sure to convert from radians to degrees if your programming languages uses radians by default! You can do this by multiplying by $$$\frac{180^\circ}{\pi}$$$. (If your programming language doesn't have $$$\pi$$$ built-in as a constant, you can compute it as $$$2 \arcsin 1$$$.)

Runtime: $$$O(1)$$$. Click here for my submission.


E — Gluttony

First, an intuitive observation: we should assign the fastest eaters to the most challenging foods. One way to prove this is to note that if we have two eaters with constants $$$a \leq b$$$ and two foods with difficulties $$$c \leq d$$$, we can see that $$$max(ac, bd) = bd \leq max(ad, bc)$$$, so we are better off assigning the eater with the lower constant to the food with higher constant. We can apply this algorithm many times to prove that this ordering--fastest eaters with the highest-difficulty foods--is optimal.

So, let's sort the eaters in increasing order and the foods in decreasing order. Then, we binary search for the answer, noting that this is valid because if we can finish within some amount of time, then we can also finish within any greater amount of time. To check if some value $$$T$$$ could be the answer, note that in order to make the maximum eating time equal to $$$T$$$, we need to train all eaters for whom $$$A[i] F[i] > T$$$ until $$$A[i] = \lfloor \frac{T}{F[i]} \rfloor$$$. We can thus compute the number of training sessions required in $$$O(N)$$$. An answer is valid if at most $$$K$$$ training sessions are needed. We can then use binary search to find the least possible value of $$$T$$$ using $$$O(\log A_i F_i)$$$ of these queries, since the most time we could possibly take is $$$O(A_i F_i)$$$.

Runtime: $$$O(N \log A_i F_i)$$$. Click here for my submission.


F — Fork in the Road

Let's first compute three auxiliary arrays. First, we compute an array $$$deg$$$ such that $$$deg[i]$$$ is the number of edges coming from node $$$i$$$. Then, compute an array $$$P$$$ such that $$$P[i]$$$ is the probability that we reach node $$$i$$$ at some point in the process. To do this, we can initialize $$$P[0]$$$ (using zero-based indexing for the nodes, of course) to $$$1$$$ and all other $$$P[i]$$$ to $$$0$$$. Then, process the $$$P[i]$$$ in increasing order, and for each edge from $$$i$$$ to $$$j$$$, add $$$\frac{P[i]}{deg[i]}$$$ to $$$P[j]$$$.

Finally, we want an array $$$E$$$ such that $$$E[i]$$$ is the expected value of the number of steps it will take to reach node $$$N-1$$$ from node $$$i$$$. We can write $$$E[i]$$$ in terms of higher values of $$$i$$$ as follows, where the summation is over all vertices that can be reached from $$$i$$$:

$$$E[i] = 1 + \frac{1}{deg[i]} \sum_{j} E[j]$$$

From here, we can initialize $$$E[N-1]$$$ to $$$0$$$ and then compute the $$$E[i]$$$ values in decreasing order. Note that the computation of all of these arrays is $$$O(N^2)$$$.

Now, it should be easy to see that the answer, if we don't remove any passages, is $$$E[0]$$$. What if we remove some passage, though?

Let's say we remove a passage from $$$i$$$ to $$$j$$$. To compute the new value of $$$E[0]$$$, we compute $$$E'[i]$$$, the value of $$$E[i]$$$ if we didn't have access to this passage, and add $$$(E'[i] - E[i]) P[i]$$$ to $$$E[0]$$$. The intuition here is that this will capture all of the resulting change because if we don't reach $$$i$$$, then this will have no effect on us, but if we do reach $$$i$$$, which happens with probability $$$P[i]$$$, our expected value changes by the addition of $$$E'[i] - E[i]$$$.

Now, how can we compute $$$E'[i]$$$? One way to do this would be to simply reevaluate the formula given above, subtracting one from $$$deg[i]$$$ and considering only the other nodes. This would run in $$$O(N^3)$$$, but with a two-second time limit and a good constant factor (since there can only be about $$$\frac{N^2}{2}$$$ edges and any given vertex, on average, can only have about $$$\frac{N}{2}$$$ as its degree, so we'll take $$$\frac{N^3}{4}$$$ operations in total), this will probably be fast enough.

However, we'll present a solution that computes $$$E'[i]$$$ in $$$O(1)$$$, for an $$$O(N^2)$$$ solution in total. We're essentially trying to compute

$$$1 + \frac{1}{deg[i] - 1} \sum_{j} E[j].$$$

This time, the summation is over only the values of $$$j$$$ that are still adjacent to $$$i$$$ after the removal. First, let's find this summation. To do so, subtract $$$1$$$ from $$$E[i]$$$ and multiply it by $$$deg[i]$$$, which gives you the summation from the original $$$E[i]$$$. Then, subtract the $$$E$$$ value corresponding to the removed passage from the summation, giving you the new summation. Now we can multiply it by $$$\frac{1}{deg[i] -1}$$$ and add $$$1$$$, at which point we're finished. Then, we can use the value of $$$E'[i]$$$ as described above to compute our answer given the removal of a certain passage.

We can then compute the answer for every possible passage removal and print the best one.

Runtime: $$$O(N^2)$$$. Click here for my submission.

  • Проголосовать: нравится
  • +95
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How would you rate the difficulty of E?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you! I didn't understand why in problem D you say "Then, we want A times the area within this rectangle at or below this height to equal X." I mean how do you come with this conclusion?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The area within the rectangle at or below this height is the area of the cross-section that will contain water. We multiply by $$$A$$$ to convert this to the volume containing water, which should be equal to $$$X$$$.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just a question, in your submission for E.

Why did you write a loop while doing a binary search? I cannot see its importance.

F0R(i, 50) {
		ll mid = (lo+hi)/2;
		if (poss(mid)) {
			hi = mid;
		} else {
			lo = mid+1;
		}
	}

Thank you :)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    We need to perform this process many times to sufficiently narrow down the possible answers. $$$50$$$ iterations should be plenty, since $$$2^{50}$$$ is well over $$$\log_2 hi$$$. (I use loops like this instead of waiting until hi is less than or equal to lo because this helps me avoid off-by-one errors that are common in binary search implementations.)

»
5 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

I find a typo in the last paragraph of solution of F.

To do so, subtract 1 from E[i] and multiply it by E[i]

maybe we should change it into

To do so, subtract 1 from E[i] and multiply it by deg[i]

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

sir can you please explain what is logic behind doing

    			sum += A[i] - T / F[i];
    		     

I had spent 3 hours for just understanding the above line but couldn't get through it please help

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    After decreasing,the number A[i] should be at most T/F[i].Therefore,this operation must be done at lease A[i]-T/F[i] times,which should be the number added to sum.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

In E, second line,
a <= b, c <= d, max(ac, bd) = bd <= max(ad, bc)
I think maybe >= instead of <=?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem E, As you say "First, an intuitive observation: we should assign the fastest eaters to the most challenging foods". So with each value of binary search, will the new array $$$A'$$$ build from $$$A$$$ to satisfy the binary search value ($$$A'[i]$$$ = $$$min(A[i],floor(x/F[i]))$$$, is still sorted? If it won't be sorted then how to prove that it is still optimal?

Thanks in advance <3.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Shouldn't the runtime of F be O(N*M), because we need to calculate the E'[i] value for each of the edges in the graph.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could anyone explain the calculation of expected values across each nodeE[I] in question F, or does anyone have any resources to learn that.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What would be the difficulty of AtCoder Beginner contest F? In terms of codeforces Div2 Problems

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks,for the editorial.

I am unable to understand how we are using the value of k in problem E