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