Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Ayariyanam's blog

Inconsistent output for 2037 B. Intercepted Inputs
By Ayariyanam, history, 4 weeks ago, In English

There is an inconsistency in output in my system and codeforces environment. Following is my implementation. https://mirror.codeforces.com/contest/2037/submission/292083626 Test case 1: 2 1 4 5 3 3 my output in codeforces is shown as 2 2 but when I run it else anywhere (online and my machine) its giving 1 4.

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

    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };

    void solve(){
        int len;
        cin>>len;
        vector<int> v(len);
        for(auto& x: v) cin>>x;
        int target=len-2;
        unordered_map<int, int, custom_hash> umap;
        for(auto x: v){
            if (target%x!=0) continue;
            umap[x]++;
        }
        for (auto& it: umap){
            int num = it.first;
            int second=target/num;
            if ((second==num) && (it.second>1)){
                cout<<num<<" "<<num<<endl;
                return;
            }
            else if (umap.find(second) !=umap.end()){
                cout<<num<<" "<<second<<endl;
                return;
            }
        }
    }

    int main(){
      int testNum;
      cin >> testNum;

      while(testNum--){
        solve();
      }
    }

Can anyone help me understand what is going wrong here?

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

unordered map is... well... unordered

there can be more than one pair of solution and it'll output a random one

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But here I am checking count through unordered map. So for '2' in testcase count is 1 Hence 2,2 should not come and its not coming in my machine also.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is coming from else part IMO

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        That part should give same wrong output on all machines right? Is there any possibility of unordered map having memory mix up issue in codeforces in case of multiple test cases?

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          It is captured in previous comment unordered map is... well... unordered

          → Reply
          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks. Using ordered map has solved my problem. But I still have the doubt why unordered map is giving issue.

            → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I had the same problem using sets in python, I only change Pypy to Python compiler and got accepted, so weird lmao

Pypy WA: 291981466

Python 3.10 AC: 291983507

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I submits the exactly same code and passes: 292088616.

I also invocates the exactly same code for 10+ times and it also gives me correct answer.

I am confused now.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I HAVE WRITTEN THE CODE IN JAVA AND USED A DIFFERENT APPROACH BUT ITS GETTING WRONG ANSWER ANYONE COULD SUGGEST THE CHANGE NEEDED PLEASE...

//CODE

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class ii2 {
    
public static void main(String[] args) {
    Scanner sc= new Scanner(System.in);
    int a=sc.nextInt();
    
   
for(int t=0;t<a;t++){
    int n=0,m=0;
    HashMap<Integer,Integer> hm= new HashMap<>();
    int c=sc.nextInt();
    for(int i=0;i<c;i++){
        int cv=sc.nextInt();
        
        if(hm.containsKey(cv)){
            if(n==0&&m==0){
                n=cv;
                m=hm.get(cv);

            }
        }else{
            hm.put((c-2)/cv,cv);
        }

    }System.out.println(n+" "+m);
    
    
}

}
}

THIS GETS THE ANSWER 3 2 FOR LAST TEST OF EXAMPLE TEST CASE BUT IT WASNT ACCEPTED SO PLEASE SUGGEST THE CHANGES NEEDED

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    note that 3 2 CAN be accepted.

    The problem is you don't ensure $$$c-2$$$ is divisible by $$$cv$$$ when you hm.put((c-2)/cv,cv).

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We we know the inputs are integer so this won't be a problem according to me as we checks with integer in the hashmap

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Consider:

        5
2 1 3 5 5

        where your code gives $$$1\ 2$$$ that is obviously wrong.

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got it bro I need to change to float and then compare thanks for helping

          → Reply
»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Its behavior seems to be dependent on the value of FIXED_RANDOM. Check the output of this submission where it prints the answer for that case 100 times each with different FIXED_RANDOM: link

It's not very common to see 2 2 as the output, so you were probably unlucky to see that when you submitted it. I think the reason why this happens is explained by others.

→ Reply