COMPRESSVD Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Kanhaiya Mohan
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

940

PREREQUISITES:

None

PROBLEM:

Chef recorded a video explaining his favorite recipe. However, the size of the video is too large to upload on the internet. He wants to compress the video so that it has the minimum size possible.

Chef’s video has N frames initially. The value of the i^{th} frame is A_i. Chef decides to remove a frame only if its value is equal to the value of either of its neighbors.

Find the minimum number of frames Chef can achieve.

EXPLANATION:

Basically in this problem we need to calculate the total number of substrings having same characters. Here the video is considered as a string with each frame as individual character.

Initially we start with n frames. On traversing the string whenever we find two adjacent frames as equal, we can decrement our frames by 1, since those two frames would belong to the same substring.
After traversing we would get the final answer as frames.

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution