CODIGO04 doubt

1

Here is the problem link -

In the ANNOUNCEMENTS section they specified the correct output for testcase

5 3
abcde

is 13 not 12 , which was true (we can verify by checking all valid splitings ) , but the accepted solutions ( first two at the top in Successful Submissions ) are giving 12 as output but still was accepted.

My solution link -
https://www.codechef.com/viewsolution/41940139

And the idea was to store the number of valid solutions for size upto i-1 to calculate the valid solutions for size i by the following logic

The possible splitings with size i = valid solutions of size i-1 ( where last element was not included in previous adjacent subarray) + no valid solutions when we add the last element to previous sub array ( = valid solutions of size i-1 - no solutions where last sub array was size k , which was dp[i-k-1] )

Is there anything wrong with my logic / implementation / question / Tester ??

My code -

#include <iostream>
#include<vector>
#include<string>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--){
	    int n,k;
	    cin >> n >> k;
	    string s;
	    cin >> s;
	    vector<int> dp(n);
	    int mod = 1000000007;
	    dp[0] = 1;
	    for(int i=1;i<n;++i){
	        long long int minus{};
	        if(i-k > 0) minus = dp[i-k-1];
	        else if(i-k == 0) minus = 1;
	        long long int ev = ((long long int)dp[i-1] * 2 - minus);
	        if(ev < 0) ev+=mod;
	        ev %= mod;
	        dp[i] = ev;
	    }
	    cout << dp[n-1] << "\n";
	}
	return 0;
}
2 Likes
2

u generated all the 13 strings?

3

also many people have done this
for this question:
https://www.codechef.com/viewsolution/41938268

4

yes , they are

  1. a b c d e

  2. a b c de

  3. a b cd e

  4. a b cde

  5. a bc d e

  6. a bc de

  7. a bcd e

  8. ab c d e

  9. ab c de

  10. ab cd e

  11. ab cde

  12. abc d e

  13. abc de

5

i didn’t understand the logic ?? can u explain that ??

6

I couldnot solve it too how they used m*n-n , i am also waiting for the editorial :smiley:

7

looks fine to me
ur dp solution is great

1 Like
8

Thanks for this post.
I was also very bamboozled looking at other solutions and even during the contest. I am not sure if problem setters made the same mistake as those solving it and reached there or if the test cases are too weak. You are not the only one with your solution because it’s somewhat the natural thing to do. Sometimes, I am genuinely amazed at how many people can get correct answer on wrong problems…
Clearly N*K - K sounded like a very small number and even asymptomatically incorrect.

I think your solution is 100% correct and all submissions of this question should be rejudged with correct test case…

Edit:
Look at this CodeChef: Practical coding for everyone
I think the only mistake in this is that it’s using N-K instead of N-k-1 (which is wrong as you can see, it leads to 12 , not 13)

1 Like
9

@cubercoder Your are right . Just changing from N-k-1 to N-k my solution was accepted.
https://www.codechef.com/viewsolution/41942522
Thanks for finding their mistake :+1: .

1 Like
10

yes, there is some mistake on test cases. test case output doesn’t match with the question statement.
We apologize for this mistake, and we are figuring things out to update right test cases.

3 Likes
11

ok.

12

thanks for this post :slight_smile:

1 Like
13

Where is editorial for this?

14

He will never post