Brahma and Shiva SHRINES Solution

by

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

Codechef Long Challenge Solutions

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

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment