OJ Board

Ah. Thanks for the responses. This is exactly the strategy I used, but after asking a friend he told me my way of calculating mu wasn't efficient enough (I actually factored each number from 1 to 1000000 instead of writing down a factor in the array when sieving).

Hey, what is the strategy for doing the mobius function problem efficiently? I see how to determine mu(i) efficiently, but i find M(i) to be the problem. I can see how many non-square-free numbers there are less than i, but how do you deal with checking how many sqyare-free numbers less than i have ...

have you tried iterative deepening on this problem ?

i do not know how well it will perform since i have no bound on how many operations the answer will be, but it's worth a try maybe

i have not read all ur code, but i see u make the assumption that each line is no longer than 10,000 characters. i am not sure you can assume this. gl.

P.S.
if any admins see this, i think the juge is missing some critical test inputs for this problem

i wrote a program that did the following and ...

isn't that like cheating?:)

edit: i switched to C++ and used string to avoid a static array since the input constraints don't say how long each word is to get AC.

[c]
CUT
[/c]

don't let the habit of always having < or >= in for loops mess you up too

[c]
AC
[/c]

why mod by even things ? just check mod by 2 in the beginning then you can speed things up by a factor of 2.

[c]
int i;
if (n<2) return 0;
else if (!(n&1)) return n==2;
else {
for (i=3;i*i<=n;i+=2) if (!(n%i)) return 0;
return 1;
}

[/c]

I tried to use BFS to solve this problem, but got SIGSEV. Does anyone see what is wrong? I've tried littering the code with asserts, but it was no help. :( The idea of my code is to keep track of which states have been visited in the states array. states [j][2] is 0 iff we haven't visited the state ...

here's some shorter I/O. you can email/message me if you want more though. warning: I got PE on this problem so when you check your output against mine you should ignore extra whitespace (i'm not quite sure why i got PE. anyone see why?)

Input:

2

5
1 1
1 2
2 1
20 19
20 20
19 20
18 20
5 4
5 6
4 5 ...

hm, i haven't taken the time to reason through your code because it is so long (why so complicated?). my ac code is only 51 lines (of which 3 are just method declarations and 15 others just have a }).

do you have email for me to send you I/O? or if you use AIM/MSN messenger i am MinilekDOC on AIM ...

your code has many special cases and is kind of ugly to read. consider wrapping your minesweeper map by a frame of .'s to avoid all special cases

e.g. if u have a 3x3 minesweeper board, but a 5x5 frame around it


.....
. .
. .
. .
.....


my code is 30 lines by doing this, and it makes things ...

[c]
AC
made stupid mistake
[/c]

good luck

Input:


0 10000
40 40
1 10000
1 9999
0 9999
551 1807
3957 8978
2784 8208
8138 9707
3965 8178
843 8651
6055 9655
6399 8052
7362 8656
742 1185
2145 6359
3607 8999
6423 9662
5536 8242
1294 4157
32 99
932 4566
6155 7063
2196 5454
894 7486
8169 9119
9498 9894
2091 3582
7027 8695
164 9213 ...

[c]
AC
[/c]

EDIT:
To anyone else who may have the same stupid problem I did. The string I used to hold the expression was a char array of size 24 (at most 12 numbers, at most 11 operators, plus the '\0'). However, I forgot that some numbers could be 2 digits, which means the array size should have ...