Codeforces Round #562 (Div. 2) B. Pairs

Правка en1, от eduard.ordukhanov, 2019-05-27 07:24:21

Explanation for B. Pairs

The answer I submitted for B. Pairs was too slow to pass the tests, so I went back after the contest to view others solutions. Then I discovered that I was missing some key assumptions.

Assumption 1.

If there is an answer, one of the numbers from the solution pair will be one of the two numbers in the very first given pair

Assumption 2.

If you choose a number K from the first pair using Assumption 1, that number will either occur in every single following pair, or there will be a point where you encounter a pair where K is not one of the numbers. At this point you must choose a second number L which will be again one of the two numbers in the currently encountered pair.

Assumption 3.

The answer is "YES" If and only if for every pair you encounter, at least one of the chosen numbers K or L are one of the two numbers in the current pair

Logic

  1. Capture all the pairs given.
  2. Use Assumption 1 to choose one of the two numbers from the first pair (K). (Choose the one you haven't used if you've done this step before).
  3. Iterate through all the pairs until. a) you reach the end of the pairs which means go to step #SUCCESS. b) you encounter a pair where K is not in the pair.
  4. Choose one of the two numbers from the current pair (L) (Choose the one use didn't use last time [first number or second number]).
  5. Continue iterating through pairs while at least one of the numbers in the current pair is K or L. 6. a) you reached the end of the pairs, go to step #SUCCESS. b) you encountered a pair where neither K or L are one of the two numbers, go to step #4 if you still haven't tried another number for L. c) you've tried both numbers for L, but you still haven't tried a different number for K, go back to step #2. d) you've tried both numbers for K, and both numbers for L for every K. Nothing left to do, go to #FAILURE.

SUCCESS: print "YES" and exit program

FAILURE: print "NO" and exit program

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский eduard.ordukhanov 2019-05-27 07:38:26 18
en6 Английский eduard.ordukhanov 2019-05-27 07:34:53 171
en5 Английский eduard.ordukhanov 2019-05-27 07:30:20 16
en4 Английский eduard.ordukhanov 2019-05-27 07:29:17 4
en3 Английский eduard.ordukhanov 2019-05-27 07:28:49 0 (published)
en2 Английский eduard.ordukhanov 2019-05-27 07:28:20 431 (saved to drafts)
en1 Английский eduard.ordukhanov 2019-05-27 07:24:21 2092 Initial Revision (published)