I will explain the algorithm step wise if someone wants to know the same
and at the same tome tell about the edge cases one can miss. Following is
the logic
1. Sort the input in ascending order of start times
2. Assign (0,0) as the end time of jobs allocated to Cameron and Jamie.
They are o because they are initially not allocated anything.
3. Pick the first job from the sorted input. If the *end time is lesser
than the start time* for Cameron i.e. Cameron is still busy and can't be
allocated the job. Do the same check for Jamie. Even if she is busy then
declare it as "IMPOSSIBLE" and break out of the loop.
4. Iterate through the entire sorted input until all allocations have been
made or the scheduling has been declared impossible.
5. Return the allocations in the same order as the input.
Now time to explain the implementation in Python 3. We know that somehow we
need to remember the order of the input. How would you do that?? Maybe a
dictionary will work with the job (start,end) as the key and the value as
'C' or 'J' (Initially you can mark it as 'X' or any other suitable
character). Now while sorting the input you need to sort the keys only and
carry out the above procedure. At the end you decide OK now the values of
the keys have been updated correctly so there is nothing remaining you will
simply concatenate the values using *''.join(D.values())*. As soon as you
submit it, it gives you *WA*.
Well, you say what is wrong? you did the allocation perfectly.... well the
issue is with Python dictionaries. They are non-deterministic in terms of
their order i.e. *the order of elements may change during run time or
compile time* and that is why they may not maintain the order with which
the input was given. The best way to get out of this is to use the same
dictionary and keep a list initialized with all 0s or some other relevant
character using ['X']*N and whenever you enumerate the job (or the key in
this case) just simply place your allocation ('C' or 'J') at the index of
the list which is equal to the value of the key. At the end simply use*
''.join(L)* to get the final answer. Now you run the tests in the problem
and you realise that the eg. is working fine and you will never get a *WA* or
*Sample Failed* and you submit your attempt to get the full bounty. Well...
now you end up with an *RE(Run time Error)*. You are frustrated...what
could go wrong now?
Well, there remains exactly one case that is creating the problem that is
*intervals
which are exactly the same*. For e.g. (2,7) and (2,7), the expected answer
is 'CJ' or 'JC' because by definition they still overlap doesn't matter
whether its a full, partial or exact overlap. Why was this creating an
issue? In our dictionary the jobs were our keys. Encountering exactly the
same interval will simply update the value of the key and not create a new
key in the dictionary because all keys in a dictionary are unique. So, the
value corresponding to (2,7) is the latest index it was encountered, say 3
(although it was encountered at index 1 also). Now when enumerating through
the sorted keys, the list is constantly getting updated with 'C' or 'J' at
various positions except at *1* because no key has a value equal to *1*. At
the end you again use the join() function but at index 1 you are either
having some non string datatype such as 0 or an irrelevant character say
'X' which never got updated and is available in the final answer. Depending
on its datatype its either an *RE* or *WA*.
So again the dictionaries are creating an issue. So let us abandon the use
of dictionaries altogether. Simply create tuples of the form
(start,end,index) and append the same to an empty list while taking the
input. Sort the input and carry out the above procedure. Whenever you need
to do an allocation use the empty list [0]*N as declared/initialised before
and put your allocations at appropriate indices as done before depending on
the last value of the job tuple. And now simply use the join() function to
print out the final answer. All your prayers will be heard and you will be
ridden of your *insanity* as soon as you see those two green ticks.
Here is my complete solution in Python3 for reference.
T = int(input())
for i in range(1,T+1):
N=int(input())
jobs=[]
for x in range(N):
jobs.append(tuple(map(int, input().split(' ')))+(x,))
L = [0]*N
cj=[0,0]
m = sorted(jobs)
imp = False
for j in m:
if j[0] >= cj[0]:
L[j[2]] = 'C'
cj[0] = j[1]
elif j[0] >= cj[1]:
L[j[2]] = 'J'
cj[1] = j[1]
else:
imp = True
break
if imp==True:
print("Case #{}: IMPOSSIBLE".format(i))
else:
print("Case #{}: {}".format(i,''.join(L)))
Hope this helps!!!
On Tuesday, April 7, 2020 at 6:20:28 AM 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 google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/917b837b-d24f-4e0e-861a-f8bba3b1b02e%40googlegroups.com.
