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

×

PRCS16E - Editorial

PROBLEM LINK:

Practice
Contest

Author: Mohit Wadhwa
Tester: Parth Mittal
Editorialist: Parth Mittal

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Segment Trees

PROBLEM:

Given numeric string $str$ where $str_i \in \{0..9\}$. We call $(x_1, x_2, x_3, x_4)$ quadruple a palindromic quadruple of string $S$ if it satisfies the following criteria : $S_{x_1} = S_{x_4}$ and $S_{x_2} = S_{x_3}$ where $x1 < x2 < x3 < x4$. Queries are:
1 i j : Print number of different palindromic quadruples $(x_1, x_2, x_3, x_4)$ for string $str$ such that $i ≤ x1 < x2 < x3 < x4 ≤ j$. $\mod 10^9 + 7$.
2 idx ch : Replace $str_{idx}$ with character $ch$.

EXPLANATION:

We can use a segment tree with some clever information in the nodes to solve this task.
Let's say we already know the answer for the two children of a node, then what additional information do we need to compute the answer for this node?
We are looking for sub-sequences of the kind abba, where $a, b \in \left\{0, 1, \dots , 9\right\}$. Possibilities are:

  • abba in left child

  • abba in right child

  • a in left child, bba in right child (and its symmetric case)

  • ab in left child, ba in right child.

So we need to store number of ways to generate these for each node too.
Note that to compute these, we need no more additional information.
Hence we have an $O(N\log N \times \texttt{alpha}^2)$ solution, where $\texttt{alpha}$ is the size of the alphabet.

This question is marked "community wiki".

asked 12 Oct '16, 23:14

rounaqwl66's gravatar image

2★rounaqwl66
263
accept rate: 25%

edited 02 Jan '17, 19:18

admin's gravatar image

0★admin ♦♦
19.7k350498541

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,480
×1,726
×1,236
×21
×1

question asked: 12 Oct '16, 23:14

question was seen: 595 times

last updated: 02 Jan '17, 19:18