You are not logged in. Please login at www.codechef.com to post your questions!

×

HAPPYARR - Editorial

Happy Array

Problem :
practice

Tags: Dynamic Programming, Prefix sum.

Author: Shami.
Tester: Naman

There are multiple ways to look at this problem.

1.Longest Increasing Subsequence A sequence (not necessarily contiguous) with leading 0s and (possibly) ending with 1s is essentially a weakly increasing subsequence. As such, we can compute the LIS for the array that will give you the answer.

This problem had weak testcases, which allowed O(N^2) LIS solutions to be accepted. However, LIS can be computed in O(Nlog(K)) as well.

2.For each 0, the longest length of happy array is, at least, number of 0s to the left (including itself) and number of 1s to the right. We can use prefix sums to compute the number of 1s at each index and use it to compute the longest possible happy array for each 0. Not using prefix sum array will cause this algorithm to degenerate to O(N^2), which is same as above.

asked 12 Jan, 15:49

mmmreddy's gravatar image

0★mmmreddy
121
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,878
×178

question asked: 12 Jan, 15:49

question was seen: 349 times

last updated: 12 Jan, 15:49