thanks alot bro silly mistake by me
Can you give some other test cases, I’m getting 14 as the output for the test cases you have mentioned, I tried all the corner test cases and it gives my correct solution for each and every test cases, but i still don’t know what is wrong in my code.
l=[3,3,3,3,3,12,12,1,21,2,1,2,1,1,1,31,31,213,213,2,44,23,432,421,4,234,324,32,]
n=len(l)
print(n)
c=0
k=2
if k>=n//2:
print(n)
else:
con1=[]
con=1
i=0
while i<n-1:
if l[i]==l[i+1]:
con+=1
#print(l[i])
if con!=1 and l[i]!=l[i+1]: #l=[3,3,3,1,5,5]]
con1.append(con)
con=1
i+=1
if con>1:
con1.append(con)
print(con)
print(con1)
# bad=n
# for i in con1:
# bad+=(i*(i-1))//2
# print(bad)
heap=[]
for i in range(len(con1)):
heappush(heap,con1[i])
while k>0 and len(heap)>0:
x=heappop(heap)
if x%2==0:
if x!=2 and x!=0:
heappush(heap,x//2)
heappush(heap,(x//2)-1)
else:
if x!=3 and x!=1:
heappush(heap,x//2)
heappush(heap,x//2)
k-=1
#print(heap)
if len(heap)==0:
print(n)
else:
bad=n
for x in range(len(heap)):
i=(heappop(heap))
bad+=(i*(i-1))//2
#print(bad)
print(bad)
I have used max heap to store frequency of consecutive same numbers. and to extract max frequency. Con1 is list and heap is max heap. Can anyone give some testcases where this approach gives WA. any?
Hello, @ratneshpatil33 I checked your code. I wrote a similar code as your approach. Can u please explain what was the error that you missed in your code as I was not able to understand it even after the test case?
Can anyone explain the solution in laymen terms … I tried to break the problem and only came to the facts that when we change a number , what we are essentially doing is dividing the array into two parts . Thats it . Can anyone share his/her thought process in detail .
this was the twist of the question now i get it cause my answer was not being accepted cause of these case, is there any edge case for even as well or we can use standard for even, further more we devide like this only when k>1?? or some other condition
The solution is more complicated than simply breaking a partition into two parts. Consider the example cited in one of the responses above:
n = 9 k = 2
1 1 1 1 1 1 1 1 1
If you split the array into two parts you will get: 1 1 1 1 2 1 1 1 1;
If you split one of the 1 1 1 1 subarrays into two parts you will get: 1 1 1 1 2 1 3 1 1. This will yield an answer of 16.
One possible optimal solution is to split the array as follows: 1 1 2 1 1 1 3 1 1. This will yield an answer of 14.
In other words, the correct solution cannot be obtained by iteratively dividing partitions by two. You must divide the partitions in a way that the resulting subpartitions are equal in size or vary at most by one (such as in the example just discussed).
2 Likes
That is a very good explanation. I was doing the dividing the array into two parts and thought that was the right answer. Reading your answer now makes a lot of sense though. Thanks
suppose for
5 2
1 1 1 1 1
correct answer is 5
by changing 2nd and 4th answer
1 2 1 2 1 (ex.)
but my solution was changing 3rd and any other one
1 1 2 1 3(ex.)
Appreciate the response . I also figured out late that
when I take n=5 and k=1
and A=1 1 1 1 1 , it needs to be divided(changed) in between
but it same case if I take k=2
then it needs to be divided(changed) at index 1 and 4 (assuming index starts with 0)
and correct(optimal) would be 1 2 1 2 1 .
Your answer cleared much doubt .
But can you explain your last line with example .I am not able to see partition that are equal in size by taking n=5 k=2 and A= 1 1 1 1 1 (my second example ).
Thanks again .
Sorry I don’t have any other testcases
Dividing a bad subarray depends on the number of operations remaining
1 Like
You will always be able to split a partition into sub-partitions where the sub-partitions will all be either of equal length or will vary in length by one. For example N = 7 K =3 A = 1111111. An optimal solution would be 1212121. The largest “bad” subarrays are all length 1. If N = 8 K = 3 A = 11111111, an optimal partitioning is 12121211. There is no way to make all “bad” subarrays equal, so the largest “bad” subarray is length 2, while the other “bad” subarrays have length 1.
One more example, N = 15 K = 4 A = 111111111111111. An optimal partitioning is 112112112112111. Here there are 4 “bad” subarrays of length 2, 1 “bad” subarray of length 3, and 4 “bad” subarrays of length 1 (the elements numbered 2).
Your problem is almost the same as the previous one, as you only consider the case to divide an existence number by 2. There are many counterexamples as mentioned by others in this post.
hey hi!
if you got the ans then please let me know also.
i have also written the same code.
I have included a python solution which takes the prepossessed data (the list of length of all repeating elements, e.g., for 1,1,1,1,1,2,2,2,3,3 you should have a list [5,3,2] as input) .
The function comp(m,k) compute the f(m,k) in the solution.
For each repeating part, we compute how much we can save from dividing it into one more piece, and use maxheap on [Save, Length, Pieces, Current\ Cost, Next\ Cost] to perform the greedy algorithm. Each step, we pop the element that can save us most and update it.
def hfindb(a,k):
#
aa=[[comp(val,1)-comp(val,0),val,0,comp(val,0),comp(val,1)] for idx, val in enumerate(a)]
heapq.heapify(aa)
for i in range(k):
x=heapq.heappop(aa)
x[2]+=1
x[3]=x[4]
x[4]=comp(x[1],x[2]+1)
x[0]=x[4]-x[3]
heapq.heappush(aa,x)
return sum([x[3] for x in aa])
1 Like
Makes sense . Thanks
Problem - F - Codeforces has MINMAXEQ as subproblem. That’s why up-solving is important.
"For me, 1661F on paper was more or less 5 mins solve because I have already analyzed the cost function in MINMAXEQ"… aryanc403 _/_.
Upsolving is always important and everyone knows that? But when the sub problem is this much complex some people need some guidance who can’t solve this within 5 minutes, because not all are red at codeforces.
1 Like
Dividing subarray into two halves doesn’t give optimal solution
Example:
n=9 k=2
arr: 2 2 2 2 2 2 2 2 2
Not Optimal Approach:
operation 1:
2 2 2 2__2__2 2 2 2 → bad subarray count = 21
operation 2:
2__2__2 2__2__2 2 2 2 → bad subarray count = 16
Optimal Approach:
operation 1:
2 2 2 2 2__2__2 2 2 → bad subarray count = 22
operation 2:
2 2__2__2 2__2__2 2 2 → bad subarray count = 14