DISTCODE - Editorial

general
, , , , , ,
1

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 ith Latin alphabet letter and the second letter - the jth 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

2

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

2 Likes
3

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

1 Like
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

5

@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).

6

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

7

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

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