Computer Science Canada

not understanding this problem
Author:  saltpro15 [ Sat Apr 11, 2009 7:35 pm ]
Post subject:  not understanding this problem
hey guys,

I'm getting back into the SPOJ questions, can't seem to understand what this one is asking, it can be found here

a palace of size N when N = 3 should be like

[ ] [ ] [ ]
[ ] [ ] [ ]
[ ] [ ] [ ]

with a total of 9 rooms right? so why is the output 16?
Author:  DanielG [ Sat Apr 11, 2009 7:57 pm ]
Post subject:  RE:not understanding this problem
maybe the N=3 is referring to the number of walls on each side?? so the number of rooms is (n+1)^2???
Author:  saltpro15 [ Sat Apr 11, 2009 7:58 pm ]
Post subject:  RE:not understanding this problem
oh maybe, thanks Daniel
Author:  saltpro15 [ Sat Apr 11, 2009 8:08 pm ]
Post subject:  RE:not understanding this problem
hmm, attempted, returned a wrong answer, there must still be a problem somewhere
Author:  Tony [ Sat Apr 11, 2009 8:16 pm ]
Post subject:  RE:not understanding this problem
The wording is ambiguous. 16 refers to the number of different ways people can be arranged inside a palace (combinatorics problem), not the number of rooms (output = n^2 makes it too simple). But I don't see where the number of people would be specified.
Author:  saltpro15 [ Sat Apr 11, 2009 8:18 pm ]
Post subject:  RE:not understanding this problem
problem abandoned for now, I'll just try some other problems, these are good ECOO practice
Author:  Analysis Mode [ Sat Apr 11, 2009 8:22 pm ]
Post subject:  Re: not understanding this problem
If you're stuck on a problem, the SPOJ Forums are your best friend.
Author:  saltpro15 [ Sat Apr 11, 2009 8:27 pm ]
Post subject:  Re: not understanding this problem
c++:

#include <iostream>
#include <fstream>
using namespace std;


int main()
{
ifstream fin ("in.txt");
ofstream fout ("debug.txt");
int tc;
int walls;
fin >> tc;
for (int a = 0; a < tc; a++);
{
fin >> walls;
fout << (walls + 1) * (walls + 1) << endl;
}
return 0;
}


I knew it wouldn't be that easy haha, worth a shot lol
Author:  Analysis Mode [ Sat Apr 11, 2009 8:46 pm ]
Post subject:  Re: not understanding this problem
why are you inputting from files? All input is done from screen.
Author:  saltpro15 [ Sat Apr 11, 2009 8:49 pm ]
Post subject:  RE:not understanding this problem
files help me think, i just ran it and it produced some number like -399764534, so I think C++ is doing it's thing again Very Happy

edit : input numbers are 1 and 3
Author:  DanielG [ Sat Apr 11, 2009 8:58 pm ]
Post subject:  RE:not understanding this problem
can you put up a link to the question, it will help us figure out what it's asking. just a little.
Author:  saltpro15 [ Sat Apr 11, 2009 9:00 pm ]
Post subject:  RE:not understanding this problem
already have, it's in my first post

here it is again, just in case the link doesn't show for some

http://www.spoj.pl/problems/PALACE/
Author:  Analysis Mode [ Sat Apr 11, 2009 9:08 pm ]
Post subject:  Re: not understanding this problem
long longs and bignums are your friends, too.
Author:  bbi5291 [ Sat Apr 11, 2009 10:02 pm ]
Post subject:  Re: not understanding this problem
Put in a more mathematical style, the question asks: how many distinct NxN grids are there, such that each cell is either empty or filled, and every row and column contains an odd number of filled cells?

And no, you don't need long longs / bignums, because the answer is to be outputted modulo 98777.
Author:  CodeMonkey2000 [ Sat Apr 11, 2009 10:57 pm ]
Post subject:  Re: not understanding this problem
For N=3 these are all the possible arrangements (a block with a * means an occupied room). I'm pretty sure this is a DP problem, look at the number of ways you can place people in an (n-1) matrix. I'm pretty sure you can brute force it to find patterns.

1
[*][*][*]
[*][*][*]
[*][*][*]

2
[ ][*][ ]
[ ][*][ ]
[*][*][*]

3
[*][*][*]
[ ][*][ ]
[ ][*][ ]

4
[ ][*][ ]
[*][*][*]
[ ][*][ ]

5
[*][ ][ ]
[ ][*][ ]
[ ][ ][*]

6
[ ][ ][*]
[ ][*][ ]
[*][ ][ ]

7
[*][ ][ ]
[ ][ ][*]
[ ][*][ ]

8
[ ][ ][*]
[*][ ][ ]
[ ][*][ ]

9
[ ][*][ ]
[ ][ ][*]
[*][ ][ ]

10
[*][ ][ ]
[*][*][*]
[*][ ][ ]

11
[ ][*][ ]
[*][*][*]
[ ][*][ ]

12
[ ][ ][*]
[*][*][*]
[ ][ ][*]

13
[ ][*][ ]
[*][ ][ ]
[ ][ ][*]

14

[*][ ][ ]
[* ][ ][ ]
[*][*][*]

15
[ ][ ][*]
[ ][ ][*]
[*][*][*]

16
[*][*][*]
[*][ ][ ]
[*][ ][ ]
Author:  CodeMonkey2000 [ Sat Apr 11, 2009 11:44 pm ]
Post subject:  RE:not understanding this problem
Actually I think there is a formula, and I think it is something like:

{2^(n-1)^2 + n^[(n+1)%2] }%98777
Author:  Tony [ Sat Apr 11, 2009 11:52 pm ]
Post subject:  RE:not understanding this problem
n = 1
{2^(n-1)^2 + n^[(n+1)%2] }%98777
{2^(1-1)^2 + 1^[(1+1)%2] }%98777
{2^(0)^2 + 1^[(2)%2] }%98777
{1 + 1^[0] }%98777
= 2

But there is only 1 possibility

[*]
Author:  Analysis Mode [ Sun Apr 12, 2009 12:49 am ]
Post subject:  Re: not understanding this problem
special case?
Author:  saltpro15 [ Sun Apr 12, 2009 7:36 am ]
Post subject:  RE:not understanding this problem
I don't like this question Sad I'm trying a shortest-path one now, i'll let you guys work on this one :p
Author:  DanielG [ Sun Apr 12, 2009 9:26 am ]
Post subject:  RE:not understanding this problem
codemonkey, how did you come up with the formula? or, if you found it, where did you find it?
Author:  bbi5291 [ Sun Apr 12, 2009 11:06 am ]
Post subject:  Re: not understanding this problem
Actually, CodeMonkey2000's formula is very close... work out some small cases, and you should see a pattern emerge Smile it's not an excessively difficult problem, at least it is very easy to code.
Author:  CodeMonkey2000 [ Sun Apr 12, 2009 12:58 pm ]
Post subject:  Re: RE:not understanding this problem
DanielG @ Sun Apr 12, 2009 9:26 am wrote:
codemonkey, how did you come up with the formula? or, if you found it, where did you find it?


2^(n-1)^2 is the number of (n-1) matrices you can have.The last column and last row needs to be fixed to accommodate the restrictions, and there are n ways if n is even and 0 ways if n is odd. The last part should be n*[(n+1)%2], that was a typo; my bad Razz That formula will give you 17 solutions when N=3

I was trying to do the problem last night, and tried to find a DP solution, but instead found a possible formula. It made sense to me last night Razz.

{2^(n-1)^2 + n*[(n+1)%2] }%98777 I think this is right, though I don't feel like coding up the solution, or signing up to the judge to verify. Someone should code a brute force solution, and verify the formula.
Author:  bbi5291 [ Sun Apr 12, 2009 1:12 pm ]
Post subject:  Re: not understanding this problem
I thought it was clear from my previous post that this formula, while close, is not quite correct.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy