Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

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

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

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

1 | 1-gon | 207 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

5 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 171 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Educational Codeforces Round 30

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2021 05:51:18 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

In problem E, first I solved it using segment tree after iterating in two loops but I got TLE.

Then I replaced the segment tree with a liner search and I got ACC. How did that happen?

This is my first submission (31286366) which had TLE. My second submission (31286415) which passed.

F — good demonstration of overkill in using suffix array.

It is most powerful suffix structure, but anyway it needs additional lcp array, prefix sums array, stack...

Suffix automaton is better here, bcs its need only... one array cnt[]!

GL, kids.

Edit: Please ignore!

can someone please explain me E ! I didn't understand how to keep all the three maximum possible at a time. if we want to maximize the first one we can (just give 2 to smallest and rest with 1) but this is not the case here !

please help me !

The first two numbers are fixed, when you do these two loops. You just have to choose the third number maximum possible.

Can somebody share the implementation of the solution given for 873B and explain "That leads to a solution: for each value of balance maintain the minimum i where this balance is obtained (let it be called minIndex), and for each index i in the string update answer with i - minIndex(balance(i))"?

input() d={0:-1} a=b=0 for i,c in enumerate(input()): b+=2*int(c)-1 d[b]=x=d.get(b,i) a=max(a,i-x)

## print(a)

a is used to get maximum length and initialize with 0 ------------------------------------------- b+=2*int(c)-1,here int(c) equals 0 or 1,it's like cnt1-cnt0,to calculate balance[i] d[b]=x=d.get(b,i),the d is dictionary to record the minIndex,when d.get(balance[i])is None, meaning that it's not recorded yet,so d[b]=i;when d[b] is not None,meaning that it' match the balance condition,we get it as x for calculate the length i-x, just the i -minIndex; a is used to get the max length among loop,a initialize with 0;

My solution for problem B. Balanced Substring, 47370595.

AlgorithmI replaced all the 0's with -1, hence now we have to find longest subsequence with sum 0. I have used hashing, and the concept is to iterate through the array and find sum for

`array[i]`

, if present before then there is already a zero sum subsequence, and update the value accordingly.Can anyone help me the editorials logic ?

Isn't this problem similar to 1278C - Berry Jam ?

For B , change each 0 with -1 and then answer becomes the max length subarray having sum as 0.