USACO 2020 February Contest, Silver Problem 3. Clock Tree

USACO 2020 February Contest, Silver Problem 3. Clock Tree

Farmer John's new barn has a truly strange design: it consists of NN rooms (2N25002≤N≤2500), conveniently numbered 1N1…N, and N1N−1 corridors. Each corridor connects a pair of rooms, in such a way that it is possible to walk from any room to any other room along a series of corridors.

Every room in the barn has a circular clock on the wall with the standard integers 1121…12 around its face. However, these clocks only have one hand, which always points directly at one of the integers on the clock face (it never points between two of these integers).

Bessie the cow wants to synchronize all the clocks in the barn so they all point to the integer 12. However, she is somewhat simple-minded, and as she walks around the barn, every time she enters a room, she moves the hand on its clock ahead by one position. For example, if the clock pointed at 5, it would now point at 6, and if the clock pointed at 12, it would now point at 1. If Bessie enters the same room multiple times, she advances the clock in that room every time she enters.

Please determine the number of rooms in which Bessie could start walking around the barn such that she could conceivably set all the clocks to point to 12. Note that Bessie does not initially advance the clock in her starting room, but she would advance the clock in that room any time she re-entered it. Clocks do not advance on their own; a clock only advances if Bessie enters its room. Furthermore, once Bessie enters a corridor she must exit through the other end (it is not allowed to walk partially through the corridor and loop back around to the same room).

 

SCORING:

  • Test cases 2-7 satisfy N100N≤100.
  • Test cases 8-15 satisfy no additional constraints.

 

INPUT FORMAT (file clocktree.in):

The first line of input contains NN. The next line contains NN integers, each in the range 1121…12, specifying the initial clock setting in each room. The next N1N−1 lines each describe a corridor in terms of two integers aa and bb, each in the range 1N1…N, giving the room numbers connected by the corridor.

 

OUTPUT FORMAT (file clocktree.out):

Print the number of rooms in which Bessie could start, such that it is possible for her to set all clocks to point to 12.

 

SAMPLE INPUT:

4
11 10 11 11
1 2
2 3
2 4

SAMPLE OUTPUT:

1

In this example, Bessie can set all the clocks to point to 12 if and only if she starts in room 2 (for example, by moving to room 1, 2, 3, 2, and finally 4).

 

Problem credits: Brian Dean

USACO 2020 February Contest, Silver Problem 3. Clock Tree 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Benjamin Qi)

Let $time_t[x]$ denote the reading on the clock at room $x$ after Bessie traverses $t$ corridors.

First consider the sample case. The quantity

$$q_t\equiv time_t[2]-time_t[1]-time_t[3]-time_t[4]\pmod{12}$$

only takes on the values zero or one, regardless of what moves Bessie makes.

Step 0:

 

    11
     |
     |
11--10--11

$q_0\equiv 10-11-11-11\equiv 1\pmod{12}$

Step 1:

 

    12
     |
     |
11--10--11

$q_1\equiv 10-12-11-11\equiv 0\pmod{12}$

Step 2:

 

    12
     |
     |
11--11--11

$q_2\equiv 11-12-11-11\equiv 1\pmod{12}$

Step 3:

 

    12
     |
     | 
12--11--11

$q_3\equiv 11-12-12-11\equiv 0\pmod{12}$

Step 4:

 

    12
     |
     | 
12--12--11

$q_4\equiv 12-12-12-11\equiv 1\pmod{12}$

Step 5:

 

    12
     |
     |
12--12--12

$q_5\equiv 12-12-12-12\equiv 0\pmod{12}$.

This can be generalized to trees of any form. Let $dist[x]$ denote the number of edges on the path from $x$ to the start vertex. So for the sample case, $dist[2]=0$ and $dist[1]=dist[3]=dist[4]=1$. Define

$$q_t=\sum_{x=1}^N(-1)^{dist[x]}\cdot time_t[x] \pmod{12}.$$

Then

$$q_0=q_1+1=q_2=q_3+1=q_4=\cdots .$$

If all clocks point to twelve after traversing $t$ corridors, $q_t$ must equal zero. This implies that $q_0$ must equal either zero or one.

Conversely, when $q_0$ is equal to zero or one a solution can always be constructed. This can be proven with induction.

  • The conclusion is true when $N=2$.
  • Otherwise, let $r$ be a room other than $1$ that is adjacent to only one other. Repeatedly traverse the cycle $1\to r\to 1$ until the clock at $r$ points to $12$. Then never visit $r$ again, effectively removing it from the tree and decreasing $N$ by one.

This solution runs in $O(N)$ time because if starting from room $1$ is okay, then starting from any room that is an even distance from room $1$ is also okay. Of course, the bounds were low enough that $O(N^2)$ solutions received full credit as well.

Dhruv Rohatgi's code:

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N;
vector<int> edges[100000];
int d[100000];
int A[100000];
int s0,s1,n0,n1;
 
void dfs(int i,int depth,int par)
{
	d[i] = depth;
	for(int j=0;j<edges[i].size();j++)
		if(edges[i][j]!=par)
			dfs(edges[i][j],depth+1,i);
}
 
int main()
{
	freopen("clocktree.in","r",stdin);
	freopen("clocktree.out","w",stdout);
	int a,b;
	cin >> N;
	for(int i=0;i<N;i++)
		cin >> A[i];
	for(int i=1;i<N;i++)
	{
		cin >> a >> b;
		a--,b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	dfs(0,0,-1);
	for(int i=0;i<N;i++)
	{
		if(d[i]%2) s1 += A[i], n1++;
		else s0 += A[i], n0++;
	}
	if((s0%12) == (s1%12))
		cout << N << '\n';
	else if((s0+1)%12 == (s1%12))
		cout << n1 << '\n';
	else if((s0%12) == ((s1+1)%12))
		cout << n0 << '\n';
	else
		cout << 0 << '\n';
	return 0;
}

[/hide]

翰林国际教育资讯二维码