6. The mallow-coloured garden - solution

Solution I: Using nested loops

This solution uses two for loops, one nested inside the other. The outer loop simulates changing the deal, N times.
The inner loop takes the current number read in that iteration and compares it with the previous one within the same deal, i.e. from the previous iteration of the nested loop. In every new iteration the current number becomes the predecessor for the next iteration.
​If  in some iteration the current and the previous number are not in non-decreasing order, the current deal is declared "incorrect"  and the counter of incorrect deals is increased by 1. Using the outer loop, the procedure is repeated for the other "deals", so that at the end the value of the counter is actually the required number of incorrect deals.#include <iostream>

using namespace std;
/*

Example 1
Input
4
3
1
2
3
4
3
4
1
5
5
8
8
8
Output
1
Data for 4 deals are read. The first, third and fourth deals are arranged well.
The second deal with the cards 4,3,4 is not arranged well.
*/

int main()
{
int n,k,count=0,b,p;
cin>>n>>k;
for(int i=0; i<n; i++)
    {
bool good=true;
for(int j=0; j<k; j++)
        {
cin>>b;
if(j==0)
            {
/*The predecessor for the next iteration becomes equal to the number in the current iteration*/
                p=b; 
            }
else
            {
if(b<p)
                {
                    good=false; //The deal is not good
                    p=b;/*The predecessor for the next iteration becomes equal to the number in the current iteration*/

                }
            }

        }
/*If the deal is not good, the counter is increased by 1*/
if(!good)
        {
            count++;
cout<<i<<". ->"<<"not good"<<endl;
        }

    }
cout<<count<<endl;

return 0;
}

Note: in this version the predecessor p is updated only when b < p. For a deal such as 1 5 3 the program compares 3 with 1 instead of with 5 and does not notice the error. Move the line p=b; outside the if(b<p) block so that it runs in every iteration. The line cout<<i<<". ->"<<"not good" is only for checking and should be removed before submitting the solution.


Solution II: Solution using vectors.

Here we use vectors to store the numbers of the cards in every deal. Put the numbers on the cards into a vector for every deal. The deals are changed using a loop. We make a copy of the vector and sort it (only the copy) in non-decreasing order.
Then that copy is compared with the original vector.
If the original and the copy are equal, it means that the original vector was correctly sorted from the very beginning. So, if they are not equal, it is a "bad" deal and the counter of bad deals is increased by 1.
The procedure is repeated for the other deals, so that at the end the value of the counter is actually the required number of incorrect deals.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
int N, k; //Number of deals and number of cards in one deal
cin >> N >> k;

int errorCount = 0; //number of wrong deals, zero at the start

for (int i = 0; i < N; ++i) {
vector<int> cards(k);
for (int j = 0; j < k; ++j) {
cin >> cards[j];
        }

vector<int> sortedCards = cards; //Copy of the vector cards
        sort(sortedCards.begin(), sortedCards.end());

if (cards != sortedCards) {
            ++errorCount;
        }
    }

cout << errorCount << endl;

return 0;
}

Summary:

  1. Reading the input:
    • cin >> N >> k; reads the number of deals N and the number of cards in every deal k.
  2. Checking every deal:
    • vector<int> cards(k); creates a vector of size k to store the cards.
    • cin >> cards[j]; reads the cards of the current deal.
    • vector<int> sortedCards = cards; makes a copy of the cards which will be sorted.
    • sort(sortedCards.begin(), sortedCards.end()); sorts the copy of the cards.
    • if (cards != sortedCards) { ++errorCount; } checks whether the cards in the original order differ from the sorted cards. If they do, it increases the number of errors.
  3. Printing the result:
    • cout << errorCount << endl; prints the total number of deals in which the cards were not arranged correctly.
This program reads all the data, checks every deal and counts the errors according to the given conditions.