HELP WITH NCPC

[shanto86]

Well I found formula for K myself. (just after about 20 minutes from posting the last post) See:

[b]Removed.[/b]

Now my question can it be made much more simple? After seeing the formula I think that long long may not help. I have to use big number algo. Right? If I get AC in it, it will be the first one big number formula type problem solved by me.

Cho said long long is enough, so i am going to code that in long long. but i am not sure! anyway let me see:

Mahbub

[..]

1. I personally think it is not so good to post the formula directly........
2. rewrite your formula

Code: Select all

X(high-low+1) + (1-k)*X*(1+X) 
X(high-low+1) + X*(1+X) - k*X*(1+X)

As X <= 20000000, you see that the sum of first 2 terms can be held by long long. And the final answer >= 0, so I also know the 3rd term won't make overflow on long long.

[shanto86]

Wai,
the formula i posted in my last post was wrong. so you don't have to worry. i corrected my formula and just now i got AC in 1st chance. now i have much more confidence on big number formula type problem. now tell me which one should i start to think? G,H,I or J? 4 is left.

[shanto86]

Well I am not sure but is Problem I easy? I know about median and solved some problems related to medians. So I first thought that it can be median problem. but now I do not think so. Because I got a counter example so perhaps I can

[kzaman010]

I think as an HSC student of Bangladesh what u have done so far (7 probs of NCPC) is great. I really appreciate your enthusiasm and spirit. But like others I also want to say that this is not the best approach to be a great problem solver. In this way you may be a great offline performer but in real time you will fail. If u solve a problem from scratch and without any hint, u will not only solve that problem but also learn so many things which will be helpful in other problems. Also, some theoretical knowledge is necessary which you will learn gradually. I am not asking you to stop trying tough problems, but I will advise that you should urself try without any hint. It may take long time to solve a problem, but it will really help you in real time contests and competitive environment. Now -

G-Different Task: Soln is very easy but formulation is tough and U have to know that 2^n - 1 moves is required to transfer all the disks from one peg to another one.

H-Right Hand Rule: Basically a search problem with one very very special case. I think, the knowledge of BFS or DFS and understanding the Right Hand Rule is enough in this case.

I - : Its a advanced computation geometry problem. I have no idea about its soln. But no simple approach will succeed in this case.

J - Roses : The main part is finding the state space. I think you should think about this problem without any hint or info from Board. You will learn lots of important things of Search problem.

I hope u will continue your try and will be a great problem solver of Bangladesh.

Best of luck.

[Observer]

Hehe... I love the problem of "Right Hand Rule"~~ You really have to be meticulous when solving this. I overlooked something trivial, and that caused me 10s of WA...

I have one little question for "Roses". Is it supposed to be solved by heuristic searches? To me, the state space looks huge...

[kzaman010]

You are right that the state space is large but it can be managed by the available memory. In fact initialization is the costly part of my solution, the search takes less time. I dont think any special heuristics is necessary, only a simple bound of previously available best solution is enough.

[shahriar_manzoor]

To Shanto,
Posting the solution is not right, Even if it is not correct because when you pasted it you did not know that it was wrong. So against such an advice u should have said sorry, but you have said "you don't need to worry..". Arrogance is bad no matter how good solver u are.


Problem I has something to do with median even if it is not in an stranght forward way.

[sohel]

Nice to see that people like Shahriar Manzoor and Md. Kamruzzaman got involved in this thread and gave shanto86 advices..
... Hopefully shanto86 will listen to them and take there advice.


I think the moderators should do something about some posts where the close form of some problems is directly given and it becomes just a matter of copy-paste to increase the number of solved problems.

I must admit, some of my posts are also spoilers and should be removed.
This will eventually cause the ranklist to reflect the true ranks.

[shanto86]

@monzoor vi, well you are right from your point of view and I am accepting your argument. But actually to post soln was not my aim. The aim was to ask

[shahriar_manzoor]

As now the board is being upgraded so I don't have the delete right. When I had the right I used to delete such posts with solutions and ofcourse I don't read all the posts.

A n-bit signed number has the range -2^(n-1) to +2^(n-1)-1 and if this is memorization then just think the number of different ways n positions can be filled only with zero and one. Equally divide this way info negative and non negative parts. Remember that positive numbers start from zero. OR just search with google to read how binary numbers work and how how numbers are represented in computer. The floating point representation is very interesting!! Without reading that u just won't realize why floating point errors are caused and how they can be reduced.

[shanto86]

Thanks monzoor vi, that's all what i wanted with data type. Thanks.

[Observer]

You are right that the state space is large but it can be managed by the available memory. In fact initialization is the costly part of my solution, the search takes less time. I dont think any special heuristics is necessary, only a simple bound of previously available best solution is enough.

Ah I've overlooked an important fact that the minimum guaranteed number of rose trampled will never exceed 10, thus a simple search is indeed possible for this problem...

Thanks for your advice!!

[shanto86]

Well, I myself code it in DFS but got TLE. why? i can't see any reason of it! I am not sure but is it forbidden to post code to seek help from other? anyhow i am posting but if i get ac or if you say then i will remove it.

#include<stdio.h>

char path[30][30],garden[30][30];
int n,now;

void start(int row,int col,int pluck)
{
if(path[row][col]=='r' || path[row][col]=='X')
return;

if(path[row][col]=='R')
{
pluck++;
path[row][col]='r';
}
else
path[row][col]='X';

if(row==0 || row==n-1 || col==0 || col==n-1)
{
if(now>pluck)
now=pluck;
return;
}

if(row!=0)
start(row-1,col,pluck);
if(row!=n-1)
start(row+1,col,pluck);
if(col!=0)
start(row,col-1,pluck);
if(col!=n-1)
start(row,col+1,pluck);

if(path[row][col]=='r')
{
pluck++;
path[row][col]='R';
}
else
path[row][col]='.';

}

int min(int a,int b)
{
if(a<b)
return a;
return b;
}

int main()
{
int i,dir,ans[5],j;

while(scanf("%d",&n)!=EOF)
{
if(!n)
break;

for(i=0;i<n;i++)
scanf("%s",garden[i]);

if(n==1)
{
printf("At most 0 rose(s) trampled.\n");
continue;
}

for(dir=0;dir<4;dir++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
path[i][j]=garden[i][j];

now=n/2;
start(n/2,n/2,0);
ans[dir]=now;
}

now=100;
for(i=0;i<4;i++)
now=min(now,ans[i]);

printf("At most %d rose(s) trampled.\n",now);
}
}

[Cho]

1. Please put the code into "code-block". No indentation is very hard to read.
2. It looks like a simple back-tracking. TLE is expected and you should be responsible for testing it with some 21x21 test cases.
3. Can you pass all the test cases in this thread?