## Search found 119 matches

- Thu Dec 04, 2008 11:54 pm
- Forum: Bugs and suggestions
- Topic: g++ compile error
- Replies:
**9** - Views:
**5280**

### 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:
**3552**

### 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:
**1774**

### 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:
**1797**

### 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:
**1774**

### 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:
**1074**

### 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 do we need the v0 ver...

- Fri Nov 21, 2008 3:24 pm
- Forum: Algorithms
- Topic: maximum consecutive subsum of all sub-intervals
- Replies:
**5** - Views:
**1774**

### 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:
**6635**

### 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:
**13935**

### 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:
**3974**

### 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:
**5769**

### 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:
**2416**

### 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:
**7112**

### 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:
**7112**

### 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:
**1654**

### 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 ...