Hello,

I don't know how to relate my asymptotic analysis for a program to run time in millisecond? For example, if I write a solution that runs in O(N^2), how long in milliseconds does it take to run?

Thanks in advance!

Hello,

After having a look at the following blog entry: http://codeforces.net/blog/entry/15729

Quoted Excerpt:

"2.Problems which you are asked to perform some queries asking you to modify a part of elements (without printing queries.) Solution of all of this problems are the same. You just need to know how to solve one of them. Example : You need to perform some queries on an array a1, a2, ...a, n. Each query give you numbers l, r and v and for each i such that l ≤ i ≤ r you should increase ai by v, and then after performing all queries, you should print the whole array. Solution : You should have another array p1, p2, ..., pn which, all of its members are initially 0, for each query, you should increase pl by v and decrease pr + 1 by v . An then, for each i, starting from 1 you should increase pi by pi - 1. So, final array would be a1 + p1, a2 + p2, ..., an + pn . Hard problem of partial sum : Troynacci Query"

Then, having a look at the editorial for Troynacci Query : 100571B - Troynacci Query , Editorial Link: http://codeforces.net/blog/entry/15722

My Question: I find it difficult to trace back the reasoning or mathematical proof behind this algorithm. Could you please suggest any hints how or why this way of solving the problem is correct?

Hello,

I'm confused how to come up with a solution for 738B - Spotlights. A naive approach should take nearly O(N^4), but the correct approach is only O(N^2).

How to formulate the correct algorith?

Please help me fill the gaps in this approach:

1 — Read all inputs, and in the same time fill values for "UP" & "LEFT". O(N^2) 2 — After reading, run a nested loop over the grid, and sum values for "Down" & "RIGHT". O(N^2)

What is the formula to sum the values?

I can only imagine counting the empty cells with '0' in each row and column, and then when one encounters an occupied cell with "1" is to subtract somehow depending on the position of this one.

I just can't put it all together into a working solution.

Thanks in advance~

What is the Pseudo Code for the solution to this problem 720A - Церемония закрытия ?

I'm n't sure if this guess is correct;

1 — make two priority queues / heaps 2 — fill the heaps with the distances from point(0,0) and point(0,m+1) in quadratic time O(2*n*m) 3 — sort queues of audience k, l=n*m-k in ascending order 4 — for each attendee of the audience from both queues (pick the one with smaller stamina) in time of O(2*n*m) 5 ----- pop the minimum / top of the heap corresponding to the entry point either (0,0) or (0,m+1) 6 ----- if point was taken before, then get pop next min 7 ----- if point's distance from entry > stamina of attendee, then return false and terminate 8 ----- mark the point as taken, so that the other heap doesn't pick it

Any better approaches?

How is problem 712D - Мемори и игра solved using Dynamic Programming?

What is the memoization array structure?

What is the base case?

What is the greedy choice equation?

Thanks in advance!

Hello,

I'm getting time limit exceeded on this problem; 710F - String Set Queries

Any idea how to tweak my solution to avoid this quadratic runtime in method "count". I reviwed others solutions, and they are all quadratic, but why my implementation is just slower?

The nested for loop gives an asymptotic runtime of O(L^2) where L is input string length.

My solution; 20459110

Any hints would be truly appreciated!

Thanks in advance!

Hello,

I have been spinning my head around this test case for a while now.

Could you please provide the full test case grid?

I thought it was the overflow of the unsigned long long value, but this didn't work.

I thought it was the memory limit, but apparently this wasn't the case.

I tried to mimic the grid by using this form;

0 3 3 3 3 3 3 3 3

And then, my solution outputs the correct value of 3 in the missing cell. (Isn't it?)

Any hints will be appreciated!

Thank you!

Problem Link: http://codeforces.net/contest/711/problem/B Problem Solution: http://codeforces.net/contest/711/submission/20392397