Before contest

Codeforces Round #680 (Div. 1, based on Moscow Team Olympiad)

18:09:12

Register now »

Codeforces Round #680 (Div. 1, based on Moscow Team Olympiad)

18:09:12

Register now »

*has extra registration

Before contest

Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad)

18:09:12

Register now »

Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad)

18:09:12

Register now »

*has extra registration

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

1 | tourist | 3619 |

2 | Um_nik | 3493 |

3 | ecnerwala | 3446 |

4 | Radewoosh | 3383 |

5 | ksun48 | 3357 |

6 | yosupo | 3324 |

7 | Benq | 3299 |

8 | maroonrk | 3243 |

9 | apiadu | 3238 |

10 | Petr | 3217 |

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

1 | Errichto | 207 |

2 | Monogon | 196 |

2 | SecondThread | 196 |

4 | vovuh | 188 |

5 | pikmike | 186 |

6 | Um_nik | 185 |

6 | antontrygubO_o | 185 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/31/2020 19:55:48 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I'll try to explain my solution. Firstly, I hope you get that you never need to make more than 2 triples of the format [x, x + 1, x + 2] (Claim 1). Now create a tile frequency array from 1 to m. We'll apply DP on this starting from 1 till m. DP state is dp[i][j][k], where i is the last index of the prefix considered, j is the number of tiles remaining of size (i — 1) and k is the number of tiles remaining of size i. Because of the claim 1, we never need to store more than 2 tiles of size (i — 1) and 4 tiles of size i for later operation (Why?). To make the transition to (i + 1), you can iterate for all possible values of j and k. https://codeforces.com/contest/1110/submission/49606713. (Note that DP state with -1 as value is representing the impossible state.)

Firstly, I hope you get that you never need to make more than 2 triples of the format [x, x + 1, x + 2]--> sorry , but i didn't get . what will happen if we take 3 triplets , will it lead to wa ?Thanks PrakharJain , i get it . 4 tiles of size i is bcoz 2 for i-1 and i pair and 2 for i and i+1 pair . its quite hard to come up with this idea on own .

No. Because you can always replace 3 triples of this format to 3 triples [x, x, x], [x + 1, x + 1, x + 1] and [x + 2, x + 2, x + 2].

At first, let's notice that it isn't worth taking 3 times or more [

x,x+ 1,x+ 2], we can take [x,x,x], [x+ 1,x+ 1,x+ 1], [x+ 2,x+ 2,x+ 2] instead.Now let's compute how many times number

xis present for any validx. Denote the value bycnt[x].Now let's calculate

dp[i][j][k] (in this dp we consider all numbers from the given array that are less thani- 1,cnt[i- 1] -k(k is up to 3) numbers which are equals toi- 1 andjnumbers which are equal toi(j is up to cnt[i]),dp[i][j][k] is the answer for these numbers)How to calculate it? As we know, there is no point in taking 3 times [

x,x+ 1,x+ 2], sodp[i][j][k] =max(dp[i- 1][cnt[i] -l][l] + (j-l) / 3),l< 3. That's because we can take [i- 2,i- 1,i] 0, 1 or 2 times. If we take itltimes, than we have (j-l) numbers that are equals to i and we have to divide them into groups of the type [i, i, i]. Also we have to divide the other numbers, but we know that the answer, it is dp[i — 1][cnt[i] — l][l]Hope, my answer will help you. Ask me if you have any questions :D

thanks i get it . Miraak

Hi, Can you please explain why "it isn't worth taking 3 times or more [x, x + 1, x + 2]". Because in both the cases I am having the answer as 3. What advantage I am having by considering [x, x, x], [x + 1, x + 1, x + 1], [x + 2, x + 2, x + 2] instead of 3 times of [x, x + 1, x + 2].