Problem Solving - Index

[wolfsinner]

This topic will serve as an index, or listing, of all the problems that are a part of the Problem Solving series I've been doing. This way they won't get lost.

Somewhere in the near future I'll write a few "Problem Solving basics" articles where I explain a few techniques used in solving problems (graphs, combinatorial optimization, time complexity, etc), those will also be listed here.

 

Problems

 

Problem #1 - Deletable Primes (Discussion | Gateway)

Problem #2 - Sharing is Caring (Discussion | Gateway)

Problem #3 - Polygon Phobia (Discussion | Gateway)

Problem #4 - Lego Mosaics (Discussion | Gateway)

Problem #5 - User-Friendly Manuals (Discussion | Gateway)

Problem #6/7 - Solving the N-Puzzle (Discussion | Gateway (C <= 3) | Gateway (15-Puzzle))

 

Articles

 

None.

 

 

 

If you have any suggestions for problems, articles, or would like to contribute in some other way to the series, this is the place to say it (or via PM to me).

[MG2R]

I made it all icky sticky

[Maximation]

Very good! I am looking forward to your articles on problem solving. I hope this will stay an active part of the programming subforum.

[wolfsinner]

I just added Problem 4, Lego Mosaics.

[wolfsinner]

So I've got a few things to inform everyone of. If you're an active participant in the Problem Solving thing, intend to become active, or just read this out of curiosity, I'd appreciate it if you "like" this post so that I know who's been informed.

 

First of all, I just added Problem #5, so there's that.

Second, I'll be travelling during most of the month of August (I "take off" this Monday) and as such I won't be as active as I'd want to be in the forums. That also means it'll be much harder for me to put out a problem every week. I'll still try to post at least one during the month of August, but I can't guarantee anything. I'll return to my regular "routine" in September. If someone is interested in replacing me while I'm gone, please PM me so we can talk about it.

 

Lastly, I just want to share a few things about the gateway itself. I've been working on a system that actually runs your code and compares its output to the correct output in the server. So you'd post your code at the gateway and everything is tested for you. This will allow me to add a few things like:

• Time limits for run-time.
• Memory limit constraints.
• Automatic testing and compiling.
• Users being able to see other's "successful" code, once they've solved the problem themselves.
• Perhaps a point system for grading the quality of a solution automatically.

Anyway, I was hoping I would have it done by now, but I didn't have enough time. It's a delicate process since I need to make sure the processes are properly isolated, limited and secure. I'll continue working on it when I come back.

 

And that's it. I hope when I get back to my "routine" you guys are still active and interested in this initiative.

[Maximation]

-snip-

Because I am on vacation right now I won't be able to solve any problems. However, when I return you're still traveling, so I can solve the past problems before any new ones get submitted.

Thank you for your dedication!

[wolfsinner]

Continuing the Problem #5 thread's discussion, I'm tagging @Nuluvius and @Tigerbomb8.
 
First of all, thank you for the suggestions. I'm very open to them.
 

That aside however I am going to play devil's advocate here and agree with @Tigerbomb8. There are a great many facets to programming and we have only been dealing with one so far, this being algorithms as I see it. Personally speaking, due to my own natural dispositions this particular area does not come easily to me by any means.
 
We are all unique and have come from unique circumstances which have shaped our current abilities, strengths and weaknesses. To state that it is not that hard is to subjectively address a specific area of strength perhaps? We may benefit our audience by diversifying our exploration of problems out into other areas as well; architecture and object design for example. Furthermore I also agree that we need some easier sub sections to further encourage and cultivate interest as we seem to be a little exclusive right now.

 

Problem Solving is very much limited to that: solving problems. It is very hard to quantify quality or evaluate success with architecture and design. I'd love to hear some suggestions on how to actually do this, as it is an interesting idea (albeit outside of the scope of Problem Solving itself, maybe a separate initiative could be started). Everyone's welcome to discuss their problem solving implementation's design though. I tend to write very lame code design-wise for Problem Solving since in a competition environment you really don't have much time to write pretty code, just efficient one.

 

I'd love to start as many programming-related initiatives as possible. Problem Solving just happens to be something I'm very strong at.

 

Also, @Tigerbomb8, I hope it didn't bother you when I said they aren't that hard. I just meant that with hardwork you could solve them. 

 

Easier sub-sections: I'll be working on a simpler problem today, and it might come out tomorrow. I just need to decide on what it will be. I also don't know how I should separate it from the main series. Maybe something like Problem N-A, N-B, N-C to identify different classes of difficulty for a given week.

 

Either way, I'm looking forward to hearing what you guys have to say!

[Ciccioo]

@wolfsinner, i am really in favor For the easier Series of problema: As someone already pointed out, this problem solving thing is just limited to a few people, i think there are much more peopleon the forum who would like and enjoy this, but are a bit scared by reading things they've never done

These simpler problem should have to teach people all those basic instruments that they need to face a General more complex problem

Maybe you could take a problem from the existing Series and break it down to the smallest subproblems. Every one of these subproblems would be a problem in the "basic" series

After solving all of those easy problems, a newconer should be able to finally face the original hard problem from the main series

The new series could even not be named "problem solving", but sonething like "Programming tools" "approaches" "tecniques" or whatever sounds better

Examples of topics covered could be "building a graph", "traversing a graph", "using the correct data structure"

sorry if i wrote something terribly, but it's hard to correct stuff on mobile

[MG2R]

--snip--

I think that's a great point. Lots of people here are still beginners in the programming field and are probably a bit scared off by the massive assignments. Even myself, after four years of different programming courses, am still a bit wary when I look at the problem.

 

I'll be interested in seeing what comes out of this. @OP, keep up the great work

[Nuluvius]

Problem Solving is very much limited to that: solving problems. It is very hard to quantify quality or evaluate success with architecture and design. I'd love to hear some suggestions on how to actually do this, as it is an interesting idea (albeit outside of the scope of Problem Solving itself, maybe a separate initiative could be started). Everyone's welcome to discuss their problem solving implementation's design though. I tend to write very lame code design-wise for Problem Solving since in a competition environment you really don't have much time to write pretty code, just efficient one.

 

I agree with you, there's a large subjective/qualitative segment in architecture and object design; many ways around a given problem or requirement. It also won't really come under what we are looking at right now. Furthermore it might indeed be tough to come up with a right or wrong definition to satisfy a problem as such? It makes me think back to my own days on my BSc Software Engineering degree. We would often have exercises whereby we had to pick out architecture from a set of requirements. In industry we will often stand around a whiteboard or use some other formalized methodology to identify what our architecture will look like. It often takes the form of a lot of UML... at least to begin with, then utilizing development methodologies such as TDD/BDD, the architecture will evolve and emerge more naturally.

 

It was interesting reading about the development you've been doing with the gateway though, that's what really made me think about this particular area. What about Cyclomatic complexity analysis/other software metrics... might be a step towards quantifying architecture. I haven't done any research on what kind of tools are available for doing this kind of thing in our particular context though.

 

Generally this was only an example and I'm just sounding out ideas... maybe there's more success to be had looking at data manipulation or even defining an application to be built. I'm looking across the broad width and verity of things that could be candidates for exploration.

 

-snip-

 

I completely agree with @Ciccioo, building blocks; this would be a fantastic way to introduce people to these concepts and build upon previous knowledge in smaller chunks.

 

-snip-

 

This is what I was really trying to get at earlier, I would imagine this might be a common feeling among our more junior or diverse audience. It certainly was for me

[Maximation]

Most of the problems I have encountered through this series of problems are indeed overwhelming for me. But because I have some basic knowledge about computer programming I just dive into the problem and learn more about the different concepts needed to solve it. It takes a lot of time though, and I do not know if that is the best way to learn about those new concepts. The "building blocks" idea seems great to me, as long as there is room for explanation of the subjects needed for that challenge I think it will be very good.

That is indeed what is needed for me, explanation. As I have never been introduced to these concepts before I would really like challenges where you will learn about subjects.

I am still learning, I started programming 1.5 years ago, I believe. As I am not allowed to go to college yet and programming courses on high schools suck I have to learn as much as I am willing to learn (and that's a lot) by searching the Internet. And that definitely isn't as easy as you would think. Sigh. I am spending way too much time on searching for quality stuff, and I do not even know where to search for. I have come to the conclusion that there are way too many beginner tutorials, but what you should do after you understand all the basics and basic concepts is really vague for me.

That's why I would like this section to be some form of guided learning opportunity while solving problems, it at least sounds good. That is just what I would like to see happening here.

But I am fine with everything else, as long as this will be continued.

[kingdorian]

By the way wouldn't it be easier to use the official LTT API for the login on the webportal?

[wolfsinner]

Hey everyone. Good news: I'm alive.
 
First of all, I'd like to point out that Ciccioo actually offered to post problems during the month of August, to which I agreed but failed to deliver him admin access to the portal in time. Sorry about that.

 

Next, I'm back but not in full force, at least for a week. There will not be a problem this weekend most likely, but I will be revamping some internals of the gateway over the next few days, mainly to accommodate the two genres of problems I intend to implement in the gateway.

First are the regular problems, which are basically the same problems we've been doing until now.

The new feature are the learning problems. The idea behind the learning problems is for the user to solve problems with help. Every problem is accompanied by all the information the developer will need to work on that program. There will be "middle" steps where the developer starts to work on and solve smaller, easier, problems that eventually lead him to achieve his final goal which is solving the main problem. These learning problems will teach things like graph theory, dynamic programming, etc through pretty drawings and by example.

 

I hope that helps ease everyone's concerns. I'd like everyone to voice their opinion on this idea.

The "tough as nails" problems you guys have been doing for about a month will still be around, but these other ones will serve as introductory courses for beginner problem solvers.

 

Finally, this idea can only be realized with the help of other people. Ciccioo agreed to help me with the problems, but I'd still like one extra person to join the "admin team" and help us. 

 

PS - I hope everyone's still on board with this idea.

[Maximation]

Hey everyone. Good news: I'm alive.

 

First of all, I'd like to point out that Ciccioo actually offered to post problems during the month of August, to which I agreed but failed to deliver him admin access to the portal in time. Sorry about that.

 

Next, I'm back but not in full force, at least for a week. There will not be a problem this weekend most likely, but I will be revamping some internals of the gateway over the next few days, mainly to accommodate the two genres of problems I intend to implement in the gateway.

First are the regular problems, which are basically the same problems we've been doing until now.

The new feature are the learning problems. The idea behind the learning problems is for the user to solve problems with help. Every problem is accompanied by all the information the developer will need to work on that program. There will be "middle" steps where the developer starts to work on and solve smaller, easier, problems that eventually lead him to achieve his final goal which is solving the main problem. These learning problems will teach things like graph theory, dynamic programming, etc through pretty drawings and by example.

 

I hope that helps ease everyone's concerns. I'd like everyone to voice their opinion on this idea.

The "tough as nails" problems you guys have been doing for about a month will still be around, but these other ones will serve as introductory courses for beginner problem solvers.

 

Finally, this idea can only be realized with the help of other people. Ciccioo agreed to help me with the problems, but I'd still like one extra person to join the "admin team" and help us. 

 

PS - I hope everyone's still on board with this idea.

 

Great! I am looking forward to the "learning problems", I am curious to see how those are going to be.

I would like to help your "admin team", but I do not know if I am of any value to you. That depends on what subject you want help with. If you need my help, you can ask for it , and maybe I will be of some value to you (I hope)

 

Thank you.

[MikeD]

Hey everyone. Good news: I'm alive.

 

First of all, I'd like to point out that Ciccioo actually offered to post problems during the month of August, to which I agreed but failed to deliver him admin access to the portal in time. Sorry about that.

 

Next, I'm back but not in full force, at least for a week. There will not be a problem this weekend most likely, but I will be revamping some internals of the gateway over the next few days, mainly to accommodate the two genres of problems I intend to implement in the gateway.

First are the regular problems, which are basically the same problems we've been doing until now.

The new feature are the learning problems. The idea behind the learning problems is for the user to solve problems with help. Every problem is accompanied by all the information the developer will need to work on that program. There will be "middle" steps where the developer starts to work on and solve smaller, easier, problems that eventually lead him to achieve his final goal which is solving the main problem. These learning problems will teach things like graph theory, dynamic programming, etc through pretty drawings and by example.

 

I hope that helps ease everyone's concerns. I'd like everyone to voice their opinion on this idea.

The "tough as nails" problems you guys have been doing for about a month will still be around, but these other ones will serve as introductory courses for beginner problem solvers.

 

Finally, this idea can only be realized with the help of other people. Ciccioo agreed to help me with the problems, but I'd still like one extra person to join the "admin team" and help us. 

 

PS - I hope everyone's still on board with this idea.

 

How's everything going? Do you have an estimate on when the new gateway or the next problems will be up?

I mean, you made it through summer, don't die on us now!!

By the way, since many people occasionally make mistakes when entering the results into the website perhaps you could move to something like mooshak for automatic evaluation (if that's not what you are already looking at)?

 

When I read "learning problems" I immediately thought developing applications or games as if it was a project for a class (kinda like starting by defining data types, develop logic for each aspect of the app and link it all together). However it seems to be more like taking a step-by-step approach at problems similar to the ones we've been solving, right? If so, would there be room for the first kind as well?

 

I'd very much like to help out with the problems, but I'm afraid I won't have much time in the foreseeable future between my dissertation and starting work.

 

By the way, since I didn't want to bump the old problem threads I'll just write a few notes here:

I was also away during summer and recently solved the last three problems; here are some thoughts:

 

P3: Damn those segments that start and end in the same point! I started with an excruciatingly slow depth-first search because it was the first thing that came to mind but then I saw the disjoint sets suggestion and all the repressed memories of the algorithms class came rushing back!

P4: Damn me for trying to manually copy the first results; obviously my pseudo-dyslexia had to kick in just then! Funny thing: I hardcoded in a dictionary the first 4 values on how many possible ways to arrange n contiguous stubs of the same color and left the bigger ones as a return 0 just to test what I already had and it was enough to solve all the inputs (actually, 3 would have sufficed I think). But yes, I figured out how to calculate it afterwards! And I found what I believe to be easter eggs in some of the inputs!

P5: Well, I apparently thought removing the edges to the successor as I visited them in order was the same thing as removing all edges first and then visiting... And then I wasted way too much time solving that problem! 

[wolfsinner]

How's everything going? Do you have an estimate on when the new gateway or the next problems will be up?

I mean, you made it through summer, don't die on us now!!

By the way, since many people occasionally make mistakes when entering the results into the website perhaps you could move to something like mooshak for automatic evaluation (if that's not what you are already looking at)?

 

When I read "learning problems" I immediately thought developing applications or games as if it was a project for a class (kinda like starting by defining data types, develop logic for each aspect of the app and link it all together). However it seems to be more like taking a step-by-step approach at problems similar to the ones we've been solving, right? If so, would there be room for the first kind as well?

 

I'd very much like to help out with the problems, but I'm afraid I won't have much time in the foreseeable future between my dissertation and starting work.

 

By the way, since I didn't want to bump the old problem threads I'll just write a few notes here:

I was also away during summer and recently solved the last three problems; here are some thoughts:

 

P3: Damn those segments that start and end in the same point! I started with an excruciatingly slow depth-first search because it was the first thing that came to mind but then I saw the disjoint sets suggestion and all the repressed memories of the algorithms class came rushing back!

P4: Damn me for trying to manually copy the first results; obviously my pseudo-dyslexia had to kick in just then! Funny thing: I hardcoded in a dictionary the first 4 values on how many possible ways to arrange n contiguous stubs of the same color and left the bigger ones as a return 0 just to test what I already had and it was enough to solve all the inputs (actually, 3 would have sufficed I think). But yes, I figured out how to calculate it afterwards! And I found what I believe to be easter eggs in some of the inputs!

P5: Well, I apparently thought removing the edges to the successor as I visited them in order was the same thing as removing all edges first and then visiting... And then I wasted way too much time solving that problem! 

 

Olá Miguel  :lol:

Well, for starters there will be a new problem this week. I've solved it, I'm just making some nice test cases and it should be up this weekend. It was actually suggested by a user here (I'll give credit in the problem thread).

As for the new gateway, it's on halt for the time being because I've been too busy lately and there are other things I need to prioritize, unfortunately. The first week of October should be a calm time, so I'll start then.

 

I've thought of Mooshak, yes. My experience with mooshak isn't that great because it's a little bit of a pain to configure, but it's an alternative I've considered many times. I want people to submit their code and have it run on the server. I personally don't like mooshak's interface, but it has already solved the problem of isolation and security so I might just go ahead and use it.

 

The learning problems idea is originally for the purpose of teaching problem solving techniques. Things like graph theory, dynamic programming, maybe some AI algorithms. I'm open to any kind of learning ideas though. I plan to make the new gateway very flexible in the sense that new series can be easily started. 

Your idea is to create "project tutorials", where beginner programmers could learn how to create software from scratch?

 

Glad you finished the remaining problems. I did notice that you had not done them yet.

[MikeD]

Olá Miguel  :lol:

Well, for starters there will be a new problem this week. I've solved it, I'm just making some nice test cases and it should be up this weekend. It was actually suggested by a user here (I'll give credit in the problem thread).

As for the new gateway, it's on halt for the time being because I've been too busy lately and there are other things I need to prioritize, unfortunately. The first week of October should be a calm time, so I'll start then.

 

I've thought of Mooshak, yes. My experience with mooshak isn't that great because it's a little bit of a pain to configure, but it's an alternative I've considered many times. I want people to submit their code and have it run on the server. I personally don't like mooshak's interface, but it has already solved the problem of isolation and security so I might just go ahead and use it.

 

The learning problems idea is originally for the purpose of teaching problem solving techniques. Things like graph theory, dynamic programming, maybe some AI algorithms. I'm open to any kind of learning ideas though. I plan to make the new gateway very flexible in the sense that new series can be easily started. 

Your idea is to create "project tutorials", where beginner programmers could learn how to create software from scratch?

 

Glad you finished the remaining problems. I did notice that you had not done them yet.

 

Boas!

Well, then, I look forward to solving it (after submitting a few incorrect answers and spending hours figuring out why)!

Until the last problem I thought the test cases were provided by the MIUP judges after the competition. How do you come up with them? Is it random or do you spend some time designing tests for the corner cases?

 

Yeah, I once tried to set up mooshak (a few years ago, out of curiosity since some of my classes used that for project submission) but I ended up just looking at some of the files because it was too bothersome to set up apache! But it shouldn't be hard to do, even to change the interface. And yes, many people have already worked on its security features.

 

As  for the learning problems, yes, I was thinking about some projects like enterprise applications or even simple games to teach architecture, abstraction and other software engineering techniques. But the evaluation of some of those types of projects are more focused on the quality of code rather than whether it passes all tests or not...

Still, I'll probably take some of those algorithms lessons 'cause, like I said before, I already forgot many of them and could always use some more problem solving practice!

 

I got stuck on the 3rd problem and then had to leave so I could only do the rest now. Better late than never!

[Nuluvius]

...

As  for the learning problems, yes, I was thinking about some projects like enterprise applications or even simple games to teach architecture, abstraction and other software engineering techniques. But the evaluation of some of those types of projects are more focused on the quality of code rather than whether it passes all tests or not...

...

 

These were my previous thoughts as well essentially.

[wolfsinner]

...

Until the last problem I thought the test cases were provided by the MIUP judges after the competition. How do you come up with them? Is it random or do you spend some time designing tests for the corner cases?

...

 

I wish! I can't get access to those, unfortunately. I try to make them tough to pass. I look for corner cases. I don't have that much time to dedicate to it though, so I can't guarantee my tests are of immense quality. I do my best with the time I have though.

I decide on a test case and write some code that will produce that input file for me.

[TizzyT]

OOPS Wrong Section...

 

Go here: http://linustechtips.com/main/topic/173405-problem-solving-1-deletable-primes/?p=3089897

[wolfsinner]

Hey hey!

Sorry for being silent lately guys. I'll have to level with you: I'm ending this initiative. I know it was very short-lived, but my personal life took a huge turn recently (for the best), and I find myself with very little time for these pet projects.

I may have time every now and then, but I like having a set schedule for new problem releases and that won't be possible to guarantee from now on, so I prefer to end it.

 

On top of that, I had a problem with my VPS provider (mostly my fault, sharp-eyed users may have noticed that the gateway has been down for about a week now). I've done everything humanly possible to try and recover the OS image I originally had on the server, but it seems like it is gone forever. I had no backups for the problem solving gateway, sorry. So that is also gone forever (I have the source code, but not the data).

 

If someone wants to reboot this initiative they're welcome to do so, and I may help when I have the time, but for the most part I won't be able to do much.

 

In other news, I'm currently working on a video course teaching basic algorithms and graph theory, which will be up next month and I'm willing to share it for free with LTT users. So there's that at least.

 

Finally, if you've enjoyed the initiative thus far, here are some cool websites you can check out:

UVa Online Judge

TopCoder

CodeChef

Project Euler

USACO Training

 

Some of them have great tutorials on problem solving and most have automatic judges. Sorry guys! I'll still be around in the Programming section though.

[Maximation]

Hey hey!

Sorry for being silent lately guys. I'll have to level with you: I'm ending this initiative. I know it was very short-lived, but my personal life took a huge turn recently (for the best), and I find myself with very little time for these pet projects.

I may have time every now and then, but I like having a set schedule for new problem releases and that won't be possible to guarantee from now on, so I prefer to end it.

 

On top of that, I had a problem with my VPS provider (mostly my fault, sharp-eyed users may have noticed that the gateway has been down for about a week now). I've done everything humanly possible to try and recover the OS image I originally had on the server, but it seems like it is gone forever. I had no backups for the problem solving gateway, sorry. So that is also gone forever (I have the source code, but not the data).

 

If someone wants to reboot this initiative they're welcome to do so, and I may help when I have the time, but for the most part I won't be able to do much.

 

In other news, I'm currently working on a video course teaching basic algorithms and graph theory, which will be up next month and I'm willing to share it for free with LTT users. So there's that at least.

 

Finally, if you've enjoyed the initiative thus far, here are some cool websites you can check out:

UVa Online Judge

TopCoder

CodeChef

Project Euler

USACO Training

 

Some of them have great tutorials on problem solving and most have automatic judges. Sorry guys! I'll still be around in the Programming section though.

 

That is sad, but I am happy for you that you let it go, as you indeed seem quite busy

I am really interested in your video course, I would love to learn more. And I want to thank you for the initiatives you started and for your helpful guidance. See you soon!

[wolfsinner]

Just a quick update. I managed to get the image back up, so the gateway is available again. All of the old problems are still there if new users want to give them a shot. (Gateway Link)