JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
more sample problems | Reply
I think this article will be nice add problems to sample problems.

I post here some problems i hope to admins or writer refer to this post :)

Moofest(USACO) - http://acm.pku.edu.cn/JudgeOnline/problem?id=1990
Moible Phones(IOI) - http://acm.pku.edu.cn/JudgeOnline/problem?id=1195
Teams(BOI) - http://infoman.musala.com/boi/2004/team.pdf
Re: more sample problems (response to post by libe) | Reply
thanks for the problems...

so i was trying to solve the 1195 problem from PKU

#include <cstdio>
 
using namespace std;
int n;
int v[1025][1025];
void Add(int idx, int idy, int S) {
	int y2 = idy;
	while (idx <= n) {
		idy = y2;
		while ( idy <= n ) {
			v[idx][idy] += S;
			idy +=(idy & -idy);
			}
		idx += (idx & -idx);
		}
	}
int querry(int idx, int idy) {
	int y2 = idy;
	int ret = 0;
	while (idx > 0) {
		idy = y2;
		while ( idy > 0 ) {
			ret += v[idx][idy];
			idy -= (idy & -idy);
			}
		idx -= (idx & -idx);
		}
	return ret;
	}
int main() {
	while (1) {
		int command;
		scanf("%d", &command);
		if ( command == 3 ) return 0;
		if ( command == 0 ) scanf("%d", &n);
		if ( command == 1 ) { 
			int x, y, a; scanf("%d %d %d", &x, &y, &a);
			Add(x, y, a);
			}
		if ( command == 2 ) {int l, b, r, t; scanf("%d %d %d %d", &l, &b, &r, &t);
			int total = 0;
			total = querry(r, t) - querry(l-1, t) - querry(r, b-1) + querry(l-1 ,b-1);
			printf("%d\n", total);
			}
		}
	return 0;
}
 


and is TLE-ing ...

any one know what is wrong??
Re: more sample problems (response to post by vlad_D) | Reply
You used 1-base index version of Binary Indexed Tree and the rows and columns are 0-base index.
Add "++idx; ++idy;" in the begin of "Add" and "querry" function to get AC.
Re: more sample problems (response to post by ktuan) | Reply
oh, that's right!
Re: more sample problems (response to post by libe) | Reply
There's one BIT solution in the practice rooms for SRM 315 Div 2 900.
Re: more sample problems (response to post by libe) | Reply
I post here some problems i hope to admins or writer refer to this post :)

I wanted to add some problems from SPOJ, but admins didn't allow me that. It probably because I didn't find more problems from TopCoder and as I understood admins, it is not point to refer problems from other sites. But it is great you have added some links through forum. Thank you.
Re: more sample problems (response to post by libe) | Reply
SPOJ::MATSUM
This is a problem identical to one that author used in his example for 2d-BIT...
Re: more sample problems (response to post by libe) | Reply
Blocked Road (TJU) - http://acm.tju.edu.cn/toj/showp3243.html
Re: more sample problems (response to post by MarioYC) | Reply
Here are the problems in SPOJ which i did with BIT
spoj HORRIBLE
spoj ORDERS
spoj CTRICK
spoj MATSUM

This s from Codechef.com/NOV10/
Problem is BOMBING nice problem we have to use compression technique :)
Re: more sample problems (response to post by libe) | Reply
A "recent" TC semifinal problem : http://www.topcoder.com/stat?c=problem_statement&pm=11120&rd=14285
Re: more sample problems (response to post by vexorian) | Reply
A problem from our yesterdays contest http://www.codechef.com/CMUTANTS/problems/TEMPQUE/

EDIT: I have added this to spoj http://www.spoj.pl/problems/TEMPLEQ/
Re: more sample problems (response to post by ktuan) | Reply
Hello! May I ask you a private problem?
Where are you from? Which collegeļ¼Ÿ
Internal Error

Your request could not be processed. Please inform TopCoder.