CSUB - Editorial

Take c as long long int.

Count of 1 can be as high as 10^5 , and when you multiply it n*(n+1), its goes out of range , thus we need to take long long int for n.

Can some check what is the error in my code, i used something like two pointer to count starting 1 and added all the ending 1’s after that pointer
https://www.codechef.com/viewsolution/38096948

It is a kind of easy question but the thing is it is a bit incomplete in terms of test cases this maybe improved

e.g= for test case 10101 the answer should be [0,0] ,[2,2],[4,4] [4,0] but the solution in editor will give 6.

If number of discontinued zeros are counted and subtracted from the solution we will get 4.

but again in testcase 10001 the answer is 3 but according to what I said above it will subtract 1 from 3 and give 2, which is a wrong answer.

so there should be a specific condition to tackle this problem.

@admin @devuy11

@anon93312092 The answer for 10101 will be 6.
for 10101
we will get 3 substring [0,0] ,[2,2],[4,4]. And other 3 are [0,4] ,[0,2],[2,4].
So total 6.

#include <bits/stdc++.h>
using namespace std;
#define long long int

void solve()
{
int n;
string str;
cin>>n;
cin>>str;
int count=0;
for(int i=0;i<n;i++)
{
if(str[i]==‘1’){count++;}
}
cout<<(count*(count+1))/2<<endl;
}
int main()
{
int t;
cin>>t;
while(t–)
{solve();}
return 0;
}

Can’t understand what’s wrong here.

why this code gives the wrong answer?

int n;string str;cin>>n>>str;
map<char,vector>mp;
for(int i=0;i<(int)str.size();i++){
mp[str[i]].push_back(i);
}
int k=mp[‘1’].size();
ll ans=k*(k+1)/2;
cout<<ans<<endl;

probably because k is an int try ll k; also it should be map<char, vector<int>> not map<char, vector>

Hello!.

5
10001

in this case
why NOT 101 or 1001 or 11 like cases been takes .
they have said for substring and we can pair them in any orders.
BUT WHY we have to choose indices first and pair. Can SOmeone TELL?

Hi,

If somebody could point me why exactly this code is giving a Wrong Answer result ?

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

Thank you very much in advance!

It gives the wrong answer for this testcase.

1 Like

True. As overflow happens before result is assigned to long.

Cast first to long when calculating possible combinations solves the issue:

    long numberOfCombinations = (long) countChar1 * (countChar1 + 1) / 2;

Or just keeping counter as long in the first place:

    long countChar1 = 0;

Thank you very much.

1 Like

USE LONG INSTEAD OF INT


class Codechef
{
    static int count = 0;
	public static void main (String[] args) throws java.lang.Exception
	{
	    
		// your code goes here
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-- > 0){
		   int lengthOfStr = sc.nextInt();
		   String str = sc.next();
		   long ans = solve(str, lengthOfStr);
		   System.out.println(ans);
		}
	}
	public static long solve(String str, int lengthOfStr){
	    long n = 0;
	    for (int i=0; i<lengthOfStr; i++){
	        if(str.charAt(i) == '1'){
	            n++;
	        }
	    } 
	    return (long)((n*n+n)/2);
	}
}

Can anyone explain why my code is not working, I guess from overflow, also I know my solution is a bit too much as I saw the Author’s solution later, but what I saw that the answer was following the Pascal’s triangle, specifically the answer was the sum of the 2nd and 3rd term of the Nth row of the Pascal’s triangle where N=number of 1’s in the string, also I know I used tgamma which is a bit too much but most of my test cases passed and only the 31st test case is giving me problem. Can someone tell me why I am getting wrong answer? Here is my code

#include
#include <bits/stdc++.h>

using namespace std;

long long comb(long long n,long long r)
{
if(n==0)
return 0;
long long r1=0;
long long N=n+1;
long R=r+1;
r1=tgamma(N)/(tgamma(R)*tgamma(N-R+1));
return r1;
}

int main()
{
long long T;
cin>>T;
while(T–)
{
long long n;
cin>>n;
string S;
cin>>S;
long long cc=count(S.begin(),S.end(),‘1’);
long long ans=0;
ans+=comb(cc,1)+comb(cc,2);
cout<<ans<<"\n";

}

return 0;

}