bluetuber's blog

Help with problem 1862B
By bluetuber, history, 18 months ago, In English

Here is the problem link. Although, I think pretty much understand the problem, I am getting wrong answer on the first test case even though I am allowed to output any possible sequence.

#include<bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0 ; i < n ; i++) cin >> a[i];

    cout << 2*n-1 << endl;
    for(int i = 0 ; i < n ; i++){
        if(i == 0) cout << a[i] << " ";
        else cout << max(1, a[i]-1) << " " << a[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1; cin >> t;
    while (t--) solve();
}

The idea behind the solution is that since any a[i] in the original sequence 'a' can only be added if a[i-1] is less than equal to it I can greedily add a number less than or equal to b[i] before it in the final sequence 'b'. Help me understand faults in the logic/code.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Output for First Test Case according to your code is : - 4 5 6 2 3

According to this array a , array b will be 4 5 6 2 as 5>=4 , this is contradictory to the given array b .

→ Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    void solve(){
 
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0 ; i < n ; i++) cin >> a[i];
 
    vector<int> ans;
 
    for(int i = 0 ; i < n ; i++){
        if(i == 0 || a[i]>=a[i-1]) ans.push_back(a[i]);
        else{
            ans.push_back(1);
            ans.push_back(a[i]);
        }
    }
 
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
    cout << "\n";
 
}

    If the elements are already in increasing order no need to add anything , if the order is non increasing add a 1 to satisfy the condition.

    → Reply