## Search found 274 matches

Mon Sep 11, 2006 6:56 pm
Forum: Volume 110 (11000-11099)
Topic: 11093 - Just Finish it up
Replies: 14
Views: 8052

### Re: 11093 - just finish it up

vinay wrote:2) otherwise start with each "potential node" from 1 to n and see if sum does not become positive in between ..
What node is a "potential node"?
vinay wrote:Could u pm me ur algo or give some idea of ur O(n) algo...
Think about the linear time solution of finding maximum contigious subarray sum.
Mon Sep 11, 2006 6:46 pm
Forum: Volume 110 (11000-11099)
Topic: 11088 - End up with More Teams
Replies: 30
Views: 17570
0.002
Mon Sep 11, 2006 5:27 pm
Forum: Volume 110 (11000-11099)
Topic: 11082 - Matrix Decompressing
Replies: 28
Views: 12338
I construct the matrix row by row. For each row, I allocate the values in such a way that the column sum will be 'neutralized'.

Take the sample as example, the initail column sums are 10 10 27 11. Then I will construct row 1 such that the sums become 9 9 20 10 for the remained rows.
Mon Sep 11, 2006 5:19 pm
Forum: Volume 110 (11000-11099)
Topic: 11093 - Just Finish it up
Replies: 14
Views: 8052
O(n^2) algorithm runs in 1.6s??
Mine is O(n), but it takes 1.555.
Mon Sep 11, 2006 5:14 pm
Forum: Volume 110 (11000-11099)
Topic: 11088 - End up with More Teams
Replies: 30
Views: 17570
I solved it with backtracking.
Sat Sep 09, 2006 6:12 pm
Forum: Volume 110 (11000-11099)
Topic: 11082 - Matrix Decompressing
Replies: 28
Views: 12338

### Re: any backtrack solution..

I also solved this problem using MAX-FLOW. But I'd like to know whether any backtracking solution exists for this problem. I heard that the judge solution was implemented using backtrack... :-? Isn't (20 x 20 ) matrix too much for a backtrack approach..???? Found a greedy approach to the problem. N...
Wed Jun 21, 2006 4:29 am
Forum: Off topic (General chit-chat)
Topic: Map Problem
Replies: 12
Views: 4827
Try this code:

Code: Select all

``````#include<cstdio>
#include<cctype>
#include<string>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

map<string,int> M;

int main()
{
return 0;
}``````
By the way, you should post in the C++ forum.
Tue May 16, 2006 3:43 am
Forum: Volume 110 (11000-11099)
Topic: 11029 - Leading and Trailing
Replies: 43
Views: 17598

### Re: some doubts

I also calculated the first three digits using <math.h> and got accepted, but I still have some doubts about precision. How can we be sure that a 100-million digit number that starts off "123999999999999999999999999..." is not printed as "124..." without doing bigint calculus? I think the 4th to 15...
Thu Apr 13, 2006 6:06 pm
Forum: Other words
Topic: Who will be ACM ICPC 2006 World Final's Champion?
Replies: 23
Views: 8528
[EDIT:] The problems are available in the official site already. Got these links from other forum: Problem A: http://blog.csdn.net/wuyingying/archive/2006/04/13/661182.aspx Problem B: http://blog.csdn.net/wuyingying/archive/2006/04/13/661780.aspx Problem C: http://blog.csdn.net/wuyingying/archive/20...
Thu Apr 13, 2006 10:06 am
Forum: Other words
Topic: Who will be ACM ICPC 2006 World Final's Champion?
Replies: 23
Views: 8528
This should give you a general picture, though it was frozen half an hour before the contest finished:
http://icpc.baylor.edu/icpc/Finals/Scor ... index.html
Mon Apr 10, 2006 4:47 pm
Forum: Volume 110 (11000-11099)
Topic: 11023 - Multisets and Sequences
Replies: 10
Views: 3882
Is the following input legal? degrade {} promote () 0 rank {} derive () 0 0 find {} () derive (1,2,3) 0 0 find {} (1,2,3) end If so, is this output correct? () {} 0 {} 0 {} 0 Are there any ways to do it in O(n^2) instead of O(n*2^n)? There is probably no polynomial time solution. My solution heavily...
Sat Apr 08, 2006 5:33 am
Forum: C++
Topic: I don't know why this got CE.
Replies: 7
Views: 2736

### Re: I don't know why this got CE.

#include <iostream> bool isprime(int n){ if(n == 0 || n == 1) return true; for(int i=2; i<n/2; i++){ if(n % i == 0) return false; } return true; } BTW: are you sure you want isprime() to work this way? According to it 0 and 1 are prime, so is 4. I don't think you'll get AC with that. Btw, it's too ...
Fri Apr 07, 2006 5:57 pm
Forum: C++
Topic: I don't know why this got CE.
Replies: 7
Views: 2736
It can be compiled succesfully by MinGW. But I got a strange compilation error from g++ in unix: t.cpp:7: parse error before `+' I then modify it and the following code can be compiled without error: #include <iostream> #include <string> #include <cstdio> using namespace std; /* bool isupper(char x)...
Fri Apr 07, 2006 5:43 pm
Forum: C++
Topic: Precision Error
Replies: 1
Views: 1411
This depends on the problem.
But I think 1e-15 is too small. I ususally use 1e-9 or even 1e-6.
Thu Apr 06, 2006 2:54 pm
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 18074
Why fread? I read the input as follow: #include <stdio.h> char txt[1024][1024], ptn[1024][1024]; int main() { int M, N, Y, X, T, i; for(scanf("%d", &T); T--; ) { scanf("%d %d\n", &M, &N); for(i=0; i<M; gets(txt[i++])); scanf("%d %d\n", &Y, &X); for(i=0; i<Y; gets(ptn[i++])); // Compute and output th...