Codenation Coding Round Problems

Revision en4, by yellow_13, 2022-07-07 20:00:12

The following problems are from the Codenation coding round held on 12th June. I was not able to solve these problems, and it would be very helpful if you guys could give a rough idea of the solution.

Q1. You have two integer arrays $$$X$$$ and $$$Y$$$ of size $$$n$$$. Initially, all the elements in both these arrays are $$$0$$$. You have to process $$$q$$$ queries, each query can be of three types:

  • $$$1$$$ $$$l$$$ $$$r$$$ : Flip all $$$0$$$ to $$$1$$$ and all $$$1$$$ to $$$0$$$ in the range $$$[l,...,r]$$$ in the array $$$X$$$

  • $$$2$$$ $$$p$$$ : $$$Y_i = Y_i + p\cdot X_i$$$ for all $$$i \in [1,...,n]$$$

  • $$$3$$$ $$$j$$$ : Find $$$Y_j$$$

Input: $$$n$$$, $$$q$$$, and all the queries, Output: For every query of type $$$3$$$, print $$$Y_j$$$

Constraints: $$$1 \leq n \leq 10^5$$$, $$$1 \leq q \leq 5\cdot 10^5$$$, $$$1 \leq l \leq r \leq n$$$, $$$1\leq p\leq 10^9$$$, $$$1 \leq j \leq n$$$

Q2. Given a number $$$n$$$, find the number of actual greater pairs. A pair $$$(a,b)$$$ is an actual greater pair if:

  • $$$0 \leq a < b \leq n$$$
  • sum of digits of $$$a < $$$ sum of digits of $$$b$$$

Since $$$n$$$ can be very large, you have to input it as a string. Return the number of actual greater pairs modulo $$$1e9+7$$$

Input: $$$n$$$, Output: number of actual greater pairs modulo $$$1e9 + 7$$$

Constraints: $$$1 \leq n \leq 10^{100}$$$

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English yellow_13 2022-07-07 20:00:12 0 (published)
en3 English yellow_13 2022-07-07 19:59:37 455 Tiny change: 'q n$\n\n\nQ2. ' -> 'q n$\n\n\n\n\nQ2. '
en2 English yellow_13 2022-06-16 02:01:07 606 Tiny change: 'ution.\n\n' -> 'ution.\n\nQ1. Given an integer array $X$'
en1 English yellow_13 2022-06-16 01:37:56 238 Initial revision (saved to drafts)