Hi Matt,
Thanks for the response
So I revisited the problem after reading the many posts.
Solution below is working and tested.
For each case:
1. take input
2. sort the input , but keep the original order as well
3. Loop through sorted task and check if the task is not overlapping in C
-- assign C at original position, similarly for J. Else: IMPOSSIBLE
time taken is O(nlogn) for sorting and O(n) for the output generation.
-- My solution during qual round:
1. Take input and make list of tasks
2. Loop through each task and check if it is conflicting in C (this is a
loop), else check if it is conflicting in J(this is also loop), Else :
IMPOSSIBLE
This gives output which passes Sample Case#3: 'CJJCC' but got WA for
submission.
Granted the my qual solution is not ideal, hitting O(n^2) but I don't see
anywhere in problem stating that when allocating task we need to do an
ascending order.
Did I miss something in the statement/language ? or am I missing some edge
case.
PFB the code in qual round(among many variations :) )
T = int(input())
def is_overlap(num1, num2):
firstNum, lastNum = None,None
if num1[0] < num2[0]:
firstNum = num1
lastNum = num2
else:
firstNum = num2
lastNum = num1
if lastNum[0] < firstNum[1]:
return True
return False
for case in range(1,T+1):
# read N
N = int(input())
#read schedules
schedules = []
for i in range(N):
schedules.append(list(map(int,input().split())))
C = [[1441,-1]]
J = [[1441,-1]]
output = []
count = 0
flag = 'J'
for task in schedules:
#Check for C
for C_task in C:
if is_overlap(C_task,task):
break
else:
output += ['C']
count += 1
C += [task]
continue
for J_task in J:
if is_overlap(J_task,task):
break
else:
output += ['J']
J += [task]
count += 1
if count != N:
output = []
output = list('IMPOSSIBLE')
print('Case #{}: {}'.format(case,''.join(output)))
On Tuesday, 7 April 2020 13:59:29 UTC-7, Matt Fenlon wrote:
>
> Hi Aabhas!
>
> Sorting by start time allows us to focus on end times only. When we sort
> by start time, we can assign activities to Cameron and Jamie in any fashion
> we choose provided that the start time of the next activity is on or after
> the end time of the last activity that we assigned to him or her. A simpler
> example:
>
> Hey, Cameron, can you take this 1-5?
> Sure!
> How about this 2-4?
> No, sorry.
> What about 5-7?
> Sure!
>
> When determining if we can or cannot take an activity, what we are doing
> is simply checking the 5 in 1-5 against the 2 in 2-4, and the 5 in 1-5
> against the 5 in 5-7. Easy! Now let's mix it up...
>
> Hey, Cameron, can you take this 2-4?
> Sure!
> How about this 1-5?
> ...
>
> The output will end up looking the same, but the means in which we get
> there are a bit more intensive than before. When deciding if we can take
> the 1-5, we first need to decide if a 1 start time is okay, then we need to
> determine if a 5 end time is okay. With two activities, the check is
> relatively simple. With 1000 activities, the check is a bit more
> challenging as we would need to search our schedule to find the 1-5
> interval and evaluate end times and start times, and vice versa.
>
> Now, when it comes to output, yes, we must give it in the same order in
> which it was received. When we are reading the input, we can index each
> event: the first event is 1, the second event is 2, and so on. When we
> sort, indices stay with the events regardless of where they end up after we
> have sorted the activities by start time so that, when we have assigned
> each activity to a partner, we can once again sort on indices. Now,
> activities are in the proper order, and each activity has an assignment.
>
> Does this answer your question?
>
> Best,
> Matt
>
> On Tuesday, April 7, 2020 at 12:56:02 PM UTC-4, AC wrote:
>>
>> Hi Bhavesh,
>>
>> Do we know why are we trying to sort the start time.
>> Since we do have to put the output in same order as we received it.
>> Is this a tie breaker condition for multiple solutions?
>> Can u share the edge cases for this.
>>
>> Thanks,
>>
>> On Tue, Apr 7, 2020 at 8:51 AM Bhavesh Kumar <bhavesh...@gmail.com>
>> wrote:
>>
>>> Yes, I solved in Python. Idea is simple, maintain a list of tuples. Each
>>> tuple will have three values (start_time, end_time, index). now sort the
>>> list based on first value. Checkout the code below.
>>>
>>> for t in range(int(input())):
>>> N = int(input())
>>> A = []
>>> for i in range(N):
>>> s, e = map(int, input().split())
>>> A.append((s, e, i))
>>>
>>> A.sort()
>>> ans = ['X'] * N
>>> C, J = None, None
>>> for x in A:
>>> if C is not None:
>>> if C[1] <= x[0]:
>>> C = None
>>>
>>> if J is not None:
>>> if J[1] <= x[0]:
>>> J = None
>>>
>>> if C is None:
>>> C = x
>>> ans[x[2]] = "C"
>>>
>>> elif J is None:
>>> J = x
>>> ans[x[2]] = "J"
>>>
>>> else:
>>> ans = "IMPOSSIBLE"
>>> break
>>>
>>>
>>> if 'X' in ans:
>>> ans = "IMPOSSIBLE"
>>>
>>> if isinstance(ans, list):
>>> ans = "".join(ans)
>>>
>>> print("Case #{}: {}".format(t+1, ans))
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Tuesday, 7 April 2020 06:20:28 UTC+5:30, Martin Seeler wrote:
>>>>
>>>> I'm asking to keep my sanity: Did anyone solve this problem with Python?
>>>> I can't find these tricky edge cases where my code fails, all
>>>> variations I try on my machine seem to work just fine. Still CodeJam
>>>> Environment says *WA*.
>>>>
>>>> If there is someone who solved it in python, then I know I'm missing
>>>> some cases. Otherwise I start to question the environment :D
>>>>
>>>> Thanks and have a nice day everyone
>>>>
>>> --
>>> 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 googl...@googlegroups.com.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/google-code/034a5111-e44e-4a02-8f8b-7d8791e89a7a%40googlegroups.com
>>>
>>> <https://groups.google.com/d/msgid/google-code/034a5111-e44e-4a02-8f8b-7d8791e89a7a%40googlegroups.com?utm_medium=email&utm_source=footer>
>>> .
>>>
>> --
>> Cheers!
>> Aabhas
>>
>>
--
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 google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/995e2b3d-e333-42af-93eb-c7c17a741b20%40googlegroups.com.
