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

×

Magical Strings - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sumeet Verma
Tester: Aman Kedia
Editorialist: Sidhant Bansal
Prerequisites - Pigeon Hole Principle, Disjoint Set Union
Difficulty : Easy - Medium
Expected Complexity: O(N*N)
Editorial -

  1. Find the mid-point of each range (query) and if there are many queries having the same mid-point then only retain that query whose length is max, i.e (where r - l is maxm)
  2. This would have reduced the number of queries to 2*N at max, since there are 2*N number of mid-points in a string of length N.
  3. Now for each query do dsu union of element l with r, (l + 1) with (r - 1), (l + 2) with (r - 2) and so on. We do this because the character which would be put on the index l would be same as the one we put on index r. Extending this logic to all queries we need to maintain dsu. So basically all the elements of one component of dsu should have the same letter on them.
  4. After processing all the queries, let the number of dsu components be x, then the answer is 26x

Complexity Analysis: O(N * N) because we do an O(N) iteration for each query and total number of queries can be 2N, therefore O(2N*N). Here I have ignored the constant of union-find for simplicity.

This question is marked "community wiki".

asked 26 Nov '15, 01:08

sidhant007's gravatar image

6★sidhant007
179215
accept rate: 12%

edited 26 Nov '15, 12:36

admin's gravatar image

0★admin ♦♦
15.9k347484508


Can anyone explain how a string of length N can have 2*N midpoints ?

link

answered 26 Nov '15, 20:42

lakshmi8's gravatar image

2★lakshmi8
461
accept rate: 14%

N for odd length ranges and N for even. :)

(26 Nov '15, 23:33) vikky_codder6★

Yeah !! Thats what I even thought of :) Thanks a lot

(27 Nov '15, 11:17) lakshmi82★

Hi, the following is my code: http://ideone.com/1ElezS (I couldn't get the inline code function to work, sorry for the external link).

When I submit however, I'm getting TLE. Can you please point out any errors? My approach is basically DSU.

Thanks :)

link

answered 28 Nov '15, 13:39

hypothesist's gravatar image

2★hypothesist
1
accept rate: 0%

Can anyone please explain it in simple terms. Thnaks.

link

answered 28 Nov '15, 15:38

glow's gravatar image

3★glow
6311
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:

×77
×50
×24

question asked: 26 Nov '15, 01:08

question was seen: 2,112 times

last updated: 28 Nov '15, 15:38