Can’t seem to find a small case that fails it, but it is clearly wrong.
For this case your code gives 396 but my code (as well as the editorial codes) give 307.
Edit: smaller case, your code gives 28, editorial gives 26.
Edit 2: Small case found
1
10 4
20 19 15 19 11 1 12 19 1 20
Clearly we can create two tables, seat the first 6 at the first one and the rest at the second one, the two 19s at the table will add 2 to the inefficiency so total cost is 10. Your code prints 11.
. I would highly appreciate it if anyone can let me know what went wrong in my approach.
Let’s say the total inefficiency of all the guests being in one table is M.
My basic idea is to take each guest and keep adding them to a table and stop when the new inefficiency of the system (i.e) arguments of the guests in this table + arguments of the rest of the guests is less than M - k (where k is the cost of the table) and adding the next guest in the list to this table does not increase the number of arguments.
Once this condition is reached, the remaining guests are put in another table and split in a similar way.
For every position in the array where there is a conflict (i.e, the frequency count of the element is more than 1), consider two cases:
You actually split the array at that point and add a new table.
You do not split and you simply increase the inefficiency of the current table.
The crux is to select the minimum value of the two cases.
Repeat the above for every conflict position.
Surely this will be of complexity N^2.
This can be improved by storing the values returned by already computed sections of the array. This is where dynamic programming helps with reducing the compute time.
if you or anyone was facing with the subtask 1 for 20 marks. The most efficient solution, in that case, was to divide the tables as much as possible so that there is no conflict left in the arrangement.
Hope it helps
I wrote a bottom up dp but the last 2 testcases are not working . Could you tell me whats wrong with my code
cook your dish here
import sys
sys.setrecursionlimit(9500)
def solve(arr,i,j,cost,dp):
if(len(set(arr[i:j+1]))==len(arr[i:j+1])):
return cost
if((i,j) in dp):
return dp[(i,j)]
d={}
rep_count=0
for ele in arr[i:j+1]:
if(ele in d):
d[ele]+=1
if(d[ele]==2):
rep_count+=2
else:
rep_count+=1
else:
d[ele]=1
curr_cost=cost+rep_count
for z in range(i+1,j+1):
if(arr[z] in arr[i:z]):
temp=solve(arr,i,z-1,cost,dp)+solve(arr,z,j,cost,dp)
# print(curr_cost,temp)
curr_cost=min(curr_cost,temp)
dp[(i,j)]=curr_cost
return curr_cost
test=int(input())
for testcase in range(test):
li=[int(x) for x in input().split()]
n,k=li[0],li[1]
arr=[int(x) for x in input().split()]
dp={}
if(k==1):
m=1
p=0
for z in range(0,n):
if(z==0):
continue
else:
if(arr[z] in arr[p:z]):
m+=1
p=z
print(m)
else:
print(solve(arr,0,n-1,k,dp))
Can anyone help me in CHEFWED problem by providing test cases for which my code will give a wrong answer. I just got 2 failed sub tasks.
Link of the code: CodeChef: Practical coding for everyone
Thanks in advance!
I have divided my splitting approach in 3 cases. First is that we have only 1 table and all are on that and stored it in ans.
Then second one that applied in loop is, suppose all are on one table initially so as we traverse through the given array if any element repeats then taking that element and all to its right to another table and so on.
and the third split is dividing the array in two halves for each i ,ie, elements from 0 to i are one one table and elements from i+1 to n-1 are on another table .
Now solve some examples and u will realize that for k>=2 it will be good to use less tables and for k==1 it will be good to use as much table so to avoid repetition and for min val. And in the code after making hash3 i am doing the 3rd type of splitting and before it the second type. hope u got it , you just have to solve 7 to 8 good examples and u will realize it.
