BRACU জয়যাত্রা’50 Techfest Inter

University Individual
Programming Contest

BRAC University

https://toph.co/c/bracu-joyjatra-50-techfest-inter-university
Schedule
The contest will run for 4h0m0s.

The standings will be frozen for the last 30m0s of the contest.

Authors
The authors of this contest are Aashiq, Arghya, imAnik, masrur, tbs_sajal15, and
upobir.

Rules
This contest is formatted as per the official rules of ICPC Regional Programming
Contests.

You can use Bash 5.0, Brainf*ck, C# Mono 6.0, C++11 GCC 7.4, C++14 GCC 8.3, C++17
GCC 9.2, C11 GCC 9.2, Common Lisp SBCL 2.0, Erlang 22.3, Free Pascal 3.0, Go 1.13,
Haskell 8.6, Java 1.8, Kotlin 1.1, Node.js 10.16, Perl 5.30, PHP 7.2, PyPy 7.1 (2.7), PyPy
7.1 (3.6), Python 2.7, Python 3.7, Python 3.8, Ruby 2.6, Swift 5.3, and Whitespace in this
contest.

Be fair, be honest. Plagiarism will result in disqualification. Judges’ decisions will be

final.

Notes
There are 9 challenges in this contest.

Please make sure this booklet contains all of the pages.

If you find any discrepencies between the printed copy and the problem statements in
Toph Arena, please rely on the later.

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 2 of 14

A. Jini and the One
Limits 1s, 512 MB

Jini’s favorite number is one. She always looks for one in any number and if she finds
the digit 1 in a number then she considers that this is a lucky number. Now counting till
a large number while finding numbers that have digit 1 at least once in them can be
hard for her. Thus she needs your help.

Given N can you find her how many numbers from 1 to N contain digit 1 at least
once?

Input
The input contains a single integer N where 1 ≤ N ≤ 106

Output
Print an Integer that indicates number of integers that has digit 1 at least once.

Samples
Input Output
19 11

Input Output
23 12

In the first example, N = 19 so the answer will be 11 since

1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 are the numbers that have digit 1 in them at
least once.

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 3 of 14

B. No More Shortest Path
Limits 3s, 512 MB

You are given a weighted directed graph with n nodes and m edges. Node S is marked
as the source node and each edge has a positive weight. So the shortest path from
source to each node is defined(shortest path to nodes which are not reachable from
the source node is also considered defined and cost of shortest path to those nodes is
infinity). But you want to make it undefined.
Shortest path from one node to another is undefined if you can make the cost of
the shortest path arbitrarily small.

To do that you can do the following operation any number of times:

• Choose any edge and decrease its weight by 1.

Now you want to maximize the number of nodes such that the shortest path from
source S to those nodes are undefined and you have to do it at the minimum number
of operations.

Input
In the first line you are given an integer T (1
≤ T ≤ 10), the number of test cases. In
the first line of each test case there are three integers n(1 ≤ n ≤ 1000), m(0 ≤
m ≤ 5000) and S(1 ≤ S ≤ n). Next m lines each contains three space separated
integers u v c (1 ≤ u, v ≤ n, u  = v, 1 ≤ c ≤ 109 ) which denotes that there is a
directed edge from node u to node v with weight c.
Sum of n over all test cases does not exceed 5000 and sum of m over all test cases
does not exceed 25000.
Note: There could be multiple edges but no self loops.

Output
Print T lines.
For each test case, print two space separated integers, maximum possible number of
nodes such that the shortest path from S to them are undefined and the minimum
number of operations required to do that respectively.

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 4 of 14

Samples
Input Output
2 3 10
3 3 1 3 7
1 2 4
2 1 5
2 3 3
4 5 1
1 2 5
1 3 5
3 4 3
4 3 3
3 2 1

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 5 of 14

C. Maximize Mismatch
Limits 1s, 512 MB · Custom Checker

You are given a permutation P of number 1, ⋯ , n (I.E. each number occurs exactly
once). Now you want to introduce some chaos to this permutation. To introduce chaos,
you can perform at most k swaps between adjacent positions. The chaosness of the
final permutation is calculated as the count of the mismatches I.E. the number of
indices i such that P [i] =
 i (the indices are 1-indexed). Output the maximum number
of mismatch you can make and also output such a sequence of swaps.

Input
There will be T testcases.

Each testcase begins with a line containing space separated numbers n, k . Next line
contains n space separated numbers representing the initial permutation.

1 ≤ T ≤ 105
3 ≤ n ≤ 105
0≤k≤n
sum of n over all testcases ≤ 105

Output
For each testcase first output one number s in a line, s is the number of swaps you will
s lines, output the swaps to be performed. To swap positions x
perform. In the next
and y output the numbers x and y . Note that the swaps you perform should be
between adjacent positions.

In case of multiple answer, you can output any.

Samples
Input Output
2 1
4 2 1 2
1 4 2 3 2
10 2 1 2
1 2 3 4 5 6 7 8 9 10 9 10

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 6 of 14

D. Matrix Construction
Limits 1s, 512 MB · Custom Checker

Construct a square matrix a of size n × n satisfying the following conditions,

1. Each row of the matrix is a permutation of size n

2. Each column of the matrix is a permutation of size n
3. The matrix is symmetric, that means a[i][j] = a[j][i] for all possible i, j (1 ≤
i, j ≤ n)
4. The matrix satisfies a[i][i] = i for all i (1 ≤ i ≤ n)

If it is possible to build such a matrix, print the matrix otherwise print −1.

Input
First line of input consists of a single integer T , the number of test cases (1 ≤T ≤
5)
Each test case consists of one line. First and only line of the test case contains n, the
dimension of the matrix. (1 ≤ n ≤ 1000).

Output
Print the matrix if possible, otherwise print −1. If there are multiple possible answers,
anyone would be acceptable.

Samples
Input Output
2 -1
2 1 3 2
3 3 2 1
2 1 3

We call a sequence of integers A permutation if every integer from 1 to |A| appears

exactly once in the sequence, where ∣A∣ denotes the length of the sequence.

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 7 of 14

E. Dancing Tuples
Limits 3s, 512 MB

Given an array A of size n, find how many tuple (i, j, k) are there such that
1 ≤ i < j < k ≤ n and Aj ≤ Ai ≤ Ak .
​ ​ ​

Input
The first line contains an integer n which represents the length of the array. The
second line contains a sequence of n integers Ai . ​

1 ≤ n ≤ 106
1  ≤  Ai   ≤  n
​

Output
Print one integer — the number of valid tuples.

Samples
Input Output
5 2
4 1 3 5 2

Input Output
6 9
2 5 3 2 5 6

Input Output
5 0
1 2 3 4 5

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 8 of 14

F. String Sorting
Limits 2s, 512 MB

You'll be given a string s = s1 s2 .....sn of length n consisting of lowercase english

​ ​ ​

letters and q queries. In each query you'll be given two integers l and r , you've to
report the minimum number of operations you need to make in order to sort the
substring sl sl+1 .....sr . In one operation you can take two adjacent indices and swap
​ ​ ​

the characters.

Input
≤ ∣s∣ ≤ 106 )
First line of input contains the string s(1
Second line of input contains the number of queries q(1 ≤ q ≤ 106 ).
Next q lines contain two integer l, r(1 ≤ l ≤ r ≤ ∣s∣) .

Output
For each query output one integer, the minimum number of operations you need to
make.

Samples
Input Output
bcab 0
3 1
1 2 3
2 3
1 4

Note that, you just have to answer how many operation it takes to sort the substring,
you are not making any operation in the string. So the original string doesn't change
over queries.

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 9 of 14

G. Caching Combinatorics
Limits 2s, 512 MB

Recently Arya the little panda got a permutation of size A as a birthday present from
his parents. Being a crazy little panda, he decided to make some operations on it. In
each operation he chooses some index i(1 ≤ i ≤ n) and moves Ai to the front of the
​

permutation.

Let's say the initial permutation is ( 3, 5, 4, 1, 6, 2 ) and the sequence of

operations is ( 3, 2, 5).
So after the 1st operation, the permutation becomes,
( 4, 3, 5, 1, 6, 2 )
After the 2nd operation, the permutation becomes,
( 3, 4, 5, 1, 6, 2 )
After the 3rd operation, the permutation becomes,
( 6, 3, 4, 5, 1, 2 )

Arya has the initial permutation and the final permutation, he also remembers how
many operations were made but he forgot the sequence of operations. Now he
wonders, how many sequence of operations could there be? As the number can be
quite large, output it modulo 998244353.

Input
First line of input consists of a single integer T , the number of test cases (1 ≤T ≤
10)
Each test case consists of two lines as follows :
First line of the test case contains n, the length of permutation and m, the length of
operation sequence (1 ≤ n, m ≤ 5000).
Second line contains n space-separated distinct integers, denoting the initial
permutation A( 1 ≤ Ai ≤ n).
​

Third line contains n space-separated distinct integers, denoting the final permutation
B ( 1 ≤ Bi ≤ n).
​

Output
For each testcase print one integer, the possible number of operation sequences of
length m modulo 998244353 . Two sequences are considered different if there is
atleast one index where they differ.

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 10 of 14

Samples
Input Output
1 2
4 2
3 2 4 1
1 3 2 4

We call a sequence of integers A permutation if every integer from 1 to ∣A∣ appears

exactly once in the sequence, where ∣A∣ denotes the length of the sequence.

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 11 of 14

H. AND Maximum Spanning Tree
Limits 1s, 256 MB

You have a weighted undirected complete graph of N nodes numbered from 0 to

N − 1.
The weight of the edge between node A and B is defined as A&B (where & denotes
bitwise AND operation).
Can you find the cost of the maximum spanning tree of this graph ?

Input
First line of input consists of a single integer T , the number of test cases.
Each test case consists of one line. First and only line of each test case contains N , the
number of nodes.

1 ≤ T ≤ 10
1 ≤ N ≤ 2 ∗ 105

Output
For each test case, print one integer — cost of the maximum spanning tree of the
graph.

Samples
Input Output
4 0
3 8
6 39
11 21
8

A complete graph is a simple undirected graph in which every pair of distinct vertices is
connected by a unique edge.

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 12 of 14

I. The Answer to Everything
Limits 1s, 512 MB

What is the answer to the ultimate question of Life, the universe, and everything?

It is

You will be given n, k, m, you have to output the answer to everything..

Input
There will be T testcases.

In each testcase, the numbers n, k, m will be given in one line, separeated by spaces.

1 ≤ T ≤ 1000
1 ≤ n ≤ 109
1 ≤ k ≤ 109
1 ≤ m ≤ 109

Output
For each testcase, output the answer in a line.

Samples
Input Output
2 9
2 1 10 6
5 3 15

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 13 of 14

 This page is intentionally left (almost) blank.

BRACU জয়যাত্রা’50 Techfest Inter University Individual Programming Contest | Toph 14 of 14