Ayariyanam's blog

Inconsistent output for 2037 B. Intercepted Inputs
By Ayariyanam, history, 5 hours ago, In English

There is an inconsistency in output in my system and codeforces environment. Following is my implementation. https://codeforces.me/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
  • -1
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it 0 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
  • »
    »
    5 hours 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
    • »
      »
      »
      5 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is coming from else part IMO

      → Reply
      • »
        »
        »
        »
        5 hours ago, # ^ |
          Vote: I like it 0 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
        • »
          »
          »
          »
          »
          5 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            4 hours 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 hours 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 hours 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 hours 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
  • »
    »
    2 hours 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