Daddy's Journey to Platinum

There are n cities and mm roads between them. Unfortunately, the condition of the roads is so poor that they cannot be used. Your task is to repair some of the roads so that there will be a decent route between any two cities.

For each road, you know its reparation cost, and you should find a solution where the total cost is as small as possible.

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n.

Then, there are m lines describing the roads. Each line has three integers a, b and c: there is a road between cities a and b, and its reparation cost is c. All roads are two-way roads.

Every road is between two different cities, and there is at most one road between two cities.

Print one integer: the minimum total reparation cost. However, if there are no solutions, print "IMPOSSIBLE".

5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4

14

1 <= n <= 1e5

1<= m <= 2*1e5

1 <= a, b <= n

1 <= c <= 1e9

도시들을 정점으로하고 연결하는 도로들을 간선으로 하는 최소 신장 트리(Minimum Spanning Tree) 문제이다. 

간선의 비용을 기준으로 작은 것부터 도시들을 계속해서 연결해 나간다. 도시 하나를 연결할때 연결된 도시수를 기록한다. 모든 도시가 연결된다면 필요한 최소 간선의 수는 도시의 수보다 1 작은 값이 되야 한다. 이 값보다 크다면, 연결할 수 없는 도시가 존재하므로 "IMPOSSIBLE"을 출력하고, 연결되면 연결하면서 기록한 비용을 출력한다.

Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game.

A set P={p1,p2,…,pk} determines the allowed moves. For example, if P={1,3,4}, a player may remove 1, 3 or 4 sticks.

Your task is find out for each number of sticks 1,2,…,n if the first player has a winning or losing position.

The first input line has two integers n and k: the number of sticks and moves.

The next line has k integers p1,p2,…,pk that describe the allowed moves. All integers are distinct, and one of them is 1.

Print a string containing n characters: W means a winning position, and L means a losing position.

10 3
1 3 4

WLWWWWLWLW

1 <= n <= 1e6

1 <= k <= 100

1 <= p_i <= n

움직일 수 있는 수 집합 P에 1이 항상 들어있으므로, 첫번째 위치는 플레이어 1이 이기는 위치가 된다. 다른 p_i개의 경우도 플레이어 1이 모든 스틱을 제거할 수 있으므로, 이 위치들도 모두 이기는 위치가 된다. 

다음 단계로 P_i에 2가 없는 경우에 플레이어 1이 2의 위치에 있다면, 제거할 수 있는 스틱은 1이 되고, 다른 플레이어가 스틱이 1개가 남은 위치가 되고, 다른 플레이어도 최선의 전략을 선택하기 때문에 이경우는 지게된다.

즉, 임의의 위치 i에서 p_i를 통해 움직일 수 있는 위치가 L이라면, 현재의 위치는 W이 된다.

그냥 1~N까지 위치를 움직이며, p_i들을 빼서 비교하는 방법을 사용하면 O( N*K )가 되고, 문제에서 나오는 조건으로는 1e8정도이므로 충분하다.

There are n cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of m roads.

A component is a group of cities where there is a route between any two cities using the roads. After each day, your task is to find the number of components and the size of the largest component.

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n 

Then, there are m lines describing the new roads. Each line has two integers a and b: a new road is constructed between cities a and b.

You may assume that every road will be constructed between two different cities.

Print m lines: the required information after each day.

5 3
1 2
1 3
4 5

4 2
3 3
2 3

• 1 <= n < 1e5
• 1 <= m < 2 * 1e5
• 1 <= a, b <= n

connected component count & component size 를 찾는 문제이다. 그래프에서 connected component를 찾는 방법은 DFS, BFS, Union find 등의 방법을 사용한다. 전체 node를 검사하는 경우 시간복잡도는 O(nm)) 이지만, n=1e5, m=2x1e5 의 입력에서 시간초과가 나오므로, 중간에 계산량을 줄이는 방법이 필요해진다.

이 문제는 road(edge)가 추가되므로 추가된 부분과 연결된 부분만 계산한다. 

즉, 모든 edge를 검사할 필요 없이, 이번에 추가되는 edge와 연결된 vertex들에 대해서, 같은 component에 있는 지 확인하고, 있다면 component 숫자나 최대 크기를 변경할 필요가 없고, 서로 다른 component에 있는 경우에는 component 숫자를 줄이고, 새롭게 만들어진 component 크기와 원래 최대 크기를 비교해서 최대크기를 갱신하면 된다.

There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes 1, 2, or 3 sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

The first input line contains an integer t: the number of tests. After this, t test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x_1, x_2, ... x_n : the number of sticks in each heap.

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

3
4
5 7 2 5
2
4 1
3
4 4 4

first
first
second

• 1 <= t <= 2*1e5
• 1 <= n <= 2*1e5
• 1 <= x_i <= 1e9 
• the sum of all n is at most 2*1e5 

Nim Game의 변형문제이다.

제외할 수 있는 숫자가 1~k개로 제한되는 경우에는 (k+1) modulo 결과를 Nim Sum 이라고 한다.

• Nim Sum == 0 : 나중에 하는 사람이 승리하는 전략이 존재
• Nim Sum != 0 : 먼저하는 사람이 승리하는 전략이 존재

대항해시대4의 경우에 동전을 제거하는 게임이 나오는데 같은 원리를 적용하면, 승리할 수 있다. (컴퓨터가 이 전략을 적용하기 때문에 최초에 남는 동전에 따라 게임 결과가 정해져 있다고 생각하면 된다.) 

There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes any number of sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

The first input line contains an integer tt: the number of tests. After this, tt test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x_1, x_2, ... , x_n : the number of sticks in each heap.

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

3
4
5 7 2 5
2
4 1
3
3 5 6

first
first
second

• 1 <= t <= 2*1e5
• 1 <= n <= 2*1e5
• 1 <= x_i <= 1e9
• the sum of all n is at most 2*1e5

Game Theory 에 나오는 Nim Game 

Nim Sum 을 계산해서, 0인 경우는 나중에 하는 플레이어가 이기게 되고 0이 아닌 경우는 먼저하는 플레이어가 이기는 승리전략이 존재한다. 따라서, 문제에서 플레이어가 이 전략을 알고 거기에 따라서 행동하기 때문에 Nim Sum을 계산하면 답을 찾을 수 있다. Nim Sum은 이진수로 표현했을때 각 자리수의 1들을 2개씩 짝지을 수 있으면 0 없으면 1로 계산하는 것이다. 즉, 값들을 bit XOR 를 하면 Nim Sum을 얻을 수 있다.