Search found 119 matches
- Thu Dec 04, 2008 11:54 pm
- Forum: Bugs and suggestions
- Topic: g++ compile error
- Replies: 9
- Views: 5573
g++ compile error
hi, i think the judge uses older version of g++. On judge i get error see bottom for error. #include<cstdio> #include<tr1/unordered_map> #include<algorithm> using namespace std; using namespace tr1; typedef unsigned long long ull; unordered_map<ull,ull> m; int main(){ return 0; } junk@edubuntu:~$ g+...
- Sun Nov 30, 2008 6:45 am
- Forum: Volume 112 (11200-11299)
- Topic: 11270 - Tiling Dominoes
- Replies: 6
- Views: 3715
11270 - Tiling Dominoes
Did anyone get the recurrence for the general nxm board ? or used the closed form at http://en.wikipedia.org/wiki/Domino_tiling
Say i didn't know closed form the url , how do i go about solving it ?
Say i didn't know closed form the url , how do i go about solving it ?
- Sun Nov 23, 2008 6:56 am
- Forum: Algorithms
- Topic: maximum consecutive subsum of all sub-intervals
- Replies: 5
- Views: 1996
Re: maximum consecutive subsum of all sub-intervals
i'm think i understood what you are doing. Storing the prefix sums and suffix sums and manipulating them. Can this also support dynamic operations , i mean insert before beginning or insert after last or in middle. My answer is no we have compute the whole tree because the suffix sums / prefix sums ...
- Sat Nov 22, 2008 11:20 pm
- Forum: Algorithms
- Topic: about anagram
- Replies: 3
- Views: 2070
Re: about anagram
for(i=0;i<n;i++) for(j=i+1,j<n;j++) if( IsAnagrampair(s ,s[j])) print s = s[j] int IsAnagrampair(string a,string b){ sort(a.begin(),a.end()); sort(b.begin(),b.end()); p= find the first index in a != <space> q= find the first index in b != <space> if( a.substr(p) == b.substr(q)) return 1; return 0; }
- Sat Nov 22, 2008 11:09 pm
- Forum: Algorithms
- Topic: maximum consecutive subsum of all sub-intervals
- Replies: 5
- Views: 1996
Re: maximum consecutive subsum of all sub-intervals
If that's not your own problem, care to give a link to a place where you've got it from? http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3760 . Then, what you want to find is: max_{A <= i <= j <= B-1} (a + a[i+1] + ... + a[j]). This query can be answered in O(log n) time with segm...
- Fri Nov 21, 2008 5:11 pm
- Forum: Algorithms
- Topic: difference constraints using bellman ford
- Replies: 1
- Views: 1157
difference constraints using bellman ford
The complexity is O((n+1)*(n+m)) the n in "n+m" and 1 in "n+1" attributed to the 0th vertex . O(n^2 + nm) , now if i have n=5*10^4 and m=50, how do i reduce to O(nm) ? Since v0 -> vi is all 0, we can intialize d[vi] = 0; and then continue bellman ford for the vi vertices ie why d...
- Fri Nov 21, 2008 3:24 pm
- Forum: Algorithms
- Topic: maximum consecutive subsum of all sub-intervals
- Replies: 5
- Views: 1996
maximum consecutive subsum of all sub-intervals
a1,a2,a3,..an are real numbers,n <= 10^6 s(k) = sum(ak) i=1 to k (cummulative sum until k) Define f(m,n) = s(n) - s(m) + n - m If we have 2 bounds [A,B], f(A,B) = maximize over f(i,j) with A<=i<=j<=B What is the datastructure to solve this and how do we go about solving this ? or maximum consecutiv...
- Wed Nov 19, 2008 10:48 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11405 - Can U Win?
- Replies: 15
- Views: 7028
Re: 11405 - Can U Win?
testcases 10 13 ...P.... .K...k.. ...pP..p P...pPp. ...P.... ........ ........ .p....P. 13 ...P.... .K...k.. ...PP..P P...PPP. ...P.... ........ ........ .p....P. 17 ...P.... .K...k.. ...PP..P P...PPP. ...P.... ........ ........ .P....P. 25 ...P.... .K...k.. ...PP..P P...PPP. ...P.... ........ ........
- Tue Nov 18, 2008 11:13 am
- Forum: Volume 112 (11200-11299)
- Topic: 11284 - Shopping Trip
- Replies: 32
- Views: 15007
Re: 11284 - Shopping Trip
My algo is run floyd to find shortest path. Run TSP on graph with vertices as opera store1,opera store2 ... with starting as vertex 0. What is wrong in my code ? I tried all the inputs in the forum and on uvatoolkit . All of them given correct answers from uvatoolkit. Can you please suggest what is ...
- Mon Nov 17, 2008 3:29 pm
- Forum: General
- Topic: New Judge (icpcres baylor) problems
- Replies: 3
- Views: 4126
Re: New Judge (icpcres baylor) problems
Do you guys reboot the server everyday ? I see on the weekends the server is pathetically slow. Almost unusable at certain times but on tuesday,wednesday it is bearable. Something should be done about this . This along with joomla errors, it is almost impossible to use. It is more than a year since...
- Tue Nov 11, 2008 2:26 pm
- Forum: Volume 1 (100-199)
- Topic: 125 - Numbering Paths
- Replies: 56
- Views: 6847
Re: 125-Numbering Paths PLZ help
i failed AC many times because when E=0 , i took nodes a 1 , it should nodes as 0. ie when E=0,n=0
, output is and case =10
matrix for city 10
matrix for city 11
, output is and case =10
matrix for city 10
matrix for city 11
- Mon Nov 10, 2008 2:03 pm
- Forum: Algorithms
- Topic: Strongly connected component
- Replies: 1
- Views: 2532
Strongly connected component
Where do we start the DFS from in SCC algorithm so that it we don't have to call it many times. 1) I run tarjan algorithm to find SCC first by trying all vertices of indegree 0. Find the SCC and store them in a set with one of the node as new vertex(NV). 2) Check for each new vertex (NV) edges from...
- Thu Nov 06, 2008 8:41 pm
- Forum: Volume 6 (600-699)
- Topic: 610 - Street Directions
- Replies: 15
- Views: 7465
Re: 610 - Street Directions
All the other unmarked edges in arr [j] (adjacency matrix) is orient[y][x]=1; for (i = 1; i <= N; i++) { for (j = 1; j <= N; j++) { if (arr[i][j]) { if (!orient[i][j]) orient[j][i] = 1; } } } Well, your mistake is in this step. You don't need it (there's no way to fix it), instead you need to chang...
- Wed Nov 05, 2008 6:54 pm
- Forum: Volume 6 (600-699)
- Topic: 610 - Street Directions
- Replies: 15
- Views: 7465
Re: 610 - Street Directions
My algorithm is I find all the bridges ,store the orientation bridge with (x,y) as orient[x][y]=orient[y][x]=1 For every other edge in DFS if x is parent of y , then orient[x][y]=1. All the other unmarked edges in arr [j] (adjacency matrix) is orient[y][x]=1; Any inputs for which this fails. #inclu...
- Wed Oct 22, 2008 2:51 pm
- Forum: Algorithms
- Topic: BRCKTS using binary indexed tree
- Replies: 1
- Views: 1768
BRCKTS using binary indexed tree
https://www.spoj.pl/problems/BRCKTS/ i'm trying to solve BRCKTS using binaryindexed tree. i can find the cummulative sum between 0 and len in log(n) but how do i check if all the cummulative sum are greater than or equal to 0. This requires o(n) and we have almost k queries (k approx n). How can we ...