Puzzle#1 – Level ( Solvable in your sleep )

Given a string, , of lowercase letters, determine the index of the character whose removal will make a palindrome. If is already a palindrome or no such character exists, then print . There will always be a valid solution, and any correct answer is acceptable. For example, if “bcbc”, we can either remove ‘b’ at index or‘c’ at index .

Input Format

The first line contains an integer, , denoting the number of test cases.
Each line of the subsequent lines (where ) describes a test case in the form of a single string, .

Constraints

  • All characters are lowercase English letters.
  • 1 < = T < = 20
  • 1 <= S <= 100000 + 5

Output Format

Print an integer denoting the zero-indexed position of the character that makes not a palindrome; if is already a palindrome or no such character exists, print .

 

Solution ( 1 of many options )

Runtime = O(N*1/2N) -> O(N²)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int checkPerIndex(int arrayA[], int len,int checkIndex){
int result = -1;
int j = len – 1;
int i = 0;
while(i <= j){
if(checkIndex == i){
i++;
continue;
}
if(arrayA[i] != arrayA[j]){
if(i > checkIndex){
result = i;
}
break;
}
i++;
j–;
}

return result;
}

void palindromcompare(int arrayA[], int len){
int skipfrontindex = -1;
int skipbackindex = -1;
for(int i = 0;i<len;i++){
if(arrayA[i] != arrayA[len-1-i]){
skipfrontindex = i;
skipbackindex = len-1-i;
int result = checkPerIndex(arrayA, len, skipfrontindex);
if(result == -1){
printf(“%d\r\n”,skipfrontindex);
break;
}
else if(result == skipbackindex){
printf(“%d\r\n”,skipbackindex);
break;
}
result = checkPerIndex(arrayA, len, skipbackindex);
if(result == -1){
printf(“%d\r\n”,skipbackindex);
break;
}
}
}

if(skipfrontindex == -1 && skipbackindex == -1){
printf(“-1\r\n”);
}
}

int main()
{
int n = 0;
scanf(“%d”,&n);
for(int i=0;i<n;i++){
char sean[100000];
scanf(“%s”,sean);
int len = strlen(sean);
int fwarray[len];

for(int k=0;k<len;k++){
int abplace = (int)sean[k] % 32;
fwarray[k] = abplace;
}

palindromcompare(fwarray,len);

}

return 0;
}

 Puzzle #2 Level ( Meh… not so easy but not a brain surgery )

You are given two strings, and . Find if there is a substring that appears in both and .

Input Format

Several test cases will be given to you in a single file. The first line of the input will contain a single integer , the number of test cases.

Then there will be descriptions of the test cases. Each description contains two lines. The first line contains the string and the second line contains the string .

 

Output Format

For each test case, display YES (in a newline), if there is a common substring. Otherwise, display NO.

Constraints

All the strings contain only lowercase Latin letters

1 < = T <= 10

1 <= |A|,|B| <= 1000000

 

Solution

#include “stdio.h”
#include “string.h”

int main()
{

int inputnum = 0;
scanf(“%d”,&inputnum);
char first[1000000];
char second[1000000];

for(int i=0;i<inputnum;i++){
scanf(“%s”,&first);
scanf(“%s”,&second);
int found = 0;

int firstint[27] = {0};
int secondint[27] = {0};

if(strlen(first) < strlen(second)){
for(int j = 0;j<strlen(first);j++){
int ia = (int)((first[j] – ‘0’) % 48 );
if(ia > 0){
firstint[ia] = 1;
}
}

for(int j = 0;j<strlen(second);j++){
int ia = (int)((second[j] – ‘0’) % 48 );
if(ia > 0 && firstint[ia] == 1){
found = 1;
printf(“YES”);
break;
}
}
}
else if(strlen(first) > strlen(second)){
for(int j = 0;j<strlen(second);j++){
int ia = (int)((second[j] – ‘0’) % 48 );
if(ia > 0){
secondint[ia] = 1;
}
}

for(int j = 0;j<strlen(first);j++){
int ia = (int)((first[j] – ‘0’) % 48 );
if(ia > 0 && secondint[ia] == 1){
found = 1;
printf(“YES”);
break;
}
}
}
else{
for(int j = 0;j<strlen(second);j++){
int sia = (int)((second[j] – ‘0’) % 48 );
int fia = (int)((first[j] – ‘0’) % 48 );
if(sia == fia){
found = 1;
printf(“YES”);
break;
}
}
}

if(found == 0){
printf(“NO”);
}

printf(“\r\n”);
}
return 0;
}

 Puzzle #3 Level ( It’s kind of interesting )

Jose found a love letter his friend Richard has written for his girlfriend. Jose is a prankster, so he decides to meddle with the letter. He changes all the words in the letter into palindromes.

To do this, he follows two rules:

  1. He can reduce the value of a letter, e.g. he can change d to c, but he cannot change c to d.
  2. In order to form a palindrome, if he has to repeatedly reduce the value of a letter, he can do it until the letter becomes a. Once a letter has been changed to a, it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations required to convert a given string into a palindrome.

Input Format

The first line contains an integer , i.e., the number of test cases.
The next lines will contain a string each. The strings do not contain any spaces.

Constraints

1 <= T <= 10

1 <= string len <= 100000

 

 Puzzle #4

You are given a 2D array with dimensions 6*6. An hourglass in an array is defined as a portion shaped like this:

a b c
  d
e f g

The sum of an hourglass is the sum of all the numbers within it.

Mission: Print the largest sum among all the hourglasses in the array.

Input Format

There will be exactly 6 lines of input, each containing 6 integers separated by spaces. Each integer will be between -9 and 9, inclusively.

Output Format

Print the answer to this problem on a single line.

Advertisements