CHEFWED - Editorial

editorial
, , , , , ,
85

But as testcase is weak you can solve uisng this trick;
I found that answer can be found from two calculation

  1. Try to arrange in one table
  2. Try to arrange in two table with all possibilities .
    and min(1,2) will be answer.
86

This is my code
…
I have one question, instead of passing one index to getAns() function, I passed two indices, a start and an end and then did two recursive calls but that gives a TLE, why is it redundant to pass two indices. Can you explain?

87

Can you explain a little bit please…

88

What i have done is that i made everyone sit in such a way that nobody gets into an argument and calculated the total cost according to this arrangement.
Then I iterated through these tables and checked if merging current table into previous one will decrease the cost or not.

89

Thanks dude :+1:

90

If somebody knows the example of 2nd sub task’s first and second cases then please post here, I really want to make my code work without DP.

91

can anyone explain whats wrong with my code.https://www.codechef.com/viewsolution/36712674

92

The editorialist code is so simple and short. Loved it!
I’m a beginner and I knew this problem is similar to Matrix chain multiplication, yet not able to write the code.

93

I would like to share my code which I can bet is the weirdest code that passed all the subtasks.
https://www.codechef.com/viewsolution/36509790
It is mix of randomness with recursion and greedy! xD

94

I am new to this platform and also beginner in CP , so actually i didn’t know much about DP yet i tried this approach and its not fully like already discussed DP approach …but yet give some review…

  1. I 1st counted the inefficiency at pos i from 0 to i and i to N-1 then add them and take min among those additions for all i from 0 to N-1.
  2. Then I calculated the inefficiency with single table.
  3. Then I calculated the inefficiency with tables no for which there will be no argument at all.
  4. At last take minimum among 1 2 3
    Give a review about my approach please
    O(N) solution
2 Likes
95

My code also failed in SubTask2 1st & 2nd TC…
My code gave wrong output in these 2 cases may be TC s are like them…
9 3
1 2 3 1 2 3 4 5 6

12 3
1 2 3 4 5 6 7 8 5 6 7 8

1 Like
96

It seems that the Tester as well as the Editor do not want to response any query or help sought from them. Does it mean that the test cases were weak and did not reflect the correct answers. If so, we should demand for re-calculation of Ranklist and Ratings should also be updated accordingly.

97

Thanks.
But my code is giving correct answers for these examples.

1 Like
98

I used matrix chain dp to solve this question-
my code:
CodeChef: Practical coding for everyone
But since matrix chain has time complexity of O(N^3) so it gives TLE for greater value of N so for N>650 ,I just used greedy and it got AC.

99

In Above solutions the ans for
1
26 2
5 1 3 4 3 4 3 4 5 1 3 3 3 3 4 4 4 4 5 1 3 4 3 4 3 4

is 24 (same as Editorialist’s Solution),
but the optimal solution would be 22 because, we split it as:
1 : {5 1 3 4 3 4 3 4} ======= further split into three tables {5 1 3 4 } {3 4} {3 4 } ===== efficiency is 2+2+2 = 6
2 : {5 1 3 3 3 3 4 4 4 4 } ======= efficiency is 2 + 8 =10
3 : {5 1 3 4 3 4 3 4} ======= further split into three tables {5 1 3 4 } {3 4} {3 4 } ===== efficiency is 2+2+2 = 6

So Total minimum efficiency would be 10 + 6 +6 = 22

2 Likes
100

meeee

https://www.codechef.com/viewsolution/36461580

101

That is what I wrote in my earlier remarks. The link is given below.

104

Whats wrong with this code
https://www.codechef.com/viewsolution/36764640

106 
for _ in range(int(input())):
    n,k=map(int,input().split())
    f=list(map(int,input().split()))
    dp=[]
    dp.append(0)
    for i in range(1, n + 1):
        dp.append(k+dp[i-1])
        dic={}
        c=0
        for j in range(i - 1, -1, -1):
            if f[j] not in dic.keys():
                dic[f[j]]=1
            else:
                dic[f[j]]+=1
            
            if(dic[f[j]]==2):
                c+=2
            elif dic[f[j]]>2:
                c+=1
            dp[i]=min(dp[i], dp[j]+k+c)
    print(dp[-1])
107

My solution based on the video explanation:

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t, n, m, k, q, x, y;
    string s;
    bool flag;

	cin >> t;
	while (t--) {
		cin >> n >> k;
		vll v(n);
		vin(v);

		vll dp(n, 0);

		dp[0] = k;
		unordered_map<ll, ll> cnt;
		FOR (i, 1, n) {
			ll args = 0;
			dp[i] = INT32_MAX;
			FORD (j, i, 0) {
				cnt[v[j]]++;
				if (cnt[v[j]] == 2)	args += 2;
				else if (cnt[v[j]] > 2)	args++;
				dp[i] = min(dp[i], dp[j - 1] + args + k);
			}
			cnt[v[0]]++;
			if (cnt[v[0]] == 2)	args += 2;
			else if (cnt[v[0]] > 2)	args++;
			dp[i] = min(dp[i], args + k);
			cnt.clear();
		}
		cout << dp.back() << '\n';
	}

    return 0;
}