Before contest

Codeforces Round #476 (Div. 2) [Thanks, Telegram!]

08:41:16

Register now »

Codeforces Round #476 (Div. 2) [Thanks, Telegram!]

08:41:16

Register now »

*has extra registration

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

1 | Petr | 3325 |

2 | OO0OOO00O0OOO0O0…O | 3289 |

3 | Um_nik | 3278 |

4 | Syloviaely | 3274 |

5 | tourist | 3206 |

6 | Radewoosh | 3197 |

7 | V--o_o--V | 3167 |

8 | mnbvmar | 3096 |

9 | dotorya | 3086 |

10 | FizzyDavid | 3023 |

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

1 | tourist | 183 |

2 | rng_58 | 168 |

3 | csacademy | 161 |

4 | Petr | 160 |

5 | lewin | 151 |

6 | Swistakk | 150 |

7 | matthew99 | 142 |

8 | BledDest | 141 |

9 | Errichto | 140 |

10 | adamant | 139 |

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/25/2018 11:53:45 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

Consider input 00000... 0011... 11111. Do you see why your algorithm has quadratic time complexity?

Sorry I am new to this coding I don't know what is a time complexity

Well basically if some algorithm has time complexity

O(x) that means it does amount of basic actions (like adding, subtracting, indexing an array, etc.) that is proportional toxin worst case wherexis some function of input size.For example, if we say

nis the size of input string of 0's and 1's, then your solution's time complexity isO(n^{2}) because if the answer is 0 it has to remove "01" or "10"n/ 2 times and each removal is done by rebuilding the whole string so it also takesnactions for the first time,n- 2 for the second,n- 4 for the third and so on, which is roughlyn^{2}/ 4 if summed up (it's actually more). So your solution's amount of basic actions in the worst case is 0.25 *n^{2}, which is linearly proportional ton^{2}, so its time complexity isO(n^{2}).So, n's maximum value in the problem is 2 * 10

^{5}, and your solution does 0.25 *n^{2}in the worst case, so your worst case is 10^{10}actions, which is impossible to squeeze into one second (moreover, on C#).I'm not an expert (though my rank states so), but I can say C# can easily do 10

^{6}actions in one second, so probably you should find a solution which time complexity isO(n) so it does about 10^{5}actions and maybe a little more.UPD: in competitive programming, algorithm's time complexity usually very well represents its speed. In other words, if you plug in your maximum values for input size variables in time complexity's function and see that the number you get is about 10

^{6}or less, then you're good to go and your solution will probably pass the time limit. Very rare are cases in which that does not work, because if you came up with a solution which time complexity is the same as the problem's real full solution, then these two are probably the same (and are easiest to come up with)Thank you so much I will study it