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

×

NIKITA AND STRING

http://codeforces.com/contest/877/problem/B i am not getting the tutorial(just a few line ) ...need some help on how to approach

asked 24 Oct '17, 14:45

popo_popo333's gravatar image

3★popo_popo333
154
accept rate: 0%


The tutorial does this by using prefix and suffix arrays.

In 1 prefix arrays, we store the number of 'a's encountered till now FROM START. In another prefix array, number of 'b' we encountered till now FROM START.

Now, start from the end of string. Can you see how we can use this information for final answer?

What I think the editorial does is, that it takes a pair of indices i and j, and fixes them as "We will consider b's inside this block" (number of b inside block can be found using prefix array we made) and then counts a's outside the block. The sum is the final answer.

But you can also get an $O(N)$ solution for it. I havent tested it yet, but I think if we go from end, keeping a count of 'a' encountered till now, then we can use the prefix array of 'a' and 'b' directly to find the max length. Like, keep going on till its 'a', on encountering a 'b', make a second pointer and make it go to the start of that block of 'b' char, and then sue prefix arrays. Then resume from the start of block. Did not test it yet, but should be correct.

link

answered 24 Oct '17, 14:52

vijju123's gravatar image

4★vijju123 ♦♦
15.4k12066
accept rate: 18%

I didnt read the editorial but let me explain my approach if it helps.See first you need to be sure a solution always exists which is clear from the line "subsets can be empty". Now i define my dp states. Let n be the index i am currently at,changes be the no.of switches i have made till now(switching means i have completed forming a subarray and is forming another one now. I.e suppose i was forming a subarray of a's when i start forming a subarray of b's i say i am switching. So its clear maximum no.of switches can be 2, first from a to b then from b to a.) And last which is 0 if i chose last element in my current subarray as a or 1 if b.(so its clear switching occurs when i change last from 1 to 0 or vice versa). Now my dp state reduces to: F(n,change,last)={ If s[n]==last F(n-1,change,last)+1 else max(F(n-1,change,last),F(n-1,change+1,last^1)+1) } At any step if last==sn we will include it in forming our subarray so we add it to our set else we can either choose to add it in our set or not. To add it we need to make a change. hope this helps. Here is the link to my solution:http://codeforces.com/contest/877/submission/31640788. If u have any doubts feel free to ask else if it helped please give a thumbs up :)

link

answered 24 Oct '17, 15:47

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

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:

×672
×643
×33

question asked: 24 Oct '17, 14:45

question was seen: 614 times

last updated: 18 Mar '18, 16:08