We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 19
  3. What Are the Odds?
  4. Discussions

What Are the Odds?

Sort by

recency

|

24 Discussions

|

  • redb17
     + 0 comments

    How this problem is solved by Binary Search ? Please Anyone. Thanks !

  • anonymous0169
     + 0 comments

    Please can anybody explain how cnt[x] can be computed in O(n)? Thanks

  • Dankan
     + 1 comment

    What are the constraints here?i am a newbie in competitive programming......I mean what are the rules of the games.i found the explanation a little unclear.Please help

    • anonymous0169
       + 0 comments

      Read about the nim game and its solution.You 'll understand most of it, else reply again.

  • iam_ss
     + 4 comments

    I solved it exactly in same manner as explained in editorial. However, I found the implementation (tester's) quite different (tough) than what was explained. However, I implemented it my way which I feel is relatively easier to understand. In case , anyone feels difficult in understanding the editorial's implementation of O(N) . Please refer the below code:

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

#define ll long long int

int main()
{
	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
	ll t=1;
	//s(t);
	while(t--){
		ll n;
		cin>>n;
		vector<ll>ar(n+2);
		for(ll i=1;i<=n;i++)cin>>ar[i];

		vector<ll>pref(n+2);
		pref[1]=ar[1];
		for(ll i=2;i<=n;i++)pref[i]=ar[i]^pref[i-1];

		unordered_map<ll,ll> cnt;

		ll suf=0;
		ll ans=0;
		cnt[0]=1;
		for(ll i=n;i>0;i--){
			ans+=cnt[pref[i-1]];
			suf^=ar[i];
			cnt[suf]++;
		}
		cout<<ans<<endl;

	}
}

    Thanks!

    • anonymous0169
       + 1 comment

      hey could please explain your last for loop? What is the logic you r following there?

      • iam_ss
         + 1 comment

        As we know, it is mandatory for alice to choose such a range [L,R] such that the xor of elements in range A[1...L-1] and A[R+1....N] are both equal.(Refer editorial for further reasoning).And we have to find all such possible pairs of [L,R]. In last for loop, we are moving from back to front and maintaning a variable suf which stores the xor of the suffix formed till now.And finally (as stated in the editorial) , for a given L, we are counting , how many R's exist to its right which has the same xor as A[1...L-1].For this, we are using map, which stores the count for every suffix. And we are simply adding it up for a given L. Hope it helps!

        • anonymous0169
           + 1 comment

          I did not get the editorial :( It would be of great help if u could plz explain how suf and cnt[] are working?

    • ImInba
       + 1 comment

      Could you please explain how cnt[0] is initialized to 1 ?

      • iam_ss
         + 0 comments

        cnt[0] is basically initialised as a base condition. Because just imagine for a given test case : 1 1 2 , for L=0, alice has to find how many suffixes exist to the right of L=0 which has the same XOR as prefix A[0...L-1] but since here L=0, there is no such prefix A[0...L-1]. It simply means that Alice will simply remove all the piles:) and hence Bob will have nothing to remove, hence he loses. So cnt[0] just deals with this situation. Hope it helps!

  • blockwood123
     + 2 comments

    If I unlock the editorial on this challenge, will it affect my overall score for the whole contest? I don't want to lose my points from my other solution.

    • JimNero009
       + 0 comments

      Also curious to know this!

    • iam_ss
       + 0 comments

      NO! You won't lose any points from any future contests. In case you solve it without editorial, you would get some points (generally +5) which contributes to your overall rating. But if you see the editorial, you won't get these extra points. That's all! Nothing to lose in future ;)

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in