Page Contents

## Brahma and Shiva SHRINES April Long Challenge 2021

Brahma created a bidimensional world, he started from a giant circle and placed 2⋅N points (numbered 1 through 2⋅N) in clockwise order on the circumference. Then Brahma created many regions by consecutively taking two of the points and slicing the circle with a line segment connecting them. The slices are such that the following conditions are satisfied:

There is exactly one slice going through each point on the perimeter

No three segments intersect at one point

There are no three segments that pairwise intersect each other

After the slices, the points resulting from the intersection of two segments were numbered arbitrarily with consecutive integers from 2⋅N+1 through V. An unordered pair (p,q) is good, if there is a slice that passes through points p and q, and none of the other V−2 points lies in the segment pq. There are in total M distinct good pairs, for each valid i, the i−th good pair is (pi,qi).

Brahma stablished a city in each of the connected regions with finite area (numbered 1 through C). For each valid i, let Ri denote the sequence of indices of the points on the perimeter of the i-th region in increasing order. Brahma numbered the cities in lexicographically increasing order (Ri<Ri+1).

Then, each of the K gods chose one of the regions to build their home, no city was chosen as the home of more than one god. Let S be the set of cities chosen by the gods.

It is possible to travel from one city to another, if their respective regions share an edge. Let D(u,v) be the length of the shortest path between cities u and v i.e the minimum number of edges we have to cross to go from u to v. The beauty of city u is given by 1∑v∈SD(u,v). The cities that have the maximum beauty among all the cities are called holy cities.

Some eons later, Shiva decided that is time to destroy the world, the only way to calm his fury is to build a shrine in each holy city. After so much time we don’t remember which cities are holy neither which cities are home of a god! However we have a plan, we’ll organize many festivities to gather information. In each festivity the following happens:

We choose two cities u, v (u≠v) and all the gods are invited to go to any of those cities.

Each god goes to the city nearest to their home. if both u and v are at the same distance, then that god does not assist to the festivity.

We count the number of gods that assisted to each of the two cities.

Your task is to save the world by organizing at most C festivities to find the holy cities.

Interaction

The first line of the input contains a single integer T denoting the number of test cases. The description of interaction for T test cases follows.

For each test case, you should start by reading a line containing four space-separated integers N, V, M, K.

The next M lines contains two space-separated integers pi and qi.

Then, you may start organizing the festivities.

To create a festivity, you should print a line containing three space-separated integers 1, u, v.

Then, you should read a line containing two space-seprated integers x, y ― the number of gods that attended city u and v respectively.

If the festivity is invalid or if you organized too many festivities, you will receive the wrong answer verdict.

When you have determined which are the holy cities, you should print a line containing Q+2 space-separated integers 2, L, H1,…, HL, where for each valid i, Hi is the index of the i-th holy city in increasing order (Hi<Hi+1).

Don’t forget to flush the output after printing each line!

Constraints

4≤C≤300

The sum of C over all test cases doesn’t exceed 104

2≤K≤C

Is guaranteed that there is only one way of reconstructing the cities from the M good pairs.

Subtasks

Subtask #1 (20 points): K=2

Subtask #2 (80 points): Original constraints

Example

Grader You

1

4 10 8 2

1 10

2 10

3 9

4 9

5 9

6 10

7 8

9 10

1 3 7

1 1

1 1 5

1 1

2 6 1 2 3 4 5 6

Explanation

The following figure describes the cities created by Brahma

The cities are numbered lexicographically. R2=(1,6,7,8,10), R6=(5,6,9,10), R7=(7,8)

There are two gods at cities 2 and 4.

In the second festivity, the god at city 2 goes to city 1, and the god at city 4 goes to 5.

All cities except 7 are holy.

*April Long Challenge 2021 Solutions*

*April Long Challenge 2021 Solutions*

- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution

*Codechef Long Challenge Solutions*

*Codechef Long Challenge Solutions*

*February Long Challenge 2021*

*February Long Challenge 2021*

#### 1. Frog Sort Solution Codechef

#### 2. Chef and Meetings Solution Codechef

#### 3. Maximise Function Solution Codechef

#### 4. Highest Divisor Solution Codechef

#### 5. Cut the Cake Challenge Solution Codechef

#### 6. Dream and the Multiverse Solution Codechef

#### 7. Cell Shell Solution Codechef

#### 8. Multiple Games Solution Codechef

#### 9. Another Tree with Number Theory Solution Codechef

#### 10. XOR Sums Solution Codechef

#### 11. Prime Game Solution CodeChef

#### 12. Team Name Solution Codechef

### January Long Challenge 2021

**Chef and Division 3 DIVTHREE SOLUTION Code Chef****Encoded String DECODEIT SOLUTION Code Chef****Point Of Impact BILLRD SOLUTION Code Chef****Fair Elections FAIRELCT SOLUTION Code Chef****Watching CPL WIPL SOLUTION Code Chef****Chef and Ants ANTSCHEF SOLUTION Code Chef****Blackjack BLKJK SOLUTION Code Chef****And-Or Game ORAND SOLUTION Code Chef****Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef****Expected Number of SCCs RCTEXSCC SOLUTION Code Chef****Curious Matrix CURMAT SOLUTION Code Chef****Cool Subsets COOLSBST SOLUTION Code Chef****Sequence Creation ARCRT SOLUTION Code Chef****Greedy Students GRDSTD SOLUTION Code Chef**

### November Challenge 2020 SOLUTION CodeChef

- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID

### October Lunchtime 2020 CodeChef SOLUTIONS

- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP

*RELATED :*

- Top Best Keylogger in Python 3 Make One
*What is Hacking?**Secrets of the Deep Dark Web**CODECHEF September Lunchtime 2020 SOLUTIONS**August Lunchtime 2020 SOLUTIONS*

*Related :*

*A. Shandom Ruffle SOLUTION**B. Pear TreaP SOLUTION**C. Sneetches and Speeches 3 SOLUTION**D. The Grim Treaper SOLUTION**Y. Sneetches and Speeches 1 SOLUTION**Z. Trick or Treap SOLUTION**A. Floor Number SOLUTION CODE FORCES**B. Symmetric Matrix SOLUTION CODE FORCES**C. Increase and Copy SOLUTION CODE FORCES**D. Non-zero Segments SOLUTION CODE FORCES**E. Rock, Paper, Scissors SOLUTION CODE FORCES**F. Number of Subsequences SOLUTION CODE FORCES*

*Related :*

*Chef and Easy Queries SOLUTIONS CHEFEZQ**Covid Run SOLUTIONS CVDRUN OCTOBER CHALLENGE**Positive AND SOLUTIONS POSAND**Replace for X SOLUTIONS REPLESX**Village Road Network SOLUTIONS VILLNET**Random Knapsack SOLUTIONS RANDKNAP**D-Dimensional MST SOLUTIONS DDIMMST**Compress all Subsegments SOLUTIONS SEGCOMPR**Adding Squares SOLUTIONS ADDSQURE**Inversions SOLUTIONS INVSMOD2 OCOTBER CHALLENGE**Rooted Minimum Spanning Tree SOLUTIONS ROOTMST*