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

DSA Trees + Heap

Image
Trees are special form of graph If n nodes => n-1 edges (means 2 points have only 1 line joining them) They are acyclic => means from node A to node B there is only 1 way to reach Whenever see  stuffs like  connected ,  unique path  -> tree Types of traversal in trees inorder traversion - left -> root -> right preorder traversion - root -> left  -> right postorder traversion - left  -> right -> root If first time visited -> must be root (bcz parent hai)  => PRE-ORDER If second time visited -> left subtree fully analyzed bcz we are moving in anti-clockwise direction => toh left check krke hi aayenge  => IN-ORDER If third time visited -> left and right subtree fully analyzed => POST-ORDER Post-order is reverse of Pre-order from clockwise Binary search tree (BST) = Binary tree + Search property each subtree follows -- left subtree < root value < right subtree Inorder traversal in BST is...
Read more

Modular Basics + Number Theory + Permutations

Image
Binary Exponentiation - to find   a b  →  converted b into binary  Benefit - instead of multiplying b times => multiply   lo g 2 ( b ) times If a is large  →  take  (a % M) If M is itself very large (like 1e18) =>  instead of a*a  →  DO a+a+a....(a times) even if a*a = 1e18  →  will not get reduced log²(n) bcz log(n) for binary_Multiply & log(n) f or expo Same code as expo => Only change * to + everywhere If b is large in a b  →  a b c  ≠  a ( b c  %  M )  ( mod M )  →   cannot take mod in power Use Euler Theorem  →  a b c ≡ a ( b c  % ɸ(m) )  (mod M )  → ɸ is euler totient function For safety, add extra ɸ in power bcz above fails if gcd(a, m) ≠  1 a b c ≡ a (ɸ(m) + ( b c  % ɸ(m) )) ( mod M )   →  updated GCD + prime  properties a divides b + b divides a ---> a =  ±  b gcd is alwa...
Read more