If you want to practice topicwise questions in the ladder way like a2oj , do register on my site http://codedigger.tech after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck.
Singhal has two strings $$$S$$$ and $$$T$$$ consisting of lowercase English Letters.
He wants to obtain string $$$S$$$ lexicographically smallest possible. He can do the following operation any number of times: choose an index $$$pos_1$$$ in the string $$$S$$$, choose an index $$$pos_2$$$ in the string $$$T$$$, and swap $$$s_{pos_1}$$$ with $$$t_{pos_2}$$$.
String $$$p$$$ is lexicographically smaller than string $$$q$$$,
- if $$$p$$$ is a prefix of $$$q$$$, $$$p \neq q$$$
- in the first position where $$$p$$$ and $$$q$$$ differ, the string $$$p$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$q$$$.
For example, abc is lexicographically smaller than abcd , abd is lexicographically smaller than abec , afa is not lexicographically smaller than ab and a is not lexicographically smaller than a.
Note: You have not to minimize number of operations and any index of both string can be chosen more than once.
The first line contains a single integer $$$t (1 \le t \le 100)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.
Each query contains two lines. The first line contains a string $$$S (1 \le |S| \le 100)$$$ , and the second line contains a string $$$T(1 \le |T| \le 100)$$$. $$$|S|$$$ and $$$ |T|$$$ is the length of the string $$$S$$$ and $$$T$$$ respectively.
Note: Both strings will have only lowercase English Letters.
For each test from the input print lexicographical smallest possible string $$$S$$$. Print the answers to the tests in the order in which the tests are given in the input.
5 ab a abc abc abd codedigger dbc a adb codealittle
aa aab abc abc aab
In the first query — swap($$$s_2,t_1$$$) to get smallest lexicographical possible.
In the second query — swap($$$s_2,t_1$$$) to get $$$S$$$ = aac and $$$T$$$ = bbc, then swap($$$s_3,t_1$$$)to get $$$S$$$ = aab.
If you want to practice topicwise questions in the ladder way like a2oj , do register on my site http://codedigger.tech after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck.
Singhal loves Equality. He has a string $$$S$$$ consisting of lowercase English Letters.
He wants to equalize the frequency of all distinct characters in his string $$$S$$$. He can do the following operation any number of times: pick any single character in the string and replace with another lowercase English alphabet.
He wants to perform minimum number of operations to equalize the frequency of distinct characters.
Frequency of a character is number of times it appear in the string.
The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.
Each query contains a single string consisting of lowercase English letters $$$S (1 \le |S| \le 10^5)$$$. $$$|S|$$$ is the length of the string.
It is guaranteed that the total sum of $$$|S|$$$ is at most $$$10^5$$$.
Print $$$t$$$ answers to the test cases. Each answer must be consisting of single integer — the minimum number of operations required to equalize the frequency of distinct characters of string.
6 aba abba abbc abbbc codedigger codealittle
1 0 1 2 2 3
In the first query — We can replace letter $$$b \to a$$$ to form aaa. Now frequency of all distinct character is same i.e. $$$3$$$ or another possibility is replace one $$$a \to c$$$ to form abc. In this case frequency is $$$1$$$.
In the second query — Frequency of all distinct character is Same i.e. $$$2$$$. No need to apply operation.
You are given a bracket sequence $$$s$$$ of length $$$n$$$. The string consists of opening brackets '(' and closing brackets ')' only.
In one move,
- you choose some index $$$i$$$, remove the $$$i-th$$$ character of $$$s$$$ and concatenate the remaining part of string. This move cost $$$a$$$ coins. Example - $$$s$$$ = "(()" choose $$$i=2$$$, remove $$$2nd$$$ character to form "()". $$$$$$OR$$$$$$
- you choose some index $$$i$$$, remove the $$$i-th$$$ character of $$$s$$$ and insert it after all remaining characters of $$$s$$$. This move cost $$$b$$$ coins. Example - $$$s$$$ = ")(()" choose $$$i=1$$$, remove $$$1st$$$ character and insert in end to form "(())".
Your task is to find the minimum number of coins required to obtain regular bracket sequence from $$$s$$$. You can perform any number of moves (including zero).
Recall what the regular bracket sequence is:
- $$$Empty$$$ $$$String$$$ is regular bracket sequence.
- if $$$s$$$ is regular bracket sequence then "(" + $$$s$$$ + ")" is regular bracket sequence.
- if $$$s$$$ and $$$t$$$ are regular bracket sequences then $$$s + t$$$ is regular bracket sequence.
For example, " ", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.
The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.
Each query contains two lines. The first line contains three integer $$$n (1 \le n \le 10^5)$$$: length of string, $$$a ( 1 \le a \le 10^9 )$$$: cost of first operation , $$$b( 1 \le b \le 10^9 )$$$: cost of second operation, all separated by space, and
The second line contains a string consisting of opening and closing brackets only of length $$$n$$$.
It is guaranteed that the total sum of $$$n$$$ is at most $$$10^5$$$.
Print $$$t$$$ answers to the test cases. Each answer must be consisting of single integer — the minimum coins required to obtain a regular bracket sequence from $$$s$$$.
Note: Cost may be greater than $$$2^{32} - 1$$$.
5 2 100 1 )( 2 1 100 )( 3 1 1000 )() 3 1000 1 ()( 5 1000000000 1 )))))
1 2 1 1000 5000000000
In the first query — Choose $$$i=1$$$, remove $$$1st$$$ character and insert in end to form "()".
In the second query — Choose $$$i=1$$$, remove $$$1st$$$ character and Choose $$$i=2$$$, remove $$$2nd$$$ character to form " ".
In the third query — Choose $$$i=1$$$, remove $$$1st$$$ character to form "()".
You have a collection of $$$N$$$ opening brackets '(' and $$$N$$$ closing brackets ')'.
A bracket sequence is $$$N$$$ periodic if it has a period of length $$$N$$$.
Example - ")()(" $$$N=2$$$. It is $$$N$$$ periodic but ")(()" is not.
Your task is to find out how many distinct regular bracket sequence can be formed using these $$$2N$$$ brackets such that sequence is not $$$N$$$ periodic.
As the answer can be rather large, print the remainder after dividing it by $$$1000000007 (10^9 + 7)$$$.
Recall what the regular bracket sequence is:
- "()" is regular bracket sequence.
- if $$$s$$$ is regular bracket sequence then $$$"\texttt{(}" + s + "\texttt{)}"$$$ is regular bracket sequence.
- if $$$s$$$ and $$$t$$$ are regular bracket sequences then $$$s + t$$$ is regular bracket sequence.
For example, "()()", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.
The first line contains a single integer $$$T (1 \le T \le 10^3)$$$ — the number of test cases in the input. Then $$$T$$$ test cases follow.
Each query contains one integer $$$N (1 \le N \le 10^3)$$$: the number of opening and closing brackets you have.
For each test from the input print the number of distinct regular bracket sequence we can form using $$$N$$$ opening bracket and $$$N$$$ closing bracket and sequence is not $$$N$$$ periodic modulo $$$1000000007 (10^9 + 7)$$$.
Print the answers to the tests in the order in which the tests are given in the input.
4 1 2 3 4
1 1 5 12
In the first query — The regular bracket sequence which can be formed by $$$1$$$ opening bracket and $$$1$$$ closing bracket is "()".
In the second query — The regular bracket sequence which can be formed by $$$2$$$ opening bracket and $$$2$$$ closing bracket are "(())" and "()()". We discard second one because "()()" is $$$2$$$ periodic.
In the third query — The regular bracket sequence which can be formed by $$$3$$$ opening bracket and $$$3$$$ closing bracket are "((()))" , "(())()" , "()(())" , "()()()" and "(()())". No one is $$$3$$$ periodic.
If you want to practice topicwise questions in the ladder way like a2oj , do register on my site http://codedigger.tech after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck.
Chitra is playing with consecutive numbers from $$$n$$$ to $$$m$$$ $$$(3\le n+2 \le m \le 10^9)$$$. Singhal tells her that the contest of Number Theory is over and concatenates all the numbers to a String But he miss one number from anywhere in the middle to concatenate.
Example — If she is playing with numbers from $$$3$$$ to $$$7$$$. He can concatenates this in the following way - $$$3567$$$ missing $$$4$$$ or other possibility would be $$$3467$$$, $$$3457$$$, but not $$$4567$$$, $$$3456$$$ , $$$367$$$ , $$$357$$$.
He gave back this concatenated string to her. Help her in finding the missing number. If there are many solution to this, you have to find the minimum possible.
Note: It is guaranteed that a solution smaller than $$$10^9$$$ must exists in the given inputs.
The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.
Each query contains a single concatenated string $$$S (1\le |S| \le 10^5)$$$. $$$|S|$$$ is the length of the string.
It is guaranteed that the total sum of $$$|S|$$$ is at most $$$10^5$$$.
For each test from the input print the missing number $$$ \lt 10^9$$$. Print the answers to the tests in the order in which the tests are given in the input.
4 13 3457 1314151718 234235236238
2 6 16 237
In the first query - the string S = 13, then the sequence is $$$1$$$, $$$3$$$ and the missing number is $$$2$$$.
In the second query - the string S = 3457, then the sequence is $$$3$$$, $$$4$$$, $$$5$$$, $$$7$$$ and the missing number is $$$6$$$.
In the third query - the string S = 1314151718, then the sequence is $$$13$$$, $$$14$$$, $$$15$$$, $$$17$$$, $$$18$$$ and the missing number is $$$16$$$.
In the last query - the string S = 234235236238, then the sequence is $$$234$$$, $$$235$$$, $$$236$$$, $$$238$$$ and the missing number is $$$237$$$.
If you want to practice topicwise questions in the ladder way like a2oj , do register on my site http://codedigger.tech after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck.
The only difference between easy and hard versions is that you have to tell the number of distinct strings in easy version but you have to tell the number of distinct palindromic string in hard version.
Singhal brings a new keyboard consisting of only two English lowercase letters a and b. Somehow keyboard is broken and whenever he press a letter to print on screen , it prints the letter twice or thrice.
Example — If he press letter a , then aa or aaa gets printed on the screen with equal probability.
He wonders that how many distinct string will be printed on the screen if he press letters of a string $$$S$$$ in sequence.
Example — If $$$S = $$$ aba , then he first press a, then b and at last a.
As the answer can be rather large, print the remainder after dividing it by $$$1000000007 (10^9 + 7)$$$.
Note : A palindromic string is a string that reads the same backward as forward, for example strings z, aaa, aba, abccba are palindromes, but strings codedigger, codealittle, ab are not.
The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.
Each query contains a single string $$$S (1\le |S| \le 10^5)$$$ consisting of only two letters a and b. $$$|S|$$$ is the length of the string.
It is guaranteed that the total sum of $$$|S|$$$ is at most $$$10^5$$$.
For each test from the input print the number of distinct string modulo $$$1000000007 (10^9 + 7)$$$. Print the answers to the tests in the order in which the tests are given in the input.
4 a ab aba aa
2 4 8 3
In the first query — The strings which can be print on screen if he press a are aa or aaa.
In the second query — The strings which can print on screen are aabb or aaabb or aabbb or aaabbb.
In the last query — The strings which can print on screen are aaaa or aaaaa or aaaaa or aaaaaa . Note that two strings are same , we have to find the distinct strings.
If you want to practice topicwise questions in the ladder way like a2oj , do register on my site http://codedigger.tech after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck.
The only difference between easy and hard versions is that you have to tell the number of distinct strings in easy version but you have to tell the number of distinct palindromic string in hard version.
Singhal brings a new keyboard consisting of only two English lowercase letters a and b. Somehow keyboard is broken and whenever he press a letter to print on screen , it prints the letter twice or thrice.
Example — If he press letter a , then aa or aaa gets printed on the screen with equal probability.
He wonders that how many distinct palindromic string will be printed on the screen if he press letters of a string $$$S$$$ in sequence.
Example — If $$$S = $$$ aba , then he first press a, then b and at last a.
As the answer can be rather large, print the remainder after dividing it by $$$1000000007 (10^9 + 7)$$$.
Note : A palindromic string is a string that reads the same backward as forward, for example strings z, aaa, aba, abccba are palindromes, but strings codedigger, codealittle, ab are not.
The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.
Each query contains a single string $$$S (1\le |S| \le 10^5)$$$ consisting of only two letters a and b. $$$|S|$$$ is the length of the string.
It is guaranteed that the total sum of $$$|S|$$$ is at most $$$10^5$$$.
For each test from the input print the number of distinct palindrome string modulo $$$1000000007 (10^9 + 7)$$$. Print the answers to the tests in the order in which the tests are given in the input.
4 a ab aba aa
2 0 4 3
In the first query — The strings which can be print on screen if he press a are aa or aaa From these strings all are palindrome also, so number is 2.
In the second query — The strings which can print on screen are aabb or aaabb or aabbb or aaabbb. None of them are palindrome.
In the last query — The strings which can print on screen are aaaa or aaaaa or aaaaa or aaaaaa . Note that all strings are palindrome and two strings are same , we have to find the distinct palindrome strings.
If you want to practice topicwise questions in the ladder way like a2oj , do register on my site http://codedigger.tech after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck.
Singhal has a string $$$S$$$ consisting of lowercase English letters. He wants to form lexicographical smallest string by applying a operation atmost once.
Operation is —
Choose three distinct indices $$$i_1,i_2,i_3$$$ such that $$$1\leq i_i \lt i_2 \lt i_3 \leq |S|$$$, where $$$|S|$$$ is the length of string and perform cyclic right shift on these indices.
If value at $$$i_1,i_2,i_3$$$ is $$$s_1,s_2,s_3$$$, then after performing right cyclic shift on these indices, value at indices will change to $$$i_2\to s_1 , i_3\to s_2 , i_1\to s_3$$$.
Example - $$$S = $$$ "codedigger". Chosen indices is $$$1,2,3$$$ then resultant string will be $$$S = $$$ "dcoedigger".
A string a is lexicographical smaller than a string b if and only if one of the following holds:
- a is a prefix of b, but a$$$\neq$$$b;
- in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.
Each query contains a string $$$S(1\leq |S| \leq 10^5)$$$ consisting of lowercase English letters. $$$|S|$$$ is the length of the string.
It is guaranteed that the total sum of $$$|S|$$$ is at most $$$10^5$$$.
Print $$$t$$$ answers to the test cases. Each answer must be consisting of single lexicographical smallest possible string.
5 aba abc acb codedigger codealittle
aab abc acb cddoeigger acdeolittle
In the first query, apply right cyclic shift on indices $$$1,2,3$$$ to get the smallest possible string $$$S=$$$ aab.
In the second or third query , if we apply operation we get lexicographical larger string. So we will not apply any operation.