NALP's blog

By NALP, 8 years ago, translation, In English,

Hi to all!

215A - Bicycle Chain

Because of small constraints we can iterate i from 1 to n, iterate j from 1 to m, check that b j divide a i and find max value of . Then we can start this process again and find amount of the pairs in which is max value.

215B - Olympic Medal

Let amagine we have values of r 1, p 1 and p 2. Then:

r 2 2·(B·p 1 + A·p 2) = r 1 2·B·p 1

Now it’s easy of understand, we must take maximum value of r 1 and p 1, and minimum value of p 2 to maximize r 2. You could not use three cycles for iterating all values, but you could find property above about at least one value and use two cycles.

215C - Crosses

Let’s iterate n 1 = max(a, c) and m 1 = max(b, d) — sides of bounding box. Then we can calculate value of function f(n 1, m 1, s), and add to the answer f(n 1, m 1, s)·(n - n 1 + 1)·(m - m 1 + 1), where two lastest brackets mean amount of placing this bounding box to a field n × m.

Now we must calculate f(n 1, m 1, s). At first, if n 1·m 1 = s then the result of the function is 2·(⌊ n 1 / 2⌋ + 1)·(⌊ m 1 / 2⌋ + 1) - 1 (you can prove it to youself).

If n 1·m 1 > s then we must to cut 4 corners which are equal rectangles with square . We can iterate length of a one of sides, calculate another side, check all constraints and add 2 to the result of the function for all such pairs of sides.

The time of a solution is O(n 3), but it’s with very small constant, less then 1.

215D - Hot Days

You can use only two features about this problem: the solution is independenly for all regions and there are only 2 possible situations: all children are in exactly one bus or organizers must take minimum amount of bus such no children got a compensation. It’s bad idea to place some children to hot bus and to place some children to cool bus simultaneously.

For solving you must calculate this 2 values and get minimum.

215E - Periodical Numbers

Will be soon…

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

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

Why in problem D (Hot Days) you only need to consider the two situations mentioned? Thank you.

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

    because the cost is a linear function about the number of buses

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

    I also can't understand the solution

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

      Supose that we will arrange n buses in ith city: If T[i]-t[i]>m/n , no children will get compensations.

      If T[i]-t[i]<k/n , ans=cost[i]*n+{m-(T[i]-t[i])*(n-1)}*x[i] =cost[i]*n+m*x[i]-(T[i]-t[i])*n*x[i]+(T[i]-t[i])*x[i] ={cost[i]-(T[i]-t[i])*x[i]}*n+(T[i]-t[i])*x[i]

      cost[i],x[i],T[i],t[i],m is known,and it's a linear function about "n".So the MinCost must appear on the endpoints.

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

I didnt get the solution for Crosses. Here f(n1,m1,s) denotes the number of crosses that can be created with area s and n1 = max(a,c) & m1 = max(b,d). But why are we adding f(n1,m1,s).(n-n1+1).(m-m1+1) to the answer ?

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

    Because we can additionally position the center of the cross in (n - n 1 + 1)·(m - m 1 + 1) ways on the given grid.

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

So will you write the solution for the last problem too?

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

Why the solution to problem E still hasn't been published?

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

alas even after 8 years the sol of E is not uploaded lol

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

I think the formula for volume in problem B here is incorrect