CSUB - Editorial

editorial
, , , ,
8

@ankitsablok89 The problem is due to overflow . In your code countOnes in of int type , so when you mutiply countOnes*(countOnes+1) , the ans would be of int type . If countOnes = 10^5 , then overflow would occur . To solve the problem you can cast it to long long type . Here is your corrected


[1].


  [1]: http://www.codechef.com/viewsolution/4341226
1 Like
9

Why is my code results “Time Limit Exceeded”

#include<stdio.h>
main()
{
long long int result;
long int i,t,n,count;
char s;
scanf("%ld",&t);
while(t–)
{
count=0;
scanf("%ld",&n);
s = (char)malloc(sizeof(char)(n+1));
fflush(stdin);
gets(s);
for(i=0;i<n;i++)
if(s[i]==‘1’)
count++;
result = (count(count-1))/2 + count;
printf("%lld\n",result);
}
return 0;
}

10

Why is my code results “Time Limit Exceeded”
Code is here: http://www.codechef.com/viewplaintext/4298438

11

Why is my code results “SIGSEGV” Code is here: CodeChef: Practical coding for everyone

12

I am unable to understand the problem …for 10001 , 10 1000 , 100 10001 , and 1 are also the substrings …isn’t that ??

13

somebody please help, whats wrong with this

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

14

Can someone provide me with a test case for which my code is wrong. It is running perfect still i am getting WA.
https://www.codechef.com/viewsolution/14664852

15

can someone tell me what’s wrong in this code,thanks in advance.
https://www.codechef.com/viewsolution/15359934

16

I am not sure what is wrong with this code : CodeChef: Practical coding for everyone

Its executing completely fine with my IDE (DevC++) but CodeChef is showing WA. Can anyone pls help ?

17

Someone please clarify : We are essentially choosing two 1’s from a string of n 1’s, so basically, we need to do nC2, right? Then by this the solution should be (n*(n-1))/2! Where am I going wrong?

18

Hi. I’m not able to understand how and where I went wrong even though it displays the correct answer for the practice cases:

#include
using namespace std;

int main()

{
string s;

unsigned long long int t,n,count,i;
char c;
cin>>t;
for(int o=0;o<t;o++)
{
	cin>>n;
	count=0;
	for(i=0;i<n;i++)
	{
		cin>>c;
		if(c=='1')
			count++;
	}
	if(count%2)
		cout<<((count+1)/2)*count;
	else
		cout<<((count/2)*(count+1));
	
	

}

}

19

Could someone please explain how we got the formula?

20

Could someone please explain how we got the formula?

21

First we have to count the number on 1’s in the string,the to find the possible combinations of no of ones so we use the formula n*(n+1)/2

22

It could be something like this…

nC1= combinations taken 1 at a time; or individual 1’s are their own start and end point.
Then nC2 = combinations taken 2 at a time.
Adding these two makes up nC1+nC2=n×(n+1)/2

But I think it should be someting like this…
Example: 111
nC1= 1,1,1
nC2=11,11,11 we can’t include last combination in this sequence because only way to move is forward and last sequence groups last index and first index together.

So nC2 is here actually nC2 - 1 combination = 11,11
Now the last one is
nC3 = 111

So total numbers in the list are 111,11,11,1,1,1

So we have 6 numbers which satisfy this condition.
And n×(n+1)/2 is actually 6.

I am not entirely sure on this…
If you guys have any other explanation please share.

23

Shouldn’t the answer for Case #2 (i.e.10001) be 4. the sub-strings being 11,101,1001,10001,
instead of 3?

24

@kalpaj12 what you’re saying is called subsets and not substrings. A substring is a contiguous sequence of characters within a string. so, here the valid substrings would be {1}(1st element of array),{1}(last element of array),{1,0,0,0,1}. Hence, Answer will be 3

25

thanks @shinchan6599

26

Hi,

I am getting WA. Following is my code. I followed the n(n+1)/2 principle, yet I am not able to clear it.
Kindly point out the mistake.

#include <bits/stdc++.h>

using namespace std;


int main(){
	int t, n, count;
	string tmp;
	cin>>t;
	while(t--){
		cin>>n;
		count = 0;
		cin>>tmp;
		for(string::iterator i = tmp.begin(); i!=tmp.end();++i){
			if(*i=='1'){count++;}
		}
    cout<<(count*(count+1))/2<<endl;
	}
	return 0;
}
27

@insoumniac hope this helps,

first string: 1111
possible ways of getting string of ‘1’ length = 4(length of string)
possible ways of getting string of ‘2’ length = 4-1 = 3(length of string - 1)
possible ways of getting string of ‘3’ length = 4-2 = 2(length of string - 2)
possible ways of getting string of ‘4’ length = 4-3 = 1(length of string - 3)

We sum the ways: 1+2+3+4 = 10(sum of first 4 numbers)

I guess you saw the pattern and how the formula came

1 Like