Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution B - Wrong Solution

B. Wrong Solution

Score: 1

CPU: 1s
Memory: 1200MB

Given a list of stock values, where the i-th element is the value of the stock on the i-th day. Find the maximum money you can earn by buying and selling stocks, given that you can buy or sell (not both) only one stock on a particular day. However, you can have multiple stocks with you at any point of time. You have to buy a stock before you can sell it.

Example:

stock_prices[] = {2,4,6,8,10},Optimal solution would be {(1,5), (2,4)} (1-based indexing), which means :

1. buy a stock on day 1 and sell that on day 5.
2. buy a stock on day 2, and sell it on day 4.

This way you can earn: 10 + 8 – 2 - 4 = 12.

For this problem, someone has submitted the following code. The idea of the code is given briefly (initially all the stocks are unmarked):

1. Find the day X where the stock value on day X is the maximum among all the days not yet marked. Choose the rightmost one in case of tie.
2. Find the day Y where Y is before X (Y < X) and stock value on day Y is the minimum among all the stocks not yet marked. Choose the stock from leftmost one in case of tie.
3. Add stock_prices[X] – stock_prices[Y] to profit. Mark day X and Y.
4. Repeat step 1 – 3, as long as you can find both X and Y.

#include<bits/stdc++.h>
using namespace std;
#define MX 1002
int stock_prices[MX], nDay, marked[MX];
int getMaximum(int start, int end){
   int ret = -1, mx = 0;
   for(int i = start; i <= end; i++){
       if(!marked[i] && mx <= stock_prices[i]){
           mx = stock_prices[i];
           ret = i;
       }
   }
   return ret;
}
int getMinimum(int start, int end){
   int ret = -1, mn = 1000000000;
   for(int i = start; i <= end; i++){
       if(!marked[i] && mn > stock_prices[i]){
           mn = stock_prices[i];
           ret = i;
       }
   }
   return ret;
}
int getProfit(int start, int end){
   int profit = 0, i;
   for(i = start; i <= end; i++) marked[i] = 0;
   while(1){
       int X = getMaximum(start, end);
       int Y = getMinimum(start, X - 1);
       if(X==-1 || Y==-1)break;
       profit += stock_prices[X] - stock_prices[Y];
       marked[X] = marked[Y] = 1;
   }
   return profit;
}
int main(){
   scanf("%d", &nDay);
   for(int i = 1; i <= nDay; i++)scanf("%d", &stock_prices[i]);
   int profit = getProfit(1, nDay);
   printf("%d\n", profit);
   return 0;
}

But this code is actually wrong for some test cases. Find one such case. You need to write a program which will generate the case and print it as output. A sample program is given here which will produce the output of the sample output. You need to submit your program.

#include<bits/stdc++.h>
using namespace std;
int main(){
   int nDay = 5;
   printf("%d\n", nDay);
   printf("2 4 6 8 10\n");
   return 0;
}

Input

There is no input.

Output

Write a program that will print the case in the following format. First line: Number of days, nDay Second line: nDay numbers: stock_prices, which indicates the stock prices from day 1 to nDay.

In your test case, you need to maintain each of the following constraints:

1. 100 ≤ nDay ≤ 200
2. 0 < stock_prices[i] ≤ 1000
3. Optimal maximum profit for the test case must be positive.
4. Profit given by calling getProfit(1, nDay) must be less than the optimal maximum profit for your test case.
5. Your test case must be such that the following function (check) should return true for your test case. You should assume that theoptimalResult(stock_prices, 1, k) function returns the optimal maximum profit for the subarray from index 1 to k in stock_prices.

bool check(int stock_prices[], int nDay){
  int k; 
  for(k = 1 ; k <= nDay - 4 ; k++ ){
      int X = getProfit(1, k);
      int Y = optimalResult(stock_prices, 1, k);
      if(X != Y) return false;
  }
  return true;
}

The sample output is not a correct solution to this problem. It’s just to show you the format.

Sample

Input	Output
No Sample Input	5 2 4 6 8 10