Painters’ Duel SOLUTION KICKSTART ROUND F
A new art museum is about to open! It is a single-story building in the shape of a large equilateral triangle. That triangle is made up of many smaller identical equilateral-triangle-shaped rooms, and the side length of the museum is S times the side length of any one of the rooms. Each room has doors connecting it to all other rooms with which it shares a side (not just a vertex).
Each room is identified by two numbers: the row of the building it is in (counting from top to bottom, starting from 1), followed by its position within that row (counting from left to right, starting from 1). Here is an example of how the rooms are connected and labeled when S = 3:
Alma and Berthe are artists who are painting the rooms of the museum. Alma starts in the room (RA, PA), and Berthe starts in a different room (RB, PB). Each of them has already painted their starting room. C of the other rooms of the museum are under construction, and neither Alma nor Berthe is allowed to enter these rooms or paint them.
Alma and Berthe are having a friendly competition and playing a turn-based game, with Alma starting first. On a painter’s turn, if their current room is adjacent to at least one unpainted room that is not under construction, the painter must choose one of those rooms, move to it, and paint it. Otherwise, the painter cannot move and does nothing on their turn. Once both painters are unable to move, the game is over. The score of the game is the number of rooms painted by Alma minus the number of rooms painted by Berthe.
Both painters make optimal decisions, with Alma trying to maximize the score and Berthe trying to minimize the score. Given this, determine the best score Alma can guarantee for the game, regardless of what Berthe does.
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing six integers S, RA, PA, RB, PB, and C. Respectively, these are the side length of the museum (as a multiple of the side length of a room), the row and position of Alma’s starting room, the row and position of Berthe’s starting room, and the number of rooms that are under construction. Then, there are C more lines. The i-th of these lines (counting starting from 1) contains two integers Ri and Pi, representing the row and position of the i-th room that is under construction.
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the best score that Alma can guarantee for the game, as described above.
Time limit: 40 seconds per test set.
Memory limit: 1GB.
0 ≤ C ≤ S2 – 2.
1 ≤ RA ≤ S.
1 ≤ PA ≤ 2 × RA – 1.
1 ≤ RB ≤ S.
1 ≤ PB ≤ 2 × RB – 1.
(RA, PA) ≠ (RB, PB).
1 ≤ Ri ≤ S, for all i.
1 ≤ Pi ≤ 2 × Ri – 1, for all i.
(Ri, Pi) ≠ (RA, PA), for all i.
(Ri, Pi) ≠ (RB, PB), for all i.
Either Ri < Ri+1, or Ri = Ri+1 and Pi < Pi+1, for all i < C.
Test Set 1
T = 48.
S = 2.
Test Set 2
1 ≤ T ≤ 100.
2 ≤ S ≤ 6.
2 1 1 2 1 0
2 2 2 1 1 2
Case #1: 2
Case #2: 0
In Sample Case #1, the turns must proceed as follows:
Alma moves to room (2, 2).
Berthe cannot move.
Alma moves to room (2, 3).
Berthe still cannot move.
Alma cannot move. Since neither painter can move, the game is now over.
Alma has painted 3 rooms and Berthe has painted 1 room, so the score is 3 – 1 = 2.
In Sample Case #2, neither painter can move. They only paint their starting rooms.
The following additional cases could not appear in Test Set 1, but could appear in Test Set 2.
3 3 4 2 1 2
3 3 2 2 3 2
The correct output for these two cases would be:
Case #1: 0
Case #2: -1
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
Codechef Long Challenge Solutions
February Long Challenge 2021
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
- 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
- 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
- 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