Page Contents
Clockwise Fence USACO Solution
The fence surrounding Farmer John’s largest pasture has fallen into disrepair, and he has finally decided to replace it with a new fence.
See Also : USACO 2021 Challenges
Unfortunately, as Farmer John is laying out the new fence, a large bee ends up chasing him around the pasture, and as a result, the fence ends up following a rather irregular path. The fence can be described by a string of characters, each either “N” (north), “E” (east), “S” (south), or “W” (west). Each character describes a 1-meter run of the fence. For example, if the string is NESW, this means the fence starts by moving north for 1 meter, then east for 1 meter, then south for 1 meter, then west for 1 meter, returning to its starting point.
The fence ends at the position where it started, and this is the only point visited more than once by the path of the fence (and the starting point is only re-visited once, at the end). As a result, the fence does indeed enclose a single connected region of the grassy pasture, even though this region could have a rather strange shape.
Farmer John is curious if the path in which he laid the fence traveled clockwise (with the enclosed region on the right side of the fence as one walks along the path of the fence in the order specified by the string) or counter-clockwise (with the enclosed region on the left side of the fence).
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains an integer NN (1≤N≤201≤N≤20). Each of the next NN lines contains a string of length at least 4 and at most 100, describing a single fence path.
OUTPUT FORMAT (print output to the terminal / stdout):
For each of the NN fence paths described in the input, output a line containing either “CW” (clockwise) or “CCW” (counterclockwise).
SAMPLE INPUT:
2 NESW WSSSEENWNEESSENNNNWWWS
SAMPLE OUTPUT:
CW CCW
The two fence paths with @ denoting the starting point:
*>* ^ v @<* *<*<*<* v ^ *<@ * v ^ * *>*>* * v ^ v ^ * *<* * * v ^ v ^ *>*>* *>*
Problem credits: Brian Dean
(Analysis by Dhruv Rohatgi and Brian Dean )
Intuitively, a clockwise fence will “tend” to turn right, and a counterclockwise fence will tend to turn left. More concretely, for every two adjacent fence segments, one can compute the angle turned at that corner: either no turn (if the two segments are in the same direction), or a turn by 90∘90∘ counterclockwise (e.g. if the first segment is E and the second is N), or a turn by −90∘−90∘ counterclockwise (e.g. if the first segment is E and the second is S). Doing a few examples by hand will reveal that the sum of these angles, over all corners of the fence, is precisely 360∘360∘ if the fence is counterclockwise, and −360∘−360∘ if clockwise (other sums can be achieved if the fence is allowed to intersect itself, but we don’t have to worry about this complication in this problem).
This fact can be proven a variety of ways, such as by inducting on the area of the region enclosed by the fence. It gives a linear-time algorithm, shown below.
Dhruv’s code:
#include <iostream> #include <string> #include <cassert> using namespace std; int angle_from_direction(char a) { if(a == 'E') return 0; if(a == 'N') return 90; if(a == 'W') return 180; if(a == 'S') return 270; } int angle_change(char a,char b) { int theta1 = angle_from_direction(a); int theta2 = angle_from_direction(b); if(theta2 == (theta1 + 90)%360) return 90; else if(theta2 == theta1) return 0; else if(theta2 == (theta1 + 270)%360) return -90; else assert(false); //fence should not backtrack on itself } void test(string s) { int total_change = 0; for(int i=0;i<s.size();i++) total_change += angle_change(s[i],s[(i+1)%s.size()]); if(total_change == 360) cout << "CCW\n"; else cout << "CW\n"; } int main() { int N; string s; cin >> N; for(int i=0;i<N;i++) { cin >> s; test(s); } }
There are several other ways to effectively approach this problem. For example, one can look at the direction of any “boundary” segment. That is, look any horizontally-oriented segment that is as far north as possible — if it is directed east, the entire path must be clockwise, and if directed west, the entire path must be counterclockwise. In fact, we can draw any horizontal or vertical line through the scene and deduce from the direction of the segments along this cross section the overall orientation of the fence. For example, if we draw a horizontal line through the scene, it will be cut by some vertical segments pointing north and some pointing south (in fact, these will alternate in direction along the cross section); if the westmost segment points north, the entire path has a clockwise orientation, and vice versa.
The shoelace formula for computing areas of polygons also leads to a solution for this problem, since it delivers a “signed” area, being positive or negative depending on the orientation of the polygon in question.
USACO 2021 February Contest
- Clockwise Fence USACO 2021 February Contest
- Just Green Enough USACO 2021 February Contest
- Year of the Cow USACO 2021 February Contest
- Comfortable Cows USACO 2021 February Contest
- Count the Cows USACO 2021 February Contest
- Modern Art 3 USACO 2021 February Contest
- Stone Game USACO 2021 February Contest
- Counting Graphs USACO 2021 February Contest
- Minimizing Edges USACO 2021 February Contest
- No Time to Dry USACO 2021 February Contest
- Maze Tac Toe USACO 2021 US
- Balanced Subsets USACO 2021 US
- Routing Schemes USACO 2021 US
- United Cows of Farmer John USACO 2021 US
Weekly Contest 247
- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony
Biweekly Contest 55
- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System
Codechef Long Challenge Solutions
July Long Challenge 2021 Solutions
- Maximum Production
- Relativity
- XxOoRr
- Optimal Denomination
- K Path Query
- Chef vs Bharat
- Chef and Pairs
- Even Odd Partition
- Dakimakura Distribition
- Madoka and Ladder Decomposition
June Long Challenge 2021 Solutions
- Maximum Frequent Subarray Sum solution codechef
- Dual Distance solution codechef
- Optimal Xor Set solution codechef
- Minimum Subtree Cover solution codechef
- Minimum Dual Area solution codechef
- Bitwise Tuples solution codechef
- Shortest Route solution codechef
- Bella ciao solution codechef
- Summer Heat solution codechef
March Long Challenge 2021 Solutions
- An Interesting Sequence ISS SOLUTION
- Tree House THOUSES SOLUTION
- Valid Paths VPATH SOLUTION
- Modular Equation MODEQ SOLUTION
- Tic Tac Toe TCTCTOE SOLUTION
- Xor Equality XOREQUAL SOLUTION
- Golf LKDNGOLF SOLUTION
- Solubility SOLBLTY SOLUTION
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
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