## HELP WITH NCPC

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

### HELP WITH NCPC

I already solved 10789 to 10794. so i want to solve the rests i mean 10795 to the last. help me please. just give me ideas to solve the problems.
Self judging is the best judging!

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

### Re: HELP WITH NCPC

At first you should solve the easiest problem in the volume.I do not know
How many problems have u solved in volume.However I think when u will continue to use the above tecknic onday you can easily solve the problems Exactly.It is better to take the idea of some problems but not
better for all Problems.I think u have understood this.Ok.
Mr. Arithmetic logic Unit

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
Well, if you see my statistic you will notice that i have solved 250+ problems. but i am HSC student. so i do not get much time to practise programming. and for that reason i saught help. if you can plz!
Self judging is the best judging!

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
I think, TISARKAR was refering to the fact that in a particular problemset it is quite impossible to solve all of the problems( unless you are Per Austrin or someone of that calibre).
Since you have already solved 6 problems out of 11...... you have done your job! and you should concentrate on solving problems from other sets.

But if you are desperate to solve all the problems from NCPC, then you can look at discussions relating to the unsolved problems by searching this board. I'm sure you will find a lot of useful information.

shanto86 wrote: Well, if you see my statistic you will notice that i have solved 250+ problems. but i am HSC student
Good job. Keep up the good work.
You also mentioned that you don't get enough time to practise, but I know a HSC student who solved 650+ problems.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
May be you are reffering to Nafi right?

well, yes i want to just know the tactics to solve the rest 5. i know that will be tough. but i am enthusiast. i think this type of learning is veru useful to becoming good in programming.

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)
Self judging is the best judging!

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
well, you are right adrian. yes i also believe that deriving algorthm is the main and most interesting work. but if you fail then you need help and if you learn how to solve that problem you will be able to learn more and it is a way of learning right? and i just asked ofr it.

for G, i first though of BFS. but as the maximum disk is 60 so in worst case it will take about 2^60 space or iteration. that means i need some thing DP or formula right?

Self judging is the best judging!

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
but if you fail then you need help and if you learn how to solve that problem you will be able to learn more and it is a way of learning right?
I am not sure about that. Certainly you need to know basic problem solving techniques, but the solution for one difficult problem itself often doesn't help to solve other problems, whereas finding the solution yourself does help. So what you have to do to improve is to practice problem solving on a lot of problems (at least that is what I did).
G can be solved recursively in O(n) or O(n^2) using the idea that a pile of disks from 1 to i can be moved to another peg in 2^i -1 steps.
For K, you have to find a formula.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### oh no!

Shanot86 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)
I didn't realize that the point that I made would make anyone angry. I thought it was a good suggestion.

My point was that since the other problems from that set are relatively much more difficult, it would be a good idea to solve other easier problems from a different set. By solving other similar, easier problems you will ultimately reach a position where you will not require help from others to solve the rest of the NCPC problems... and that should be the main goal, shouldn't it?
I mean if you solve all the other hanio problems, then you will be able to genearte ideas of your own, even if you don't succeed in it.

I get more satisfaction by solving a hard problem than by solving 5/6 easy problems. And the magnitude of contentment augments if I generate the idea from scratch, by myself.

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
I do agree with Sohel. Not only that, I must mention that this sorts of mentality may be proved destructive, as well. Back in my early days in UVa (Shanto, please note that I was a H.S.C student like you at that time), I had had thoughts similar to Shanto sometimes. Very often I would stick to 1/2 very difficult problems & desperately wondered why shouldn't I be able to solve it. But the very fact was that I was not good enough to solve then by the time. It was only when I gave up this idea & started to solve problems within my ability alongwith increasing my skill, I started to get improved. It is noticable that, returning to many of those problems after some months, I found many of them even not worthy of giving a tought. So, I would like to tell you one thing Shanto, I know you are a very good programmer & have a bright future but you can never ignore the value of experience. It's required, try to fetch. Very best of luck to you.
You should never take more than you give in the circle of life.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
Well, actually different people thinks in different way. I know experience is a great factor. But actually as it is my exam very near so I can
Self judging is the best judging!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
[quote="shanto86"]Anyhow, Adrian said recursive is needed for G. is it backtracking? I don
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
[quote="shanto86"]As I have read entire NCPC problems and last problems rises feeling they are easy but I can

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
Ok, let me think on K.

For the first sample input, 1 10 4.

Here there are 10 buildings from 1 to 10. we need to count the ways we can chose 4 buildings that fulfills our constraint. Right?

But why the answer is 4?
We can choose:
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
5 6 7 8
Self judging is the best judging!

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
shanto86 wrote:But why the answer is 4?
We can choose:
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
5 6 7 8
1+2+3+4=10 which is not divisible by 4. Read the second criteria.
shanto86 wrote:Will this loop around d give AC? Have I to make strict formula?

this code needs Big number algo or long long will be enough? [i think big number algo.]
I think any loop will give you TLE.
long long is enough.