# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 202 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 185 |

5 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/08/2020 03:26:22 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Remainder: Contest starts in less than 20 mins.How to solve the third problem (Automobil) for N,M <= 1'000'000?

Let's calculate the answer first without any operations. Then calculate array

RandC,R_{ i}denotes the product of all query's for theith row, similarly for columnsC_{ i}denotes the product of theith column (I created them lazily withstd: :map). Then update the answer according to these, first by rows then by columns. Then update the intersection of the queried rows and columns manually (for example if in one row we multiplied byaand then in one column we multiplied bybthen at their intersection we considered this valuea+btimes but should've considered itabtimes), sinceKis pretty small there won't be many (atmost ), so this way we have aO(K^{2}) algorithm.Ah, I think I got too caught up thinking of how to handle the intersections, should've realised that there would only be ~

K^{2}of them. Thanks!I solve this problem as follows:

1 Add all values that don't have modifications (blank areas on the image), this step has a time complexity of numbers of queries executed over rows multiply by numbers of queries performed over columns.

2 For each row found in the queries find their corresponding sum and exclude every element that is affected by a column query (red areas on the image). After that add to your answer, this sum multiply by every Y found on the queries that affected the current row.

3 Same as the previous step but by columns.

4 Finally, add to your answer the cells marked in red on the image above.

Time complexity O( K*K ). Memory complexity O( N ).

I hope that this will be useful for you. If you need I can share you my code.

My approach was a little diferent that mavd09 and mraron

The problem is to solve the next summation for each column:

where

k_{ i}= multiplication of times rowiwas updated andv_{ i}is the value that is ini-throw of each column. C is the multiplication of times that column was updated. But the difference between each column for values (v_{ i}) is 1 between consecutive columns (I meanv_{ j}_{ i}+ 1 =v_{ j + 1}_{ i}withjbeing thej-thcolumn ). So we can rewrite the solution as:Now if you look that carefully, the terms and are always same for each j. So you only need to calculate them once. Call the first sumViKi and second sumKi

Now our answer would be

It can be reduced a little bit. But that's enough for me. So now you only need to precalculate both terms sumViKi and sumKi and the rest is just iterate over columns.

Complexity( )

Code

How to solve D (large) and E?

D:

dp_{ i, j}= cani-th player win if (i- 1)-st player said numberj.dp_{ i, j}=trueifa_{ i}≠a_{ i + 1}anddp_{ i + 1, j + 1... j + k}has at least onefalse.a_{ i}=a_{ i + 1}anddp_{ i + 1, j + 1... j + k}has at least onetrue.Write array

amany times and use some prefix/suffix sums to find that "at least one" thing in instead of .Total complexity: .

Code

Thank you. I wanted to do the same thing but defined state a little different so I couldn't do bottom up DP.

I also did this, but will it definitely pass? There are

NMdp states, andKprocessing at each state, giving usO(NMK), or about 1.25 * 10^{11}operations. Am I missing something?Edit: I was mistaken, should've paid more attention to the explanation. Thanks for the clarification.

No, process each state is O(1) cause you only need to track the last winning and last losing state.

if you do transitions in . Check the code.

I think is like dp[i][j] = is turn of i-th animal and the number the previous animal said is j. Now I need to look for a winning or losing state in (i+1)-th animal depending on what kind of animal is animal i and i+1. The first idea of course is to iterate through [j+1 — j+k].

But if you see carefully, the state of [i][j] always is looking in [i+1]. So you only need to know what are the position of the last winning and losing state in [i+1].

Then check if last winning <= j+k or last losing <= j+k depending on the case if i and i+1 are same animal, or not.

AC code

How to solve 140, 160?

EFix the roof i. Let

X=H_{ i}, then we should findXthat minimizes . Let's just simply write it as . We can see this is unimodal, and it attains it's minimum whenX= (median ofY).So, for each roof

i, we have to find the median ofY, and calculate . We will do it inO(lg^{2}(n)) per eachi.For the first part, binary search for the answer, and calculate the number of j such that

H_{ j}-j≤X-iand 1 ≤j≤i, plusH_{ j}+j≤X+iandi+ 1 ≤j≤nWe can maintain fenwick tree for and and and answer the queries. Second part don't need binary search, and it's simillar to the first part.https://ideone.com/5tyUj0

FI think it uses the technique from Balkan OI 2011 Time Is Money, but I'm not sure whether it will pass TL (at least it runs very fast on random datas). Whatever, that technique is cool, so I highly encourage you to learn (solution for Balkan OI 2011)

How to find maximum/minimum of unimodal function if there are more

xs with same value ofF(x)?Nothing changes. It attains its minimum when

X= (median ofY)I meant for an arbitrary unimodal function (I know it is so for this one).

If you are saying about staircase-like functions, then it don't happen as the function is convex. (I regret "unimodal" is not a good word to explain that function)

And you can't find a maximum in unimodal function. Let f(x) = (x == 12345678). Then you should find 12345678 somehow but it's impossible

Ok, thank you.

You can make

lg^{2}(n) intolg(n) by using a binary search tree to maintain the sequenceYand extract the median for eachi, right?For E/140 I sort of did a 2-Dimensional Ternary Search. Not entirely sure both are convex functions. Did anyone else do something like this? Or is there another way to do it>

I doubt that will work. But for fixed

iternary search works.I generated some random tests in python to check if choosing

iis convex and you're right of course, it isn't.results?

Results are out in evaluator!

How to solve F?

My F/CESTE was Dijkstra's algorithm with vertices (v, time), that the time must be increasing and cost decreasing on each v. It was too slow for

O(NM*MaxTime) vertices in the worst case, but luckily passed.We know that there exists x (0 <= x <= 1) for which the shortest path with weights time * x + cost * (1 — x) gives the optimal answer for time * cost.

Great, then let's find shortest paths with x = 0.

Then, let’s find minimum x < x’ <= 1 such that there is an edge (u, v) such that with weights time * x’ + cost * (1 — x’) Path ((1->u) (optimal for x) -> (u, v)) is better than (1->v) (optimal for x).

And rebuild shortest paths with x = x’.

We will do this process while we can find such x’.

(We can find this x’, just solve some equation a * x + b * (1 — x) < c * x + d * (1 — x) for each edge).

Code: https://pastebin.com/NXPX7Kb5

I think I might have understood what you just said. However, I'm far from being able to prove any of the facts you used. First, let me make sure I understood it the right way: for a fixed x, you compute the optimal path from 1 to all the other vertices, where the weight of a path is defined as time * x + cost * (1 — x) (basically x is a constant that helps in defining the weight of an edge). Now, my problem is: how do you know that there exists a proper choice of x so that the optimal path that you get in that case is also optimal when considering the weight as time * cost? It makes sense intuitively but I can't think of any attempt to prove it. Then, you also count on the fact that you can somehow make leaps that take you to a better answer while increasing the x. This seems even harder to prove, so if you have any idea how to prove any of these facts, I'd be grateful to see them. Aand my last question would be: this is a really strange approach, maybe even more interesting than Alien's trick (which I heard is actually Lagrange multiplier), so I was wondering whether you just came up with it, or you saw something somewhat similar to it in some other problem. If so, could you share that problem with us? Thanks in advance!

To the dowvnoters: Really?:)) It's so funny to see the -7 when my comment also explains part of the solution that some people might not have understood and definitely helped at least those. CF community doesn't cease to impress me