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

×

OneTwo, OneTwo, testing.. unofficial editorial OETW

Since there's a lot of discussion on this problem, I thought I'd share my technique:

Problem pages:
Div1 contest
Div2 contest
Practice

Problem statement:
Find the number of distinct sums of contiguous portions of a given array of $1$s and $2$s.

Analysis:
Probably like most people I thought briefly about summing all combinations, maybe with an accumulated array so it was just a subtraction each time. But the input array bounds seemed(?) too high for that. Looking at the boundary cases though, clearly we can make the array sum, so I coded up the two boundary cases - found using the sum - of all $1$s and all $2$s, which each allow only $n$ sums. Then I realized (first insight) if we have a $2$ on both ends of a mixed array we can't make one less than the sum. In fact we can peel back the array to remove the shorter "tail" of $2$s and know that we have that many possible sums at the top end that we couldn't make.

So what about when there is a $1$ at one end of the array? This is the second insight, more important but enabled by the first one. If we look at the partial sums we can make without that $1$, but including its neighbour, we form a sequence that goes up to the sum of the reduced array. And in that sequence, the biggest jump in values is only $2$ - that is, if say $41$ is somewhere in the middle of that sequence, then either $42$ or $43$ is next. Now if you look at the sums including the end $1$ we were previously disregarding, that will be the same values shifted by $1$, so will fill all the gaps in the previous sequence. So whenever there is a $1$ at one end of the sequence, all sums are possible up to the sum of the sequence.

In case this "second insight" isn't clear, here's a practical example of a sequence with a 1 starting:

1  2  2  1  1  2  1  2  2  2

Partial sums starting from the second element (excluding the edge 1):

   2  4  5  6  8  9 11 13 15

Partial sums starting from the 1:

1  3  5  6  7  9 10 12 14 16

and obviously the second set is each time one bigger (plus the leading 1), giving full coverage of all values from 1 to the sum.

Combining these two insights: find the shorter tail of twos, and the length of that will tell you how many values (to the sequence sum) you can't make. All other values are possible.

My solution

asked 24 Sep '18, 10:30

joffan's gravatar image

5★joffan
9488
accept rate: 13%

edited 27 Sep '18, 21:14


In this Problem, when test case is 2 2 1 1 1 2 2 answer should be 9 . In your test case answer is 9 but i seen so many solution which are accepted are giving answer 10 . @vijju123

link

answered 24 Sep '18, 11:53

blackerror's gravatar image

3★blackerror
213
accept rate: 0%

Yep, the testcases for this question were too weak.

(24 Sep '18, 11:55) krishyadav0072★

I cant guarantee anything, but will see whatever I can do.

(24 Sep '18, 14:03) vijju123 ♦♦5★

How do you like my solution?

link

answered 24 Sep '18, 10:42

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

edited 24 Sep '18, 10:50

OK, but a bit too terse for editorial purposes. It would perhaps have been more impressive if you have solved under the time pressure of the competition itself (before successful competition entries were visible to all). And also if you hadn't posted this solution twice to the board.

(27 Sep '18, 21:17) joffan5★
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:

×15,683
×16

question asked: 24 Sep '18, 10:30

question was seen: 1,362 times

last updated: 27 Sep '18, 21:17