Programming

Programming Challenges Problems

Here’s the list the 21 problems I’ve solved on the Programming Challenges site.
If any ATR people have solved more I’ll have to start solving them again…

110101 The 3n+1 problem
110102 Minesweeper
110103 The Trip
110106 Interpreter
110107 Check The Check
110108 Australian Voting
110201 Jolly Jumpers
110202 Poker Hands
110203 Hartals
110207 Contest Scoreboard
110301 WERTYU
110306 File Fragmentation
110308 Fmt
110404 Longest Nap
110405 Shoemaker’s Problem
110406 CDVII
110504 Ones
110805 Tug of War
110903 The Tourist Guide
111302 Rope Crisis in Ropeland !
111308 How Big Is It?

The problems I can’t/haven’t solved and would love to hear of solutions for are

110104 LC-Display (edit 2008: now solved)
110206 Erdos Numbers (edit 2010: now solved)
110208 Yahtzee (edit 2010: now solved)
110307 Doublets
110801 Little Bishops
110804 Servicing Stations
111002 The Necklace

[Edit 2010] I have a newer, complete list here

Comments:

Amith Kumar 2008-02-08 18:26:19

hi ,
Im amith kumar from India.I came across your blog googling for solutions of “Trip” UV problem . I have been trying to solve this problem but I dont know whats wrong in my solution Im always getting WA on UV.Can you please help me to solve this. My code is :-

[Edit Removed overly long code]

Amith Kumar 2008-02-08 18:29:37

Oh I looks like comments cant be too big !!!

Is it possible for me to contact you in some other way to send you my (incorrect) solution

or can I see your correct solution

Thanking You in advance
Amith Kumar

Simeon 2008-02-11 13:30:58

Hello Amith,

Looking at your code I see some differences. I’ll give you (and anybody else) some extra sample input, and say what my answers are. You can then check them my hand to see if you think my answers are correct (follow the rules) then make your program follow that same rules.

5
15.00
15.01
3.00
3.01
3.01
11
15.00
15.01
3.00
3.01
3.02
3.03
3.04
3.05
3.06
3.07
3.08
0

$14.39 (yours $14.38)
$19.57 (yours $19.53)

Hope this helps you..

Amith Kumar 2008-02-12 08:49:45

Hello Simeon,
I got my mistake now. I was not considering the cases where (the total amount given) ! = (total amount taken ). Now I’m able to correct my code and get it run on the Programming challenges site.

Thanks a lot Simeon for giving the example which took me into the correct direction.

Jack 2008-09-11 04:09:25

Hello there Simeon,

I found your blog on a google search, and wanted to know if you could send me your solution codes of the following problems:

110306 File Fragmentation
110307 Doublets
110304 Crypt Kicker II

My email address is j3blizzard@yahoo.com.br

Thank you so much in advance my friend.

Simeon Pilgrim 2008-09-11 09:36:10

Giving out code is not my style sorry.

GUO 2008-12-21 18:06:54

Can you tell me how to solve Problem 110306？
I have no idea…..

Simeon 2008-12-27 22:04:52

Hello Guo,

Without actually looking at my solution the key points of this problem are:

You are given X number of fragments that make (X+1)/2 files. If there are an even amount there should he a head and tail pair set for all fragments. If there are an odd number there should be one fragment that is complete.

Once again without looking at the code, sort all the fragments by string size, then take in a backtracking method match head and tails of the list to find a combo. There maybe some corner cases when there are 2 or more fragments of the same length.

basically write some test data that covers these cases, then make your solution solve them.

Simeon

Santiago 2009-03-16 16:18:58

Hi Simeon, i’m brazilian programmer, and i solved Display problem, if you wanna see… Now i have a problem on “Trip”, my solution solved yours samples but in Prgramming Challenges it not solved :(. Can you help me? Sorry for my english, i don´t know very well.

Santiago.

Simeon 2009-03-16 16:26:10

Hi Santiago,

Don’t stress about your English, seems great too me, and is better than my non-existent Portuguese.

Cheers for the offer of the Display code, my code now passes, which shows the original judging was wrong.

Flick me your trip code to simeon.pilgrim@gmail.com and I’ll find some data that our solutions differ.

Simeon.

Santiago 2009-03-16 16:54:45

I sent my source for your email.

Thanks

Santiago

Simeon 2009-03-16 17:19:53

Try,

36
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
10000.00
10000.00
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
9999.99
0

I get $76388.73 while you get $76388.74

Rodrigo 2009-04-03 13:45:39

Hi simeon, i`am brazilian too. The problem Contest Scoreboard necessits validate a penalty time?(max 300). I don’t see other problem in my code.

Simeon 2009-04-03 13:59:55

Well if it’s any help my solution runs in 0.03 seconds, but without seeing your code my physic helping skills are limited.

Rodrigo 2009-04-03 14:57:41

I’ve been sent my code in your mail. If you could be help…

Simeon 2009-04-03 15:04:57

Hello Rodrigo,

I have three concerns with your solution:
1. your using a bubble sort, which will be the cause of your time limit.
2. you scoring method will give you wrong answers, once you solve the time limit.
3. use a any array of struct for ‘ resultado’ instead of double nested array of long. then you can have named members which will help with readability, not that it matters.

Rodrigo 2009-04-03 15:20:21

Thank for helpfull, but you could send me one test that you submit in my code and give the wrong answer? Thank a lot of tips in the mail.

Simeon 2009-04-03 15:30:17

1

1 1 25 C
1 1 26 C
2 1 25 C
2 1 26 I
2 1 27 C

should equal:
1 1 25
2 1 25

Edgarin 2009-04-08 19:25:11

Hi, I’m trying to solve CDVII, but get WA despite of my efforts…
After sharing info in forums, and improving my solution, I’ve considered many things:
· Enter km can be greater than exit km
· After sorting for each car, I search for an “enter”, then search for the next “exit” (ignoring enters in the middle) When an “exit” is found, i calculate the toll, otherwise it’s ignored (as the problem says) This process is repetitive
· If a car has nothing to pay, it doesn’t generate a bill

Am I omitting some important consideration? what could be wrong?
I can send you my C++ code, it’s relatively short

Please help me, I’ll thank you a lot

Simeon 2009-04-08 21:14:55

Sure, send me your code, email address: simeon.pilgrim@gmail.com

One lot of thanks will be enough.

Diego 2009-08-23 10:33:13

Hi Simeon:

I did sent you an email, explained you my situation thanks.

Diego 2009-08-23 14:42:48

Hi Simeon:

I did solve the proble already I just have a question why we need to add .05 to the average to solve the problem???

Diego 2009-08-23 16:05:10

Hi its me again, I just read the LCD problem litle help for this one I am clueless!!

thx

Bdanders 2009-09-07 13:00:02

I am having trouble with the trip problem, and so far I have solved every test case presented here, but I keep getting Wrong Answer from the Programming-Challenges judge. Any help would be appreciated.

here is the abridged code.

[Edited by Simeon to remove garbled code]

Bdanders 2009-09-07 13:01:21

oh of course, html garbles :/ I’ll email it.

Simeon 2009-09-08 13:23:57

The problem with you code is you don’t follow this rule “There are no more than 1000 student”

Alex 2009-10-31 04:30:09

Hi,
I have the same problem as the above poster but can’t understand what you mean by following the rule.
Will mail you my code just in case I miss something.

Simeon 2009-10-31 10:11:55

Hi Alex,

In the case of Bdanders, he didn’t allow for his solution to handle 1000 students trip costs, thus was failing, and the judge most likely tests that fact.

I’ll read you code now and see if I can see any major problems…

Simeon 2009-10-31 10:21:24

Well it’s nice and tidy code, and solves the body of the problem.

Your problem is the transition from double to int. Try loop from 01 to 100, divided it by 100 and store in a double, then turn the double back to an int via your method, and check they are the same number, the loop iterator and derived value.

Alex 2009-10-31 23:50:56

Thanks a lot for the help. Guess I will not count on the internal convertion anymore. :)

Simeon 2009-11-01 13:33:55

There is nothing wrong with how a double is converted (truncation) to an int, the problem is a double cannot accurately represent all floating point numbers, and therefore you need to round up to remove the error when converting.

Harinath 2011-12-25 15:17:50

Hi Simeon,

I could run the test cases presented here but the programming challenges judge gives me Wrong answer.Can you check my code, Ill mail you my code.

Beknazar 2012-05-21 10:20:03

Hi, Simeon!

Can you check this, please: 110103 The Trip

`using namespace std;

int main()
{
..deleted code body..
}`

Simeon 2012-05-21 10:47:35

Yes I can confirm this code will not work, for the exact reasons intended by the problem creator.

Hint, learn how floats work (or DONT ;-) ), and think about the problem more.

I notice you have not made it work against example set I’ve provided, so you are failing to even help yourself. Does your code even work against the problems examples???

For general advice to future people, in these “problems”, nearly every word is there for a reason. Just like a specification, it was written for a reason, learn to follow the instructions given, and also learn to read ‘between the line’ to find the un-specified parts, and think “how would I want this to work given N options”.

Luiz 2013-01-14 15:25:15

Hello Simeon,

I’m facing a problem with The Trip: for some set of values, my sum gets truncated due to the float representation For example, 10000.00 + 0.11 == 10000.1 . Have you faced this issue? How can I bypass it? I thought in get 2 integers, one for the integral part and one for the mantissa and then do the maths. But it is not amusing me (and I didn’t finished it yet)… Did you have a more clever/elegant solution? Thanks in advance.

Simeon 2013-01-14 15:32:17

Hi Luiz, Welcome to the one of the two lessons of this problem: Floating point numbers are not suitable for financial problems. You want to use fixed point (use a single int/long/long long, but know it’s talking cents, not dollars) thus your counting hundredths. Then do modulo/division when you want to output.

Luiz 2013-01-15 14:10:09

Is the other lesson the buffer overflow with input/output buffers?
I solved the issue with the floating point operations, but I still got the Wrong Answer result. Then I tried to test with 1000 inputs and the program halted. Do I have to manage the buffers so or it shouldnt be a problem? also, does the output for values greater than 1000 need to be like $70,000.00 or $70000.00? Thanks for your comments!

Simeon 2013-01-15 14:23:24

Well I have a an example of output for 5 digits, so I’d assume no comma.

Not sure how your halting/running out of buffers for 1000 input. However your solving the problems sounds very wrong.