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

×

Segment tree

Problem link:-https://www.codechef.com/problems/QPALIN How to use segtree in such questions...I have done practice of some questions(basic) using segtree? here comes string.

asked 01 Apr '17, 11:02

adhish_kapoor's gravatar image

3★adhish_kapoor
90410
accept rate: 9%


You can solve it by segment tree or BIT.

Here's my solution using BIT > link text

Solution

We need to find number of odd characters in interval l to r. If it is less than 2 then answer will be YES else NO.

So we need to maintain a frequency array for each alphabet in the range 1 to n. Answer each query in logn complexity which can be done using BIT/segment tree.

link

answered 01 Apr '17, 12:26

dushsingh1995's gravatar image

4★dushsingh1995
92213
accept rate: 11%

edited 01 Apr '17, 12:27

I just looked at its editorial and found a very interesting optimization. We can solve it without creating hash tables or 26-length array in each node. We will use a very beautiful property of XOR operation, which is, XORing same number even number of times cancels out.

For, e.g, 2 ^ 3 ^ 1 ^ 2 = 1 ^ 3

Thus only those terms gets XORed which appear odd number of times, we can use this to our advantage. Since we are using 26 character in our string, each character can be thought as integer whose only ith bit is set to 1 and i = ASCII(character) - 97. Thus we would be needing at most 26 bits, and thus normal "int" would suffice for our purpose. For merging two nodes, just XOR the numbers, and finally check the number of bits set to 1.

If you are still confused, then look at this, almost same as the previous one. Solution

link

answered 01 Apr '17, 18:30

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%

2

Neat! Similar approach is used here > http://codeforces.com/contest/570/problem/D

(01 Apr '17, 21:23) dushsingh19954★

If you are concerned just about how to handle string, then you can replace them with their ASCII number. Following observations are sufficient to solve this problem

1) if the string has even length it can be palindrome iff all the characters have even frequency of occurrence

2) if the string has odd length it can be palindrome iff exactly one character has odd frequency of occurrence

BIT works faster than Segment-Tree, but not asymptotically. So if you already know BIT then you should see dushsingh1995 solution. Otherwise, here is one Segment-Tree based solution for you Solution

EDIT : you can further reduce these observations to one pointed out by dushsingh1995

link

answered 01 Apr '17, 13:49

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%

edited 01 Apr '17, 14:34

@ashwanigautam Ok...I will definitely try it out...thanks

link

answered 01 Apr '17, 14:24

adhish_kapoor's gravatar image

3★adhish_kapoor
90410
accept rate: 9%

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,700

question asked: 01 Apr '17, 11:02

question was seen: 425 times

last updated: 01 Apr '17, 21:23