DALGONA - Editorial

editorial
, ,
23

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

please check my solution am not getting anything wrong in it
if(n!=1 && n!=4)
{my array contain 2 numbers
n-1 times 2
1 times ( root under(n^2-4*(n-1)))}

for n==1
{ array -1,1;
}
for n==4
{array-2,2,2,2;}

what is wrong

24

My dumb brain misread the question, and I thought the question required you to find a solution which comprised only of digits from 1 to 10 instead of 10 distinct digits. So, here is what I did.

Suppose, we are given N and the next perfect square of it be M.
N = 1^2 + 1^2 + … N times.
For every 1 we replace with a digit from 2 to 10, we get closer to M.

If we replace a 1 with 2, with increase the value by 3 ( 2^2 - 1^2 ).
If we replace a 1 with 3, with increase the value by 8 ( 3^2 - 1^2 ).
If we replace a 1 with 4, with increase the value by 15… and so on…

Here, if we notice, we can replace multiple 1s with combination of digits from 2 to 10 to get different increase in values. If we arrange the values, they would be as follows:
3 ( 1*(1 → 2) )
6 ( 2*(1 → 2) )
8 ( 1*(1 → 3) )
9 ( 3*(1 → 2) )
11 ( 1*(1 → 3) 1*(1 → 2) )
12 ( 4*(1 → 2) )
14 ( 1*(1 → 3) 2*(1 → 2) )
15 ( 5*(1 → 2) )
16 ( 2*(1 → 3) )

Now, here we see, we can increase value by 14, 15, 16 which are three consecutive numbers. And since we can also replace a 1 with 2 to increase value by 3, we can increase the value by any number greater than or equal to 14 with combination of replacing 1s with 2s and 3s.

Now, if difference between M and N is less than 14, we can then take the next perfect square of M.

My s##ty implementation to the above idea - CodeChef: Practical coding for everyone

25

even after changing it is giving wrong output

#include<bits/stdc++.h>
using namespace std;
bool isvowel(char m){
if( m==‘a’ || m==‘e’ || m==‘i’ || m==‘o’ || m==‘u’)
return true;
else
return false;
}
int main(){
int T;
cin>>T;
while(T–){
int n; int count =0; int ans = INT_MAX;
cin>>n;
string s; string p;
cin>>s>>p;

for(int j =‘a’;j<=‘z’;j++){
for(int i=0;i<n;i++){
if(s[i]==’?’)
s[i]=j;
if(p[i]==’?’)
p[i]=j;
}

for(int i=0;i<n;i++){
if(isvowel(s[i])!=isvowel(p[i]))
count = count+2;
else if(s[i]==p[i]){
continue;
}
else
count++;
}
ans=min(ans,count);
}
cout<<ans<<endl;

}
return 0;
}

26

Check my soln for this problem

1 Like
27

ok

28

why have you again create a new string and copy the old one in it ???

    ll n;
    cin >> n;
    string s, p;
    cin >> s >> p;
    ll min_ans = 1e10;
    string stemp, ptemp;
    F(j, 0, 26)
    {
        stemp = s;
        ptemp = p;
29

cout<<k<<" 1"<<endl;
cout<<a<<" "<<f<<endl;}

Why are you printing k and 1 here? I suppose it should be 1 here.
Just a tip, use proper indentation and spacing to make your code more readable.

30

yep bro.

31

You have not considered the condition of at most 10 repetitions :thinking:

32

becuase I need to check every possibilty , i.e I try out replacing the question mark with all the 26 alphabets and then I find the minimum of all . So the string gets modified every time , hence I was copying the initial string again.

@tusharkumar123

1 Like