COCI 2017/2018 — Round 4

7 лет назад, # |

How to solve the third problem (Automobil) for N,M <= 1'000'000?

→ Ответить

mraron

7 лет назад, # ^ |

← Rev. 4 →

+13

Let's calculate the answer first without any operations. Then calculate array R and C, R_i denotes the product of all query's for the ith row, similarly for columns C_i denotes the product of the ith column (I created them lazily with std: : 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 by a and then in one column we multiplied by b then at their intersection we considered this value a + b times but should've considered it ab times), since K is pretty small there won't be many (atmost $\text{[math]}$ ), so this way we have a O(K²) algorithm.

→ Ответить

7 лет назад, # ^ |

+10

Ah, I think I got too caught up thinking of how to handle the intersections, should've realised that there would only be ~K² of them. Thanks!

→ Ответить

mavd09

7 лет назад, # ^ |

← Rev. 4 →

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.

→ Ответить

-osdajigu-

7 лет назад, # ^ |

← Rev. 6 →

My approach was a little diferent that mavd09 and mraron

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

$\text{[math]}$ where k_i = multiplication of times row i was updated and v_i is the value that is in i - th row 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 mean v_j_i + 1 = v_j + 1_i with j being the j - th column ). So we can rewrite the solution as:

$\text{[math]}$

Now if you look that carefully, the terms $\text{[math]}$ and $\text{[math]}$ 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

$\text{[math]}$

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( $\text{[math]}$ )

Code

→ Ответить

7 лет назад, # |

How to solve D (large) and E?

→ Ответить

7 лет назад, # ^ |

← Rev. 4 →

dp_i, j = can i-th player win if (i - 1)-st player said number j. dp_i, j = true if

a_i ≠ a_i + 1 and dp_{i + 1, j + 1... j + k} has at least one false.
a_i = a_i + 1 and dp_{i + 1, j + 1... j + k} has at least one true.

Write array a many times and use some prefix/suffix sums to find that "at least one" thing in $\text{[math]}$ instead of $\text{[math]}$ .

Total complexity: $\text{[math]}$ .

Code

→ Ответить

7 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

7 лет назад, # ^ |

← Rev. 2 →

I also did this, but will it definitely pass? There are NM dp states, and K processing at each state, giving us O(NMK), or about 1.25 * 10¹¹ operations. Am I missing something?

Edit: I was mistaken, should've paid more attention to the explanation. Thanks for the clarification.

→ Ответить

-osdajigu-

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

← Rev. 4 →

$\text{[math]}$ if you do transitions in $\text{[math]}$ . Check the code.

→ Ответить

-osdajigu-

7 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

7 лет назад, # |

How to solve 140, 160?

→ Ответить

7 лет назад, # ^ |

← Rev. 3 →

+13

→ Ответить

7 лет назад, # ^ |

← Rev. 2 →

How to find maximum/minimum of unimodal function if there are more xs with same value of F(x)?

→ Ответить

7 лет назад, # ^ |

Nothing changes. It attains its minimum when X = (median of Y)

→ Ответить

7 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

7 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

7 лет назад, # ^ |

Ok, thank you.

→ Ответить

7 лет назад, # |

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>

→ Ответить

7 лет назад, # ^ |

← Rev. 3 →

I doubt that will work. But for fixed i ternary search works.

→ Ответить

7 лет назад, # ^ |

+10

I generated some random tests in python to check if choosing i is convex and you're right of course, it isn't.

→ Ответить