An unexpectedly difficult problem

№	Пользователь	Рейтинг
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

№	Пользователь	Вклад
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	134
9	maroonrk	132
10	cry	130

Hi, I was solving this problem a few minutes ago, and the following problem is a subproblem of that one.

Given integer $$$n$$$, $$$ n \ge 3$$$, and array $$$a$$$ consisting of $$$n - 1$$$ integers, all of them are equal to some value $$$b$$$. Later, some integer $$$c$$$, such that $$$c \ne b$$$ is selected and inserted into the array $$$a$$$ at random position. By given $$$n$$$ and $$$a$$$ find $$$c$$$.

This problem itself isn't so difficult, but with a certain restriction I couldn't solve it. The restriction is folowing: you can't use $$$if$$$ and ternary operators in any way.

I came up with the solution, that calls $$$if$$$ only one time.

my solution

#include <bits/stdc++.h>

using namespace std;

int a[100001] = {0};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    if(a[0] == a[1])
        for(int i = (n & 1) ^ 1; i < n; i++)
            ans ^= a[i];
    else
        for(int i = 0; i < 3; i++)
            ans ^= a[i];
    cout << ans << "\n";
    return 0;
}

Can you solve this problem with the given restriction?

UPD: In the comments there is one of the solutions, and I've also came up with one.

my final solution

#include <bits/stdc++.h>

using namespace std;

int nxr[32] = {0};

void add(int a, int n) {
    int mask = 1;
    for(int i = 0; i < 31; i++) {
        nxr[i] += (a & mask) >> i;
        nxr[i] %= n;
        mask <<= 1;
    }
    return ;
}

int ans() {
    int mask = 1, ans = 0;
    for(int i = 0; i < 31; i++) {
        ans += nxr[i] * mask;
        mask <<= 1;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, a;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a;
        add(a, n - 1);
    }
    cout << ans() << "\n";
    return 0;
}

BledDest's solution is shorter, but mine is easier to understand, at least for me, this is just

spoiler

int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int b = (a[0] & a[1]) | (a[1] & a[2]) | (a[0] & a[2]); int c = b; for (int i = 0; i < n; i++) c ^= (a[i] ^ b); cout << c << endl; return 0; }

int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int res = 0; for (int x : a) res ^= x; res ^= ((n & 1) ^ 1) * ((a[0] == a[1]) * a[0] ^ (a[0] == a[2]) * a[0] ^ (a[1] == a[2]) * a[1]); cout << res << endl; return 0; }

Комментарии (17)

Написать комментарий?

fossil823656

4 года назад, скрыть # |

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

→ Ответить

bronze_coder

← Rev. 3 →

Sort any three elements, then let $$$x$$$ second element. $$$c=x\oplus\sum_aa\oplus x$$$

BledDest

4 года назад, скрыть # ^ |

I think this will find $$$b$$$, not $$$c$$$

← Rev. 2 →

Thanks for the answer, but I can't really accept it. First, sorting has $$$if$$$ in itself, and second, this approach finds b, and not c. After edit it finds c, but still sorting requires $$$if$$$.

Might be overkill, but zero if/else statements.

code

#include<bits/stdc++.h>

using namespace std;

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

    map<int, int> cnt;
    for(auto x : a) cnt[x]++;

    vector<pair<int, int>> aux;
    for(auto x : cnt) aux.push_back(make_pair(x.second, x.first));
    sort(aux.begin(), aux.end());
    cout << aux[0].second << endl;
}

I believe $$$sort$$$ has $$$if$$$ in it, as well as $$$map$$$.

I bet using while when it is supposed to be if isn't gonna cut it?

Yeah

Is !! also banned?

If not, then this is the solution

#include<bits/stdc++.h>

using namespace std;

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

    int full_xor = 0;
    for(int i = 0; i < n; i++)
        full_xor ^= a[i];

    long long b = 0;
    for(int i = 0; i < n; i++)
    {
        int pair_xor = (a[i] ^ a[(i + 1) % n]);
        b += a[i] * ((!!pair_xor) ^ 1);
    }

    b /= (n - 2);

    int ans = full_xor * (n % 2) + (full_xor ^ b) * ((n + 1) % 2);
    cout << ans << endl;    
}

+16

Simpler version without `!!`

#include<bits/stdc++.h>

using namespace std;

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

    int full_xor = 0;
    for(int i = 0; i < n; i++)
        full_xor ^= a[i];

    long long b = 0;
    for(int i = 0; i < n; i++)
    {
        int pair_xor = (a[i] ^ a[(i + 1) % n]);
        b += a[i] * (!pair_xor);
    }

    b /= (n - 2);

    int ans = full_xor * (n % 2) + (full_xor ^ b) * ((n + 1) % 2);
    cout << ans << endl;    
}

Thank you for your solution, this is what I've searched for.

ivatopuria

I'm pretty late but yeah.

Spoiler

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

int main(){
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int sxor=0;
	for(int i=0;i<n;i++){
		sxor^=a[i];
	}
	int sxor1=0;
	for(int i=1;i<n;i++){
		sxor1^=a[i];
	}
	bool t=a[0]^a[1];
	cout<<(n%2)*sxor+(t*a[0]+(!t)*sxor1)*(!(n%2))<<"\n";
}

Thank you, pretty tricky solution.

Ooops looks like my solution is wrong when $$$n$$$ is even and $$$a_1=c$$$, for example:

1 2 1 1

I guess it doesn't matter anymore, but here is corrected version:

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

int main(){
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int sxor=0;
	for(int i=0;i<n;i++){
		sxor^=a[i];
	}
	int sxor1=0;
	for(int i=1;i<n;i++){
		sxor1^=a[i];
	}
	bool t=a[0]^a[1];
	bool t1=a[1]^a[2];
	cout<<(n%2)*sxor+(t*((!t1)*a[0]+t1*a[1])+(!t)*sxor1)*(!(n%2))<<"\n";
}

heuristica

+44

Another solution:

TheOpChicken123

Very cool. I like this solution a lot. It is very simple to understand, even for me, and very slick as well.

Um_nik

+12

The problem is you can't really say if something is an if.

(flag ? x : y) is equivalent to x * flag + y * !flag, for example.

Блог пользователя fossil823656