Hello, I would like to receive help in understanding why my solution to Problem 3 of the Google CodeJam 2020 Qualifier does not work.
Link to problem: https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9 My solution: High-level overview: - take input - figure out if the given input is impossible by sorting according to start times and then checking if more than 2 subsequent activities are 'active' at once (which is impossible) - if it is, output accordingly; if it isn't, proceed with the procedure below - arbitrarily assign the first person: in my solution I choose Cameron (C). - next, since we know that a solution exists, and the array I iterate through is sorted according to start times, if the very next activity interval (chronologically) overlaps in its duration with the current, assign it to the person who is not currently busy. This is purely because a solution exists, and it clearly cannot be the current person, so it must be the other. - moreover, if the very next activity interval (chronologically) does not overlap with the current activity, then assign it to the person who is currently busy (because he will not be busy for the next activity) - in addition, quoted directly from the problem's official analysis: "If an assignment is possible, there cannot be any set of three activities that pairwise overlap, so by the contrapositive of the the previous argument, we will be able to assign the activity to at least one of Jamie or Cameron at every step." At this moment, I believe that these arguments suffice to show that my logic is valid, although my code evidently does not always produce the correct answer. I would greatly appreciate any help on this, since I have spent hours trying to debug, un-reason, or find a counter-example to my code to no avail. I have included my code, for reference, below. Code: ``` for p in range(int(input())): s = int(input()) l = [] for i in range(s): l.append(list(map(int, list(input().split())))) unsort = l.copy() l = sorted(l, key=lambda tup: (tup[0],tup[1])) enumerated = list(enumerate(unsort)) enumerated.sort(key=lambda x: x[1][0]) impossible = False endings = sorted([(x[1], False) for x in unsort]) startings = sorted([(x[0], True) for x in unsort]) total = sorted(endings + startings, key=lambda tup: (tup[0], tup[1])) size = 0 for i in total: if i[1] == True: size += 1 else: size -= 1 if size > 2: impossible = True def overlap(a,b): if not max(a[0], b[0]) >= min(a[1], b[1]): return True else: return False ans = "C" def opp(a): if a == "C": return "J" else: return "C" if impossible == True: print("Case #" + str(p+1) + ": " + "IMPOSSIBLE") else: for i in range(0, s-1): if overlap(l[i], l[i+1]) == True: ans = ans + opp(ans[len(ans)-1]) else: ans = ans + opp(opp(ans[len(ans)-1])) #the stuff below is to order the activity assignments according to input order key_value = [(ans[i], l[i]) for i in range(s)] fans = "" for i in range(s): for j in range(s): if enumerated[j][0] == i: fans = fans + key_value[j][0] print("Case #" + str(p + 1) + ": " + fans) ``` -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/70105f87-feee-4598-8526-5c96de3b2332%40googlegroups.com.
