wrong answer for funny marbles(dec 2013 challenge)

here’s my code and i am unable to figure out why am i getting a wrong answer.Please help.
here’s the link for question funny marbles

#include <stdio.h>
 
typedef struct s{
	int no,g,t;
	long long int sum;
}s;
s sp[10000002];
int main(void) {
	int i,q,x1,y1,j=0,k=0,m=0;
	long long int d,eff_gt,n,vis[50001],temp[50000];
	char act[1];
	scanf("%lld %d",&n,&q);
	sp[0].no=sp[0].sum=0;
	for(i=1;i<=n;i++)
	sp[i].g=sp[i].t=0;
	for(i=1;i<=n;i++)
	{
    scanf("%d",&sp[i].no);
	sp[i].sum=sp[i-1].sum+sp[i].no;
	}
	for(i=0;i<q;i++)
	{
	scanf("%s %d %d",act,&x1,&y1);
	if(act[0]=='S')
	{
	 eff_gt=0;
	for(k=0;k<j;k++)
	eff_gt=sp[vis[k]].g-sp[vis[k]].t+eff_gt;
	d=sp[y1+1].sum-sp[x1].sum+eff_gt;
	temp[m++]=d;
	}
	else if(act[0]=='G')
	{
	sp[x1+1].g=y1;
	vis[j++]=x1+1;
	}
	else if(act[0]=='T')
	{
	sp[x1+1].t=y1;
	vis[j++]=x1+1;
	}
	}
	for(i=0;i<m;i++)
	printf("%lld\n",temp[i]);
	return 0;
}

u have to use fenwick tree concept to solve the problem.Brute force wont work… @http://en.wikipedia.org/wiki/Fenwick_tree

@anonymousins: sorry for the ideone stuff earlier:( it runs fine on my machine :slight_smile: .your solution fails for the following case:

5 3

1000 1002 1003 1004 1005

G 3 1000

S 0 2

S 0 1

The output should be 3005,2002 but your program outputs 4005 and 3002.

this is because in ‘S’ case even the change for 3th position is added in sum for interval [0:2].

Hello @anonymousins,

After so many complaints about many people having WA veredict, I decided to double check the test cases and unfortunately, one of the files is oddly formatted, with the 1st query being used directly after the input array.

Sadly, this was not detected by any of the 4 people who tested the problem (!!!), and, when I wrote it, I obviously had confidence on it and I also believe more people looked at some of my test case generators, so, it still remains a mystery to me as how this slipped trough…

However, having over 1500 successful submissions, probably also indicates that this was not a very “serious” bug, as many, many people possibly thought alike me and the testers…

All I can do now, besides being sorry, is to leave here my solution as a reference:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
#include <numeric>
#include <stdio.h>
using namespace std;

inline int lowbit(int & i) { return (i & -i); }

void update(vector<long long int> & T, int i, long long int value)
{
    for(; i < T.size(); i+= lowbit(i))
		T[i] += value;
}

void build(vector<long long int> & T, vector<long long int> & A)
{
    for(int i=0; i < A.size(); i++) update(T, i+1, A[i]);
}

inline long long int sum(vector<long long int> & T, int i)
{
    long long int value = 0LL;
    for(; i > 0; i-= lowbit(i)) value+= T[i];
    return value;
}

inline long long int sum(vector<long long int> & T, int i, int j)
{
    return i > 1 ? sum(T,j) - sum(T,i-1) : sum(T,j);
}

int main()
{
		int N,Q;
		scanf("%d %d",&N, &Q);
		vector<long long int> v(N);
		vector<long long int> t(N+1);
		for(int i = 0; i < N; i++)
			scanf("%lld",&v[i]);
		build(t,v);
		for(int i = 0; i < Q; i++)
		{
			string s;
			cin >> s;
			if(s=="G")
			{
				int ind;
				long long int val;
				scanf("%d %lld",&ind, &val);
				update(t,ind+1,val);
			}
			if(s=="T")
			{
				int ind;
				long long int val;
				scanf("%d %lld",&ind, &val);
				update(t,ind+1,-1*val);
			}
			if(s=="S")
			{
				int low, high;
				scanf("%d %d",&low, &high);
				long long int x = sum(t,low+1,high+1);
				printf("%lld\n",x);
			}
		}
	return 0;
}

As I’ve said earlier, it’s terrible that such big mistake happened, and, it’s of no use to try to find excuses for this…

I’m sorry to everyone who was affected in a more serious way (Python users!!! Sorry guys!!)…

I guess it’s fate telling me to take a break of setting problems for a while… :slight_smile:

Best,

Bruno

but whats the cause of a wrong answer?

but how can it enter only once?
i have for(i=0;i<q;i++)
also it is giving correct solution on turbo c
please help

@anonymousins: sorry, it runs fine on my machine :frowning: i edited my answer.

Still getting WA
my solution:http://www.codechef.com/viewsolution/3143507

first of all we are very thankful to you that you are on codechef :slight_smile:
is it like this
suppose queries are
S 0 2
print answer
G 0 3
S 0 2
print answer

tried to submit it but got wa and here’e the link http://www.codechef.com/viewsolution/3143602
i think i dint get what you are telling.please help

The idea is that, for every S query you should output the answer, taking account of any further updates in-between S queries, so, you should maintain a sort of persistent data structure which “detects” all updates and answers queries fast. Such structure is a Fenwick Tree :slight_smile: Look at my implementation and editorial, and hopefully you will understand it.

This can’t really be explained much further, but, when you finally see this data structure power and when a “click” occurs you will feel awesome :smiley: Good luck and anything you need, let me know :wink: or alternatively, e-mail me at olivbruno8 at gmail dot com and I will try and write a longer/detailed explanation when its possible for me

please view my solution and it would be really helpful if you figure out that why is it giving WA
http://www.codechef.com/viewsolution/3143507

Well, one cause might be the input being badly formatted as I’ve refered earlier and also, check if your array of structures is being properly initialized…

@anonymousins: this solution actually times out.http://www.codechef.com/viewsolution/3143662 .

the reason for WA and high memory consumption is becoz of declaring sp 10000002 (there is an additional 0 added) . WA: http://www.codechef.com/viewsolution/3143630 (though dont know why an additional 0 results in WA…)

try implementing it using binay indexed trees its fun :slight_smile: (tutorial: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees )

also i would like to emphasise that its giving correct answer in turbo c but ideone for the given test case shows o/p as just 3005 and doesn’t show 3008.i would surely like it to implement by the above approach(binary indexed trees)but still working on my WA.:frowning:

@anonymousins: WA is because of size of sp and the solution timed out(see previous comment for link)

but by shrinking the size also it is giving wrong o/p at ideone but right o/p on turbo c

in ideone the program runs differently, but by reducing size codechef results (TLE: www.codechef.com/viewsolution/3143662 ) ,… previously (WA on codechef: http://www.codechef.com/viewsolution/3143630 )


Did using BIT… Cannot find the mistake.