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

×

DISTCODE - Editorial

Problem Link:

Practice
Contest

Difficulty:

CakeWalk

Pre-requisites:

Basic Language Constructions

Problem:

Find the number of distinct consecutive 2-letter substrings of the string $S$.

Explanation:

Solution for the subtask 1 (35 points):

If $|S| = 2$, then there is only one possible substring - the string $S$. So, the answer is $1$.

If $|S| = 3$, then if all letters in the string are the same, then the answer is $1$, otherwise there are $2$ distinct consecutive $2$-letter substrings, so, the answer is then $2$.

Solution for all subtasks:

Consider a boolean array $A[][]$ of $26$x$26$ elements.

Let $A[i,j]$ be true if there is a substring of $S$ with first letter - the $i$th Latin alphabet letter and the second letter - the $j$th Latin alphabet letter.

Initially all elements of $A[][]$ are false.

Let's iterate through the symbols of the string $S$ and set true all elements of $A$ for the corresponding substrings. Note, that $S$ is $1$-indexed in the given pseudocode.

The pseudocode for the same follows:

For k := 2 to |S| A[S[k-1], S[k]] = true;

The last step is to iterate through the array $A$ and calculate the number of elements $A[i,j]$ such that $A[i,j]$ is true.

The complexity is $O(|S|)$ for a single test case.

Setter's Solution:

Can be found here

Tester's Solution:

Can be found here

asked 22 Dec '15, 21:24

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 0%

edited 27 Dec '15, 14:26

admin's gravatar image

0★admin ♦♦
19.7k350498541


Simply insert all 2 length contiguous substrings in a set and display the size of the set :)

link

answered 27 Dec '15, 14:29

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2912319
accept rate: 10%

Insertion costs you lgN time. Should lead to a TLE.

(15 Apr '16, 20:06) arpanb83★

Instead of using Set or the method given in editorial I stored all the contiguos character elements of length 2 in a 2-D character array and sorted that array using quicksort. Complexity-(O(t*N(logN)) Result-SIGSEGV Reason-?

Can u suggest a valid test case for which it is giving SIGSEGV,I have tried all the manual ones. Here is my solution link- https://www.codechef.com/viewsolution/9027818

link

answered 27 Dec '15, 14:41

akshayv3's gravatar image

3★akshayv3
1578
accept rate: 4%

a string with 10000 identical chars. Yields a stackoverflow because:

1) Your quicksort implementation is quadratic in this case (and is implemented recursively). 2) You allocate an array temp of size 10000 for each function call.

Reducing size of temp to 3 will probably eliminate SIGSEV - but maybe the algorithm is still TLE

(27 Dec '15, 15:10) ceilks7★

@ceilks declaring temp globally removed SIGSEGV but got TLE on last subtask. REASONS? The upper limit on the no. of test cases is 100 and quicksort is implemented in NlogN it should have passed in 1s but it didnt. If I stick to this method can u suggest any optimised version of quicksort here(may be by chosing different pivot).

(27 Dec '15, 15:33) akshayv33★

just push all 2 length string in a set and print out size of set

solution:-https://www.codechef.com/viewsolution/21622540

link

answered 14 Nov '18, 15:08

arun_1713's gravatar image

3★arun_1713
1
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:

×1,610
×76
×38
×28
×12
×2
×2

question asked: 22 Dec '15, 21:24

question was seen: 2,667 times

last updated: 14 Nov '18, 15:08