CPP notes

DP States - Cheatsheet dp[i] = Best result starting/ending at i position amongst all solutions must include the i position in solution --> Kadane dp[l][r] = for operations in subarray A[l..r]  Perform some operation on two sequences A[i..n] and B[j..n] --> like LCS dp[i][mask] = for array with bitmask Can decrease complexity by solving recurrence relation OBSERVE  f(i, k) = f(i+1, k-0) + f(i+1, k-1) + ... + f(i+1, k-(i-1)) f(i, k-1) = f(i+1, k-1) + f(i+1, k-2) + ... + f(i+1, k-(i-1)) + f(i+1, k-i) Finally, f(i, k) = f(i, k-1) + f(i+1, k-0) - f(i+1, k-i) Good Practices  use (~dp[i]) instead of (dp[i] != -1) use ans/ tmp instead of dp[ind][states] bcz can be long and hectic return dp[i] = ans => assigns and returns at the same time If string acts as state --> NEVER pass by reference bcz if value changes at address --> affect other previously stored values use int as return type NOT bool => bcz 3 dp values --> -1, 0, +1 and also -1 acts as true NOT ...

For interactive problem  [your solution and the interactor exchange the data and decide what to print based on the "history of communication"]:  if you output some data it is possible that this data is first placed to some internal buffer and may be not directly transferred to the interactor =>  better to use endl (it flushes automatically)  after every output   can also use fflush(stdout) or cout<<flush   Only use with cout (NOT with cin) Input/output here works much slower than in usual problems — try to use scanf/printf instead of cin/cout try to find relation between number of query and number of input eg.- q=(5/2)*n => for q=5 --> n=2 means using 5 queries u can find 2 elements of array now make an ALGO keeping above thing in mind ios_base :: sync_with_stdio ( false ); This disables the synchronization between the C and C++ standard streams. Now, printf and cout are not in sync. Eg.-printf("2\n") cout<<"1"  --> B...

  Time complexity vs No. of iterations Time complexity --> how algorithm scales with data (means for very large n) Eg.- N² v/s 1000*n ==> for small n --> N² is better but very negligible difference But for large n ---> huge difference (seconds v/s hours)   Big Oh - supremum     (worst case) Big Omega - infimum      ( best case) Big Theta - lies in range [infimum,supremum] => Gives clear picture of time  average cas e = > O({∑all possible time}/ total number of possibilities) Amortized / Average time complexity When we insert element into vector using push_back => two scenarios can occur: The array has room for the new element => O(1) The array is full => resized to make room for the new element.  This involves creating a new array of 2*size, copying the elements from the old array to the new one, and then adding the new element. This operation has a time complexity of O(n) in C++11 => elements are moved inst...

BITMASK -  Two varieties of approach Type -1 --> analyze for each bit (for simplicity -> take array as {1 0 0 1 0} types) Practice ke liye =>  OA wala question  +  Atcoder Type-2  (See both accepted solutions) BITSET   in   cpp NOTE - use bitset => binary representation (NOT decimal) Why do we need? Let's say make boolean array of size 1e9 => High time complexity But with bitset, it will automatically break 1e9 into multiple part of each 32 size (bcz 32-bit system) => time = 1e9/32 Can use in case of take/ not take situation bitset<1000> num --> by default, num = 0 bitset<1000> num (x) --> set num = x => x can be number or binary string num.to_string() => converts to string num.to_ullong() => converts to unsigned long long; can access ith bit as num[i] Operations set sets all bits to  1            --> num.set() reset sets all bits to  0 flip toggles ...

Must see for specific input taking Scanf Details # include <stdio.h> int main () {     int m , n ;     scanf ( "(%d)-%d" , & m , & n );     printf ( "%d %d \n " , m , n );     // scanf accept input only if it is in same format as specified     // eg.- here if u write (8) 6 => 8 is in format           =>m=8 but n=0 (by default) bcz not used '-'     scanf ( " (%d) - %d" , & m , & n );     printf ( "%d %d \n " , m , n );     // spaces doesn't matter at start or in between     scanf ( "(%d)-%d " , & m , & n );     printf ( "%d %d \n " , m , n ); // never give space at end bcz compiler ko lgta hai ek aur value hai aage and when u give 1 extra inputs then only it stops . => only first input get stored. *******************************************************************     int a ;     char c ; ...