Please read the new rule regarding the restriction on the use of AI tools. ×

fakehandle's blog

By fakehandle, history, 3 years ago, In English

Hi everyone In contest This Question the solution i wrote . But now i am not able to find the logical mistake please help me to find logical mistake.

thanks in advance here is code

...
#include<iostream>
using namespace std;
#define ll long long int
int main(){
	ll t ;
	cin>>t;
	while(t--){
		ll n ,k;
		cin>>n>>k;
		string s;
		cin>>s;
		ll lastX=-1,lastS=-1;
		ll count=0;
		ll last=-1,i;
		for(i=0;i<n;i++){
			if(s[i]=='*'){
				s[i]='x';
				lastX=i;
				count++;
				break;
			}
		}
		for(i=n-1;i>=0;i--){
			if(s[i]=='*'){
				last=i;
				count++;
				s[i]='x';
				break;
			}
		}
		if(last==-1 || last &mdash; lastX<=k){
			cout<<count<<endl;
		}
		else{
			for(i=0;i<n;i++){
				if(s[i]=='*'){
					if(i-lastX<k){
						lastS=i;
					}
					else if((i-lastX==k))
					{
						s[i]='x';
						lastX=i;
						lastS=-1;
						count++;
					}
					else{
						s[lastS]='x';
						lastX=lastS;
						lastS=-1;
						count++;
					}
				}
			}
			if(last-lastX>k&&lastS!=-1){
				count++;
			}
			cout<<count<<endl;
		}
	}
}
...

  • Vote: I like it
  • -17
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pro tip: Please explain what you want your code to do, and your thought process for the solution, because it's hard to read code and understand it with no knowledge of what it's supposed to do.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

There are many things in your blog which makes it hard for anyone to debug

  1. No explanation of idea
  2. Bad formating (use spoilers or links for the code)
  3. Write sentences properly. I don't remember where I read this, but writing sentences properly using propper spelling, indentation, capitalization, etc. makes it more likely for people to take it seriously (and obviously easier to understand).

Anyway, the ideia is wrong from what I understood from the code, it is always taking the first character '*' possible, but that is not necessarily optimal. For a greedy solution, you should take the last '*' character possible which is in a distance of $$$k$$$ of the last character 'x'. You can also solve it with dp, it would be a good exercise.