Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[miauw62]

The while loop was sort of a mistake I made just before I posted the code here :x What's it called again, I think it was shotgun programming? I break stuff in trying to fix other things. Also, the problem says that I can assume that there is a solution. You have a good point though.
I fixed the loop fuckery to what it was and just replaced size with money. (could probably be money / 2 but w/e).
Anyway, it now works but isn't finding the correct solution, somehow. book1a and book2a are getting set with new values even though those new values are less optimal and I have a check in place to prevent this.

Code: [Select]

#include <iostream>
#include <vector>

using namespace std;
vector<int> books;
int findr(int value, int skip = -1);

int main()
{
   while (true)
   {
      int totbooks;
      int book1 = -1;
      int book2 = -1;
      int book1b = -1;
      int book2b = -1;
      cin >> totbooks;
      for (int i = 0; i < totbooks; i++)
      {
         int book = 0;
         cin >> book;
         books.push_back(book);
      }
      int money;
      cin >> money;
      for (int i = 1; i < money; i++)
      {
         book1 = findr(i);
         if (book1 == -1)
         {
            continue;
         }
         book2 = findr(money - books[book1], book1);
         if (book2 == -1)
         {
            continue;
         }
         else if ((book1b == -1 && book2b == -1) || abs(books[book1] - books[book2]) < abs(books[book1b] - books[book2b]))
         {
            book1b = book1;
            book2b = book2;
         }
      }
      int abc = books[book2b];
      int books1a = books[book1b];
      if (abc > books1a)
      {
         int temp = abc;
         abc = books1a;
         books1a = temp;
      }
      cout << "Peter should buy books whose prices are ";
      cout << abc;
      cout << " and ";
      cout << books1a;
      cout << ".\n\n";

      if (feof(stdin))
      {
         return 0;
      }
      books.clear();
   }
}

int findr(int value, int skip)
{
   for (int i = 0; i < books.size(); i++)
   {
      if (i == skip)
      {
         continue;
      }
      if (books[i] == value)
      {
         return i;
      }
   }
   return -1;
}
Specifically,

Code: [Select]

else if ((book1b == -1 && book2b == -1) || abs(books[book1] - books[book2]) < abs(books[book1b] - books[book2b]))This should prevent book1b and book2b being set to new values if the new values give a larger price difference. Yet this input:

Code: [Select]

4
4 6 2 8
10results in an output of 4 and 6. A breakpoint at the check tells me that the values are indeed being overwritten from 2 and 3 (positions in the vector) to 0 and 1.

I also don't see how book1 = findr(i) could be book1 = i;, since that gives no guarantee that said price is actually present. (it's probably an awful way to go about it, but it turns out im a terrible terrible terrible competetive programmer :c)

[MagmaMcFry]

Isn't 4 and 6 the correct result for that input?

I also don't see how book1 = findr(i) could be book1 = i;, since that gives no guarantee that said price is actually present. (it's probably an awful way to go about it, but it turns out im a terrible terrible terrible competetive programmer :c)

Try using typedefs (isbn, price) instead of raw int signatures. In this case you'd notice that i is an isbn variable, but findr expects a price as a first argument. So you can't actually pass i to findr.

EDIT: Oh wait you changed i to price type instead of isbn? That basically breaks your runtime to hell and back:

2
100000000 100000000
200000000

Also your code is incredibly muddled by now, you should think about just rewriting everything from scratch.

[miauw62]

i is the price, it's horribly inefficient ;_;
That's why my program wasn't working before: i was checking all book numbers instead of all prices as was the intention.
the correct answer would be 2 and 8, since this minimizes the price difference.

E:
And at this point, it isn't actually muddled.

[MagmaMcFry]

The difference between 2 and 8 is 6. The difference between 4 and 6 is 2. Pretty sure your program did better than you.

Code: (Pseudocode linearithmic solution btw) [Select]

read numBooks, prices, money;
sort prices ascending; //<-- Linearithmic part
i = 0; j = numBooks-1;
p1 = p2 = 0;
while (i < j) {
  if (prices[i]+prices[j] > money) {
    --j;
  } else if (prices[i]+prices[j] < money) {
    ++i;
  } else if (prices[i]+prices[j] == money) {
    p1 = prices[i];
    p2 = prices[j];
    --j;
    ++i;
  }
}
print("Peter should buy books whose prices are " + p1 + " and " + p2 + ".\n\n");


[miauw62]

Oh. Welp.
>.>
I think I'm going to stop coding right before I go to sleep.

[Reelya]

The difference between 2 and 8 is 6. The difference between 4 and 6 is 2. Pretty sure your program did better than you.

Code: (Pseudocode linearithmic solution btw) [Select]

read numBooks, prices, money;
sort prices ascending; //<-- Linearithmic part
i = 0; j = numBooks-1;
p1 = p2 = 0;
while (i < j) {
  if (prices[i]+prices[j] > money) {
    --j;
  } else if (prices[i]+prices[j] < money) {
    ++i;
  } else if (prices[i]+prices[j] == money) {
    p1 = prices[i];
    p2 = prices[j];
    --j;
    ++i;
  }
}
print("Peter should buy books whose prices are " + p1 + " and " + p2 + ".\n\n");


There's a problem here, if you throw away the "less than" options, then if there are no exact value amounts that fit, then the algorithm will fail to return a value. What you want to record is the "best so far" match for each "less than or equals" pair. This would be important if the algorithm is to extend to dollars/cents values, like you have $40 to spend and the best books are $29.99 and $9.99

So, I'd say when you get the "<" check, you calculate how close the match is to the spending money, and update it if it's closer than a previous-best. Set "best" to the maximum at first, and update the pair any time you find one better. Combine the "<" and "=" branches into "<=" (with another variable to track "best fit" and only update the pair if it's a better fit), and let the ">" check catch all the times you need to decrement "j".

Code: [Select]

read numBooks, prices, money;
sort prices ascending; //<-- Linearithmic part
i = 0; j = numBooks-1;
p1 = p2 = 0;
bestfit = money;
while (i < j) {
  if (prices[i]+prices[j] > money) {
    --j;
  } else if (prices[i]+prices[j] <= money) {
    if(money-prices[i]-prices[j] <= bestfit)
    {
        p1 = prices[i];
        p2 = prices[j];
        bestfit = money-p1-p2;
    }
    ++i;
  }
}
print("Peter should buy books whose prices are " + p1 + " and " + p2 + ".\n\n");

[MagmaMcFry]

I actually considered the problem as it was described on the site.

You can consider that is always possible to find a solution

But yes, your method would be a logical generalization of the problem and solution.

[miauw62]

I didn't link the site because i got a redirect loop error. I fixed that now.

anyway, i optimized my program to be... I think O(n)? Not quite sure.

Code: [Select]

#include <iostream>
#include <vector>
#include <string>

using namespace std;
short books[1000000];
int money = 0;

int main()
{
while (true)
{
int totbooks = 0;
cin >> totbooks;
if (totbooks == EOF || feof(stdin))
{
return 0;
}
for (int i = 0; i < 1000001 && i < money; i++)
{
books[i] = 0;
}
int book1 = -1;
int book2 = -1;
int book1b = -1;
int book2b = -1;
for (int i = 0; i < totbooks; i++)
{
short book = 0;
cin >> book;
books[book] += 1;
}
cin >> money;
if (((money & 1) == 0) && books[money / 2] > 1) //the first statement is to check if money is even.
{
book1b = money / 2;
book2b = money / 2;
}
for (int i = money / 2 + 1; i < money; i++)
{
if (books[i] != 0 && books[money - i] != 0)
{
book1 = i;
book2 = money - i;
}
else
{
continue;
}
if ((book1b == -1 && book2b == -1) || abs(book1 - book2) < abs(book1b - book2b))
{
book1b = book1;
book2b = book2;
}
}
if (book1b > book2b)
{
int temp = book2b;
book2b = book1b;
book1b = temp;
}
cout << "Peter should buy books whose prices are ";
cout << book2b;
cout << " and ";
cout << book1b;
cout << ".\n\n";
}
}
The last hurdle is the goddamn EOF that I have to read. It just jumps into an infinite loop of "Peter has to buy books -1 and -1" when it encounters it, despite checks.

[Thief^]

correct me if I'm wrong but I don't think "cin >> totbooks;" will read an actual EOF character, so "totbooks == EOF" will never be true. I'm not sure feof will work either given it tests the C stdin not the C++ cin stream.

Supposedly the correct thing to do is:

Code: [Select]

if (cin >> totbooks)
{
 // read succeeded
}or

Code: [Select]

if (!(cin >> totbooks))
{
 // read failed
}

[miauw62]

Thank you! That seems to work.

E:
I'm still getting wrong answer, though.

[Reelya]

I need to set up a blog as part of my coursework, either using the colleges in-house system or setting up my own. I'd prefer to set up my own.

Does anyone have a suggestion for a library or software which would be good, plus quick to deploy? My paid server space is linux-based, and I could do Wordpress if that's the right way to go, though I have no experience with using it.

[Arx]

Wordpress is good, and presumably moderately user-friendly since plenty of non-coders use it for their blogs. I've used the free x.worpress.com version, and it's pretty customisable and functional.

[MorleyDev]

I use ghost, personally (http://blog.morleydev.co.uk/). It's open source, written in node.js so easy to set-up and fairly hackable, and it's still actually a blogging platform, whilst Wordpress is a platform system that evolved into being a CMS.

In fact, I use "Wordpress Syndrome" to describe the specific type of feature creep where tangentially related features are brought in that turn a product into a completely different product. Nowadays Wordpress is more like a CMS that just happens to include a blogging plugin by default.

[Antsan]

It always bugs me if the only navigation between posts in a blog is going into the archives, if there is no link to the first post but in the archives or if there are no archives. Reading these blogs as a new reader always is tedious.

[Angle]

Trying to get my websockets to talk, and they're having none of it. http://stackoverflow.com/questions/28523294/websocket-web-application-access-denied-java-util-propertypermission-org-gla