×

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$.

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

719436377
accept rate: 0%

19.7k350498541

 2 Simply insert all 2 length contiguous substrings in a set and display the size of the set :) answered 27 Dec '15, 14:29 291●2●3●19 accept rate: 10% Insertion costs you lgN time. Should lead to a TLE. (15 Apr '16, 20:06) arpanb83★
 1 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 answered 27 Dec '15, 14:41 3★akshayv3 157●8 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★
 0 just push all 2 length string in a set and print out size of set answered 14 Nov '18, 15:08 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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