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

×

Codechef CHRL2

Codechef Lunchtime 08 Question CHRL2 http://www.codechef.com/problems/CHRL2

Editorial suggests a DP solution in O(n^2)

I was thinking of a different solution. Obviously , I got a WA. But I can't figure out the mistake can anyone help ?

Suppose we store all the occurrences of C,H,E,F seperately.

Then we match each C to the first H which comes after it and then with first E that comes after H and first F that comes after E. And proceed accordingly.

for eg. in CHHHEEEFFCC vc -> 0, 9, 10 vh -> 1,2,3 ve -> 4,5,6 vf -> 7,8

now vc[0] = 0; we can match it with 1(i.e H), 4, and 7 Now vc[1] = 9 There is no i such that vh > 9 Therefore program ends.

Can anyone point out the mistake ?

~Thanks

asked 12 Jan '15, 23:40

do_or_die's gravatar image

3★do_or_die
11
accept rate: 0%

edited 13 Jan '15, 14:33

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:

×2,172
×550
×86

question asked: 12 Jan '15, 23:40

question was seen: 615 times

last updated: 13 Jan '15, 14:33