Why my solution does not work?

#	User	Rating
1	jiangly	3976
2	tourist	3815
3	jqdai0815	3682
4	ksun48	3614
5	orzdevinwang	3526
6	ecnerwala	3514
7	Benq	3482
8	hos.lyric	3382
9	gamegame	3374
10	heuristica	3357

#	User	Contrib.
1	cry	168
2	-is-this-fft-	165
3	atcoder_official	161
3	Um_nik	161
5	djm03178	157
6	Dominater069	156
7	adamant	154
8	luogu_official	152
9	awoo	151
10	TheScrasse	147

Hello there,

I was solving problem 2001D and I came up to pretty straightforward conclusion that explore all permutations and output the lexicographically smallest one. Now, when I implemented this in code, it didn't work.

Code

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

using ll = long long;
using str = string;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) x.size()

const char nl = '\n';

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << ": " << __func__ << ": " << #x << " = " << x << nl;
#else
#define dbg(x) 42
#endif

bool LS(vector<int> a, vector<int> b) {
    int n = sz(a);
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            a[i] *= -1;
            b[i] *= -1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) continue;
        if (a[i] < b[i]) return true;
        if (a[i] > b[i]) return false;
    }
    return true;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (s.count(x) == 1) {
            continue;
        }
        s.insert(x);
        a.pb(x);
    }
    vector<int> res;
    res = a;
    do {
        if (LS(a, res)) {
            res = a;
        }
    } while (next_permutation(all(a)));
    cout << sz(res) << nl;
    for (auto x : res)
        cout << x << " ";
    cout << nl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll tt = 1;
    cin >> tt;
    for (int i = 1; i <= tt; i++) {
        #ifdef LOCAL
        cout << "Case #" << i << ": starts" << nl;
        #endif
        solve();
        #ifdef LOCAL
        cout << "Case #" << i << ": ends" << nl;
        #endif
    }
    return 0;
}

Any help will be deeply appreciated!

Comments (3)

Write comment?

MAieshAdnan

3 hours ago, # |

Auto comment: topic has been updated by MAieshAdnan (previous revision, new revision, compare).

→ Reply

Hassouna_

2 hours ago, # |

← Rev. 3 →

There is a significant difference between the concepts of a $$$Subsequence$$$ and a $$$Permutation$$$ of a given array. In this problem, the final answer must include all unique elements present in the array. However, not every permutation of the array can be derived as a subsequence of the original array.

For example, consider the following test case:

Test Case

We know that the final answer will include three elements: 1, 2, and 3. Some permutations of the array {1, 3, 2} (referred to as a in your code) cannot be valid answers because they cannot be extracted as subsequences, such as {3, 2, 1}. In contrast, only the permutations {1, 3, 2} and {1, 2, 3} can be subsequences of the original array.

Finally, regardless of the code's logic, its complexity is very high since generating all permutations of an array has a time complexity of $$$O(n!)$$$, where $$$n$$$ is the size of this array.

HVCYM

Need help with the following problem :

Given an array of n integers. Count the number subsequence whose product is divisible by k. Return answer modulo 1E9 + 7.

1 <= n <= 1E5 1 <= k < 1E9 1 <= a[i] <= 1E9

I think idea is use to prime factorization but I am not able to get it completely.

MAieshAdnan's blog