199 - Partial differential equations

[Stefan Pochmann]

Hi,

can somebody please explain to me how to get the value of vector "b" in the sample output? I can't even get it right on paper. I get values close to those, but only close. My matrix "a" is perfect.

In (7), I get these values:
P1: 0 + 36 - 4P1 + 54 + 4P4 = 20 + 18 + 21 + 16

So I get a "-15" here, not a "-8".

Stefan

[Stefan Pochmann]

The sample output is wrong! b should be
-35 -188 -189 -315
instead of
-8 -152 -198 -333

[paulhryu]

I have been trying to solve problem 199 (Partial Differential Equations), and have noticed two things:

1. The sample output as stated in the problem description is wrong. It should be:
-36 0 0 36
0 -36 27 0
0 18 -36 0
9 0 0 -36
-35 -188 -189 -315

2. I get a Presentation Error for no good reason, even though I am clearly not putting any extraneous spaces or line breaks. Has anyone else noticed this, and if so, is there a way to get around the Presentation Error problem?

[Andrey Mokhov]

I've got the same.

The sample output is really wrong, what kept me out of this task for a long time as I thought my solution to be incorrect. But it's AC.

I got PE also.

Bad problem statement, I guess.

Bye.
Andrey.

[SnapDragon]

Technically, the final row of output should be
-15 -168 -221 -347
Since the "f" function is specified as being given in order of increasing y from top to bottom. But your output is what ends up accepted.

To avoid the PE, put a space after each line of numbers.

[Ruslan Shevelyov]

First of all, sorry for my English.

I keep getting weird compile errors for my programs which Borland C++ 5.5 compiles with no single warning. For example (199 Partial Differential Equations):
[cpp]
#include <algorithm>
#include <iostream>
#include <valarray>
#include <numeric>
using namespace std;

template <class T> class slice2d_iterator{
valarray<T>& data;
int strt, s1, s2, l1, l2, curr1, curr2;
void setcurr(int c1, int c2){curr1=c1; curr2=c2;}
public:
slice2d_iterator(valarray<T>& arr, int start, int stride1, int stride2,
int len1, int len2) : data(arr), strt(start), s1(stride1),
s2(stride2), l1(len1), l2(len2), curr1(0), curr2(0) {}
slice2d_iterator<T> end(){
slice2d_iterator<T> t(data, strt, s1, s2, l1, l2);
t.setcurr(l1, 0);
return t;
}
slice2d_iterator<T>& operator++(){
curr2++;
if(curr2==l2){curr2=0; curr1++;}
return *this;
}
slice2d_iterator<T> operator++(int){
slice2d_iterator<T> t = *this;
t.setcurr(curr1, curr2);
curr2++;
if(curr2==l2){curr2=0; curr1++;}
return t;
}
T& operator*(){return data[strt+curr1*s1+curr2*s2];}
bool operator == (slice2d_iterator<T>& k){
return curr1==k.curr1 && curr2==k.curr2 && strt==k.strt && s1==k.s1 &&
s2==k.s2 && l1==k.l1 && l2==k.l2;
}
};

template <class T> inline bool operator != (slice2d_iterator<T> k1, slice2d_iterator<T> k2){
return !(k1==k2);
}


template<class T> inline slice2d_iterator<T> submatrix(valarray<T>& data,
int top, int left, // top-left corner of the result
int rows, int cols, // dimensions of the result
int srcrowlen){ // number of elements in src matrix row
return slice2d_iterator<T>(data, top*srcrowlen+left, srcrowlen, 1, rows, cols);
}
/* ... */

[/cpp]

Here are the compiler error messages:

/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_numeric.h: In
function `int inner_product<slice2d_iterator<long int>, long int *, int>(slice2d_iterator<long
int>, slice2d_iterator<long int>, long int *, int)':
01783980_24.c:77: instantiated from here
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_numeric.h:58:
ambiguous overload for `slice2d_iterator<long int> & != slice2d_iterator<long int> &'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_relops.h:37:
candidates are: bool operator !=<slice2d_iterator<long int> >(const slice2d_iterator<long int> &,
const slice2d_iterator<long int> &)
01783980_24.c:41: bool operator !=<long int>(slice2d_iterator<long int>,
slice2d_iterator<long int>)
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h: In
function `void (* for_each<slice2d_iterator<long int>, void (*)(long int)>(slice2d_iterator<long
int>, slice2d_iterator<long int>, void (*)(long int)))(long int)':
01783980_24.c:92: instantiated from here
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:82:
ambiguous overload for `slice2d_iterator<long int> & != slice2d_iterator<long int> &'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_relops.h:37:
candidates are: bool operator !=<slice2d_iterator<long int> >(const slice2d_iterator<long int> &,
const slice2d_iterator<long int> &)
01783980_24.c:41: bool operator !=<long int>(slice2d_iterator<long int>,
slice2d_iterator<long int>)

--

If only I understood it right, B. Stroustrup wrote in "C++ Programming Language" (Special Edition, 17.1.4.2) that these operators will not be implicitly instantiated unless you said "#include <utility>, using namespace std::rel_ops" ?
I finally got it accepted after replacing "using namespace std" with
[cpp]
using std::cin;
using std::cout;
using std::valarray;
using std::inner_product;
using std::for_each;
using std::fill_n;
[/cpp]
I know that "using namespace ..." is potentially dangerous, but in this case it shouldn't have caused any problems!

Now I'm getting another weird error with 101 The Blocks Problem, and this trick don't work anymore:
[cpp]
#include <iostream>
#include <vector>
#include <string>
#include <list>

using std::vector;
using std::list;
using std::string;
using std::for_each;
using std::find;
using std::cin;
using std::cout;
using std::back_inserter;

typedef list<int> bstack;

class set_location{
vector<int>& loc;
int b;
public:
set_location(vector<int>& location, int bb) : loc(location), b(bb){}
void operator()(int a){loc[a]=loc[ b ];}
};

class put_block_back{
vector<int>& loc;
vector<bstack*>& st;
public:
put_block_back(vector<bstack*>& stacks, vector<int>& location) :
loc(location), st(stacks){}
void operator()(int a){
loc[a]=a;
st[a]->push_back(a);
}
};

inline void unstack(vector<bstack*>& stacks, vector<int>& location, int elem){
bstack* where = stacks[location[elem]];
bstack::iterator tmp = find(where->begin(), where->end(), elem);
tmp++;
for_each(tmp, where->end(), put_block_back(stacks, location));
where->erase(tmp, where->end());
}
/* ... */
[/cpp]

Here are the compiler error messages:

01787343_24.c: In function `void unstack(vector<list<int,allocator<int> >
*,allocator<list<int,allocator<int> > *> > &, vector<int,allocator<int> > &, int)':
01787343_24.c:40: implicit declaration of function `int find(...)'
01787343_24.c:40: warning: cannot pass objects of type `_List_iterator<int,int &,int *>' through
`...'
01787343_24.c:40: warning: cannot pass objects of type `_List_iterator<int,int &,int *>' through
`...'
01787343_24.c:40: conversion from `int' to non-scalar type `_List_iterator<int,int &,int *>'
requested
01787343_24.c:42: implicit declaration of function `int for_each(...)'
01787343_24.c:42: warning: cannot pass objects of type `_List_iterator<int,int &,int *>' through
`...'
01787343_24.c:42: warning: cannot pass objects of type `_List_iterator<int,int &,int *>' through
`...'
01787343_24.c: In function `int main()':
01787343_24.c:69: warning: cannot pass objects of type `_List_iterator<int,int &,int *>' through
`...'
01787343_24.c:69: warning: cannot pass objects of type `_List_iterator<int,int &,int *>' through
`...'
01787343_24.c:69: conversion from `int' to non-scalar type `_List_iterator<int,int &,int *>'
requested
01787343_24.c:70: warning: cannot pass objects of type `_List_iterator<int,int &,int *>' through
`...'
01787343_24.c:70: warning: cannot pass objects of type `_List_iterator<int,int &,int *>' through
`...'

--

Can anyone please explain, how can
[cpp]
template <class InputIterator, class T>
InputIterator find(InputIterator first,
InputIterator last,
const T& value);
[/cpp]
return int???

Thanks...

[Ruslan Shevelyov]

I apologize for posting complete solution for problem 101; hope no one will get really angry, since the problem is trivial.

After receiveing that "implicit declaration of function int find(...)" I removed
[cpp]
#include <algorithm>
using std::find;
using std::for_each;
[/cpp]
from my program and cut'n'pasted these templates from an opensource STL implementation:
[cpp]
/* @JUDGE_ID: 30345HK 101 C++ */

// Hewlett-Packard code taken from gcc 2.7.2.1: begin

/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*/

template <class InputIterator, class Function>
Function for_each(InputIterator first,
InputIterator last, Function f) {
while (first != last) f(*first++);
return f;
}

template <class InputIterator, class T>
InputIterator find(InputIterator first,
InputIterator last, const T& value) {
while (first != last && *first != value) ++first;
return first;
}

// Hewlett-Packard code: end


#include <iostream>
#include <vector>
#include <string>
#include <list>

using std::vector;
using std::list;
using std::string;
using std::cin;
using std::cout;
using std::back_inserter;

typedef list<int> bstack;

class set_location{
vector<int>& loc;
int b;
public:
set_location(vector<int>& location, int bb)
: loc(location), b(bb){}
void operator()(int a){loc[a]=loc [ b ];}
};

class put_block_back{
vector<int>& loc;
vector<bstack*>& st;
public:
put_block_back(vector<bstack*>& stacks, vector<int>& location) :
loc(location), st(stacks){}
void operator()(int a){
loc[a]=a;
st[a]->push_back(a);
}
};

inline void unstack(vector<bstack*>& st, vector<int>& loc, int elem){
bstack* where = st[loc[elem]];
bstack::iterator tmp = find(where->begin(), where->end(), elem);
tmp++;
for_each(tmp, where->end(), put_block_back(st, loc));
where->erase(tmp, where->end());
}

int main(){
int boxes; cin>>boxes;
vector<bstack*> stacks;
vector<int> location;
for(int i=0; i<boxes; i++){
bstack* tmp = new bstack;
tmp->push_back(i);
stacks.push_back(tmp);
location.push_back(i);
}

string cmd1, cmd2;
int a, b;
for( ; ; ){
cin>>cmd1;
if(cmd1=="quit") break;
cin>>a>>cmd2>>b;

if(a==b || location[a]==location [ b ]) continue;
if(cmd1=="move") unstack(stacks, location, a);
if(cmd1=="onto") unstack(stacks, location, b);
bstack* from = stacks[location[a]];
bstack* to = stacks[location [ b ]];
bstack::iterator bgn = find(from->begin(), from->end(), a);
for_each(bgn, from->end(), set_location(location, b));
copy(bgn, from->end(), back_inserter(*to));
from->erase(bgn, from->end());

/* ***** debug prn ***** **
for(int i=0; i<boxes; i++){
cout<<i<<":";
for(bstack::iterator p = stacks->begin();
p != stacks->end(); p++)
cout<<' '<<*p;
cout<<'\n';
}
for(int i=0; i<boxes; i++)cout<<location; cout<<'\n';
** ***** debug prn ***** */
}

for(int i=0; i<boxes; i++){
cout<<i<<":";
for(bstack::iterator p = stacks->begin();
p != stacks->end(); p++)
cout<<' '<<*p;
cout<<'\n';
}
}
[/cpp]
This program was compiled successfully by Online Judge and returned WA because of a misprint in int main:
[cpp]
if(cmd1=="move") unstack(stacks, location, a);
if(cmd1=="onto") unstack(stacks, location, b);
[/cpp]
Should be
[cpp]
if(cmd1=="move") unstack(stacks, location, a);
if(cmd2=="onto") unstack(stacks, location, b);
[/cpp]
After I fixed that, the program was Accepted. So I decided that OJ's STL is buggy, and decided to write a bug report. Just to be sure, I resent the old code, fixing that misprint only:
[cpp]
/* @JUDGE_ID: 30345HK 101 C++ */

#include <iostream>
#include <vector>
#include <string>
#include <list>

using std::vector;
using std::list;
using std::string;
using std::cin;
using std::cout;
using std::back_inserter;


// !!!
#include <algorithm>
using std::find;
using std::for_each;

typedef list<int> bstack;

class set_location{
vector<int>& loc;
int b;
public:
set_location(vector<int>& location, int bb)
: loc(location), b(bb){}
void operator()(int a){loc[a]=loc [ b ];}
};

class put_block_back{
vector<int>& loc;
vector<bstack*>& st;
public:
put_block_back(vector<bstack*>& stacks, vector<int>& location) :
loc(location), st(stacks){}
void operator()(int a){
loc[a]=a;
st[a]->push_back(a);
}
};

inline void unstack(vector<bstack*>& st, vector<int>& loc, int elem){
bstack* where = st[loc[elem]];
bstack::iterator tmp = find(where->begin(), where->end(), elem);
tmp++;
for_each(tmp, where->end(), put_block_back(st, loc));
where->erase(tmp, where->end());
}

int main(){
int boxes; cin>>boxes;
vector<bstack*> stacks;
vector<int> location;
for(int i=0; i<boxes; i++){
bstack* tmp = new bstack;
tmp->push_back(i);
stacks.push_back(tmp);
location.push_back(i);
}

string cmd1, cmd2;
int a, b;
for( ; ; ){
cin>>cmd1;
if(cmd1=="quit") break;
cin>>a>>cmd2>>b;

if(a==b || location[a]==location [ b ]) continue;
if(cmd1=="move") unstack(stacks, location, a);
if(cmd2=="onto") unstack(stacks, location, b);
bstack* from = stacks[location[a]];
bstack* to = stacks[location [ b ]];
bstack::iterator bgn = find(from->begin(), from->end(), a);
for_each(bgn, from->end(), set_location(location, b));
copy(bgn, from->end(), back_inserter(*to));
from->erase(bgn, from->end());

/* ***** debug prn ***** **
for(int i=0; i<boxes; i++){
cout<<i<<":";
for(bstack::iterator p = stacks->begin();
p != stacks->end(); p++)
cout<<' '<<*p;
cout<<'\n';
}
for(int i=0; i<boxes; i++)cout<<location; cout<<'\n';
** ***** debug prn ***** */
}

for(int i=0; i<boxes; i++){
cout<<i<<":";
for(bstack::iterator p = stacks->begin();
p != stacks->end(); p++)
cout<<' '<<*p;
cout<<'\n';
}
}
[/cpp]

And it was Accepted too!

Any comments?

[Krzysztof Duleba]

So could you sum up what is the problem? I tried to post a reply for this post a few times so far but failed to see the point of your writing.

General advice is to compile the code with GNU C++ compiler, version 2.95, which is used by the OJ. There are newer and way better versions available, but in some cases the code works in a significantly different way. I use g++ (actually g++-2 ) provided with Cygwin and I have to admit it works very well.

[Ruslan Shevelyov]

So could you sum up what is the problem?

OJ's C++ compiler cannot compile many programs which I think it should, since other ANSI C++ compilers which I tried can (Borland C++ 5.5, ANSI mode; Comeau C++ 4.3.3 BETA at http://www.comeaucomputing.com/tryitout/, C++ mode strict, no -tused). If anyone is interested, I can post some more code samples, say 10Kb or so.

General advice is to compile the code with GNU C++ compiler, version 2.95, which is used by the OJ.

It is too big to download with my 56k dialup.

[Krzysztof Duleba]

OK, I'd like to see that. I trust GNU C/C++ compilers much more than Microsoft's of Borland's

[Ruslan Shevelyov]

I understood what was wrong with the code I was going to post; the reason is: I #included a.h and then attempted to use some functions/classes from b.h which is included from a.h in all implementations on which I could test my program (but not in gcc), so I assumed it'll work everywhere.

Thanks for your help.

[FCS]

this is a southwestern european regional competition (1995) problem
http://www.ntnu.edu.tw/acm/ProblemSetAr ... WERC/1995/

i have taken a look at the sample solution used to generate the outputs - it wrongly uses f as increasing y from bottom to top.

hence all the mistakes.

interestingly, one team managed to get it accepted during the competition!

[junbin]

Can someone explain question 199 in simple english? I am horrible at maths and I only had a short 1/2 months crash course on Linear Systems/Vector Spaces during my A' levels (and I certainly didn't understand anything).... and now I have no idea what the question is asking me to do.

As far as I can tell, it's asking me to generate the matrix a and b, but all the equations listed just goes right over my head. :p

Any help would be greatly appreciated.

[..]

I already forget detail of the problem, so I can't tell you what it is asking.
What I remember is, the most challenging of this question is to finish reading the problem specification. Once you finish the specification, you will know that this problem is not asking something complicate.

[fjt]

It seems that the judge uses incorrect input data: b1,..,b4 do not match at the corners.
Use b1 and b2, not b3 or b4 there.
-fjt