10798 - Be wary of Roses

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa »

little joey,

(I'll reply at most once to this offtopic)
So now we're going to see some five postings for every problem you solve or try to solve? What are you trying to achieve by that? Exposing the thought process of a superior mind? Increasing your number of posts?
1. When I face trouble with some problem, I use the board. So the board helps me. I think it's fair to give some help here as well if I use it.

2. Sometimes help goes too far, then I add <SPOILER>. If you didn't solve the problem yet, you shouldn't have read it unless you really want to.

3. sohel asked why his algorithm isn't working and I replied why.

4. If you don't want to read it, just don't. Many posts are about different aspects. When some idea comes later, I edit the previous post instead of adding a new one. That's why there are many. I sometimes come to thread dead for the month. So I have several replies, some of which come later.

5. Some problems (particularly this one) are not about asymptotic, but about memory/CPU limit. Those spoilers are my personal "reward" to their authors. Actually there is possibility of a test which will kill my 0.035 sec solution (and I think many of those who got AC). I know that this test is not easy to find, but its authors' care to make problems clean not only in description, but also in test data. In fact, preparing hard tests consume most of the time, and sometimes eliminates judge's "bright" solution. But should the authors have set a limit for N=11, algorithm wouldn't change, but there would be less misery like "(v<<5) | 0x1F", non-general heuristics, etc...
I like to discuss problems and the way to solve them, but I'm not interested what you're doing right now. It serves no purpose. But that, of course, is only my opinion.
What part of my words was about "what I am doing right now"? I've thought of algorithm, coded it. Got WA. Understood why, and saw some other people who got WA for same reason. So I explained them why they got WA. Then I've come up with another solution (BTW, based on theirs), and with <SPOILER> remark showed that they are on the right track.

P.S: Nothing personal and no offence. Let's stay at least neutral 8)
To be the best you must become the best!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

You should remove the SPOILER and ask people to PM you if they need help. This way, if someone needs help, but maybe not _that_ much help, they don't need to see the answer.

And that they can read the rest of the thread without wondering if things are spoilers..

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa »

Larry,
Ok, just edited it. You're right, I am just getting too amazed when something "unsolvable" works better than anything submitted before :)
Last edited by Destination Goa on Tue Feb 22, 2005 1:16 pm, edited 1 time in total.
To be the best you must become the best!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

[Off-topic]

Hi. I agree with what little joey and Larry said.
Larry wrote:Actually, I think BFS is fine, since the number of states isn't that big..
So when someone has already mentioned the key of the algorithm, why make so many posts when you're basically talking about the same thing? I see that you like to share with others the joy you get while solving problems, but it's really not a good idea to give away too much details. This simply spoils the fun...

As a "newbie problemsetter", I sometimes feel quite sad seeing people complaining without even thinking about a task carefully. Let's take 10816 - Travel in Desert as an example. Quite a number of people expressed their anger and included "evil emoticons" ( :evil: ) in their posts, not realizing that they were in fact applying a completely wrong algorithm (Sorry buddies, but that's what I felt :P )...... Is it really so bad to sit down and think more?

So many members come here whenever they get WA, making posts like "Why WA? Here's my code...." And some enthusiastic members, instead of guiding them to think, simply put their accepted solutions here to "help" them. Soon come replies like "Thanks. I get AC with that..." :-? That's not a proper way of learning...... I bet other problemsetters think so too.

I recall a post previously made by Adrian (under the topic HELP WITH NCPC):
Adrian Kuegel wrote:
shanto86 wrote:So please if someone can then help me with other problems. (I am very agry to both of you. i want to learn but you two guys are insisting me to learn! . bad very bad! actually i did not like your advise. i will try to solve problems when i will get time. as i am interested in NCPC problems so i want to solve them, understand? Sorry for being so much ruied)
There is no nead to become angry, they gave you a good advice.
The other problems are more difficult, so a small hint wouldn't help you, so someone would have to tell you the algorithm/formula and you are left to implement it. Is that what you call problem solving?
For me, problem solving means finding the algorithm, the programming is the minor and sometimes even boring part.
Let us not only think about ourselves. Think about other fellow solvers too.

P.S. If you are so keen on posting your algorithms, you may like to put them on http://www.comp.nus.edu.sg/~stevenha/pr ... acmoj.html or http://www.algorithmist.com/

P.S.2. When you find problems with the judge, why not write an email to the moderators?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa »

[Off-topic]

Observer,

I personally think that all hints are either spoliers or help nothing at all, so they are useless. You never know, at which hint the person who came for help at this thread will stop. I think it would be a good idea to add 'spoiler' tag. I saw it at one of games forum (also phpBB-based). There you see a spoiler as text black-on-black until you select it. BTW, that's another reason to make several posts. It's easier to stop between messages rather than within the message.

Also, giving idea on the problem is not much bigger than giving the code on it. That's why I am showing flow of my mind on solving it (perhaps that's what little joey meant as "what I am doing right now"). Otherwise it's like giving shortest path length without the path itself. Giving a single hint is like giving only 1st step of that path. Neither helps you to solve it in general case.

If all you think that the board is just to seek for tricky IO / judge mistakes with the problems, then why is there a board? There should be trouble tickets with YES/NO/NO_COMMENTS replies from the authors (or at least those who got AC) like in the real contest for each such query. And it will be exposed to the public only when the judge is wrong, and the judge will decide whether to reply and what to reply.

P.S: I aslo think that if a person goes to the board before spending at least two hours of fruitless efforts, then his/her intention is to get some hint, perhaps the whole solution. Otherwise s/he shouldn't come here. If you got AC, why do you care about what I write. If you didn't, then why do you try to read anything? Just use your own mind... Well, that's my idea of problem-solving.

P.P.S: Since I see two gurus blaming me for what I do, I think I'd better revert to read-only mode like I did before. That'll save nerves for all of us and also a couple of bytes on board's HDD.
To be the best you must become the best!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Well, don't take it personally, it's just a good (at least by consensus) guideline. I don't think a hint is necessary a spoiler - at least in the definition that spoiler gives everything away. There are problems that I (as a beginner) used to think was, say, exhaustive search, until someone pointed out it was easier as a DP etc..

There are also specific problems that are tailored to one specific algorithm - when in reality, there are probably a few different ways for those problems.

And for those types of a problem, a little "classification" goes a long way, instead of a totally incorrect approach, or if you're on the right approach and are missing some bordercases/careless mistakes. That should be enough.

There are a few really really good problem (I would say including this one, because it was one of the first problems I solved in a way I haven't before) that if someone just told me how to do it, I might've just coded it, but I wouldn't have learned anything from it. It was great when I finally realized how to solve it. But I would be disappointed if someone gave me a formula - I can still understand the algorithm and logic, but I might not have learned as much.

nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:

Post by nealzane »

Cho wrote:I think random test cases might not be helpful for tracing bug for this problem. Anyway, it's better than nothing to do.
100000 random cases: 10798.zip (3.6MB)
Caution: The unzipped files are 19.5MB and 2.8MB
my AC code generates different answers than yours in these tests:

Code: Select all

Comparing files out and 10798.OUT
***** mine
80570:  At most 1 rose(s) trampled.
***** yours
80570:  At most 2 rose(s) trampled.
*****

***** mine
81370:  At most 2 rose(s) trampled.
***** yours
81370:  At most 3 rose(s) trampled.
*****

***** mine
96949:  At most 1 rose(s) trampled.
***** yours
96949:  At most 2 rose(s) trampled.
*****

8-)

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

Those three cases you mentioned are as follow. I also print out the path I got. Would you show me also the paths which lead to your output? Or would somebody also check these out to see if it's my mistake?

Code: Select all

R..R.R....RR....R   .................
...RR.........RRR   .................
...RR........R..R   .................
...RR............   .........**......
...R....R........   .........****....
...R.........R...   ........**.**....
R.R.......R......   ........*..*.....
R.R..........RRR.   ........*.**.....
...R.R.RP.......R   ........P.*......
RR..R.......R...R   ..........****...
..........RR.....   ............**...
.R..R..........R.   ..........***....
..........R..R.R.   ..........*......
R...R...........R   ..........*......
.....R...R..RR...   ..........**.....
....RR..R.R....RR   ...........**....
.......RRRR....R.   ............*....
At most 2 rose(s) trampled.

RR.........RR.R.R....   ..........*..........
..RR...R...R.R......R   ..........*..........
..R.......R...RR.RR..   ..........*..........
......RR..R..........   ..........*..........
R...R.......R.R......   ..........*..........
....R.R......RRR..R.R   ..........*..........
.R.RR..........RRR.RR   ..........*..........
R...RRR.R.....RR....R   ..........*..........
....RR.R....R....RR..   ..........*..........
.R....RRR.......R...R   ..........*..........
..RR..R...PR..R..R...   ..........P..........
.......R..R..........   .....................
R.RR...R.......R...RR   .....................
.....R..R.R......R..R   .....................
........R..RRR.......   .....................
.R..R..R.R.R.......R.   .....................
.R.....R.R......R.R..   .....................
......R..R...RR..RRR.   .....................
....RR...R..RR.....R.   .....................
.RR............RR...R   .....................
....R....RR..R.......   .....................
At most 3 rose(s) trampled.

R.R..R..R.RR.   ......*......
..R.R.R..R..R   .....**......
..RR..R......   .....*.......
...R.........   .....**......
..RR.........   ......*......
......R......   ......*......
....RRP...R..   ......P......
R.........R.R   .............
......R.R.R..   .............
RR..RR...RR.R   .............
.R...R.....R.   .............
.R.....R.....   .............
.............   .............
At most 2 rose(s) trampled.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

For those three cases, my program gives:

Code: Select all

.................
.................
.................
.................
.................
.................
.......***.......
......**.**......
......*.P**......
.....**..........
..****...........
***..............
.................
.................
.................
.................
.................
At most 1 rose(s) trampled.

.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
**..*****.P*.........
.****...**.*.........
.........***.........
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
At most 2 rose(s) trampled.

.............
.............
.............
.............
.............
.............
......P*.....
..****.*.....
***..*.*.....
.....***.....
.............
.............
.............
At most 1 rose(s) trampled.

In the first case the path goes EENWN... in stead of taking the shorter ENN..., but that's because it explores E befor N.
I haven't checked your input file before, because my program is way too slow to check 100000 cases within a reasonable time :)

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

Thx a lot, Joey.
There's a logical bug in my optimization code. Fixed now.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity »

.. wrote:What the problem require is, when you are at the center square(without knowing which direction you are facing), you have to decide the whole path. Say the path is, forward, right, left, forward, left, forward........

Once you decided the path, you have to use this path to walk.
You can't change the path once you start, so don't consider something like
"oh! I have stepped on a rose, I should be at position (x,y)"
You can assume that you will not know if you step on rose, though this assumption is not realistic.
Can anybody who got AC verify if this is correct? :-?

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity »

Never mind, it is correct. :D

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS »

Hi,
What is the answer of this case:

Code: Select all

5
RRRRR
RRRRR
..P..
.....
.....
Is it 1? Or 2?

--
DJWS, a newbie in programming :wink:

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

DJWS wrote:What is the answer of this case:

Code: Select all

5
RRRRR
RRRRR
..P..
.....
.....
Is it 1? Or 2?
2
I code, therefore I am.

Post Reply

Return to “Volume 107 (10700-10799)”