The life of a coder

Abridged problem statement Compute  A N! % P Constraints 1 ≤ T ≤ 100. Small dataset 1 ≤ A ≤ 10. 1 ≤ N ≤ 10. 1 ≤ P ≤ 10. Large dataset 1 ≤ A ≤ 10 5 . 1 ≤ N ≤ 10 5 . 1 ≤ P ≤ 10 5 . Approach   Just use the fact that  A m*n = (A m ) n A m*n % P = ( (A m % P) n % P ) Code # include < iostream > using namespace std ; int power ( long long x , int n , int M ) { long long result = 1 ; while ( n > 0 ) { if ( n % 2 = = 1 ) result = ( result * x ) % M ; x = ( x * x ) % M ; n = n / 2 ; } return result ; } int main ( ) { freopen ( " A-large-practice.in " , " r " , stdin ) ; freopen ( " output-large.txt " , " w " , stdout ) ; int t , a , n , p ; long long ans ; cin > > t ; for ( int i = 1 ; i < = t ; i + + ) { cin > > a > > n > > p ; ans = a ; fo...

Abridged problem statement Count Number of ways to select four points in RxC grid such that these four points make  a square. These squares need not be aligned with the axes. Constraints 1 ≤ T ≤ 100. Small dataset R, C < 10 3 Large dataset R,C < 10 9 Print answer modulo 10 9 + 7 Approach   Let us assume  C >= R. First count all the squares that are aligned with the axes:             number of 1x1 squares is (R-1)*(C-1)             number of 2x2 squares is (R-2)*(C-2)             ...             number of RxR squares is (R-R)*(C-R) Now count all the squares not aligned with the axes:           We can see from the above image that a N x N square has N enclosing squares( including the green squares we counted in the...

Abridged problem statement Given the number of left and right parenthesis, output the maximum number of balanced substrings in all possible subsets of the string. Constraints 1 ≤ T ≤ 100. Small dataset 0 ≤ L ≤ 20. 0 ≤ R ≤ 20. 1 ≤ L + R ≤ 20. Large dataset 0 ≤ L ≤ 10 5 . 0 ≤ R ≤ 10 5 . 1 ≤ L + R ≤ 10 5 . Approach   Let us try to obtain the answer manually for certain cases. Case 1: L = 1, R = 1 We can form only ( ) string which conatains 1 balanced substring. Case 2: L = 2, R = 2 We can form ( ) ( ) which contains 3 balanced substrings, i.e. index 1 to 2, index 3 to 4, index 1 to 4. Case 3: L = 3, R = 3 We can form ( ) ( ) ( ) which contains 6 balanced substrings, i.e. with indices 1 to 2,  3 to 4,  5 to 6, 1 to 4, 3 to 6, 1 to 6. Case 4: L = 4, R = 4 We can obtain 10 balanced substrings from ( ) ( ) ( ) ( ). Hence we obtain the series 1, 3, 6, 10, ... This forms the set of triangular numbers: where a(n) = bi...

Abridged problem statement In an election where candidate A receives N votes and candidate B receives M votes with N > M , what is the probability that A will be strictly ahead of B throughout the count.   Problem Statement Constraints 1 ≤ T ≤ 100 Small dataset 0 ≤ M < N ≤ 10 Large dataset 0 ≤ M < N ≤ 2000 Approach   This problem is a combinatorics problem which can be solved using the Bertrand's Ballot Theorem. The closed form solution for this problem is (N - M) / (N + M) For more information refer to this article Bertrand's ballot theorem . Code # include <iostream> # include <iomanip> # include <fstream> using namespace std ; int main (){ int t, m, n; freopen("inputlarge .in ", "r", stdin); freopen("outputlarge .txt ", "w", stdout); cin>>t; for(int cases = 1; cases <=t; cases++){ float ans; cin>>n>>m; ans =...

Abridged problem statement Given a set of strings output the string with the highest number of distinct characters. In case two strings have the same number of characters, output the lexicographically smallest one.   Problem Statement Constraints 1 ≤ T ≤ 100 1 ≤ N ≤ 100 Approach Initialize an integer to max to 0 and string leader to empty string for every test case. For every name initialize  char_arr to 0. For every character in the name if char_arr[index of character] equals 0 then increment char_arr[index of character] and count. At the end of the iteration count holds the number of distinct characters in the name. If count is greater than max , then update max to count and leader to the current name . if count equals max , then update leader to lexicographically smallest of leader and current name. Code  # include <iostream> # include <vector> # include <cstring> # include <fstream> using namesp...