Interactive + extras

  • 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"  --> BUT O/P = 1 2 ----> first print cout then printf
  • cin.tie(NULL);
    • unties cin from cout -> if cin and cout are tied => flushed automatically before each I/P or O/P operation on the other stream.
    • Eg.- cin.tie(NULL); cout << "Enter name:"; cin >> name;  ---> first give I/P then only the prompt to
      Enter name appears bcz cout is not flushed (stored in buffer) => output is flushed (displayed) only on demand or when the buffer is full. To avoid this, flush the cout manually every time when you want to display something before expecting input on cin.
  • Use string as char array only
  • DON'T Use
    • ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      • because it might interfere with reading input and output. You won't need the speed gains anyway for interactive problems.

Comments

Post a Comment

Popular posts from this blog

Templates (for CP)

Next smaller element in left and right side of any element -  Link     (Can easily modify) Next greater element for both sides in one pass -  Link String Hashing -  Link MUST call precalc() inside function Count inversions in any random array (GENERAL)  -  Link Count inversions in binary string -  Link Sum of XOR of all subarrays -  Link  ——₪——  Original question link Sum of XOR of all subsequence -   Link  ——₪——  Original question link Prefix sum of 2-D array -  Link Number of subarrays with sum = k →  Link Number of subarrays with sum divisible by k  →  Link Segment Trees →  Link djikstera algorithm -  Link Prime Factorization of given number n →  Link Count no. of divisors in  O(N ⅓ )  →  Link
Read more

How to Approach problem ??

Image
  Firstly, read the question carefully.  If able to understand 100% => don't read the test case else read the test cases to get the feel If not able to come up with any approach --> think of brute force -> then optimize Categorize the problem where it lies Brute Force Maths Binary Search  Greedy DP Graph Bitwise stuffs If given tree --> Visualize as shown in image (Think of BFS/DFS) If given subarray -> can think of prefix sum or dp If the code seems too lengthy => simplify => There must be a way Can use MATHS sometimes to simplify the expression or logic If dp => lookout for the transition and state definition first Whenever including edge case in anywhere always be 100% sure (even though you think its correct, it may be wrong). Lookout for edge cases !!! If sure of solution => spend time on edge cases, even it seems trivial If stuck  Check for negation of problem demand what will happen if include one by one  solve for small values l...
Read more

DP Ideas

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