KiZamaDo17's blog

Java Solution of D- Divisible Pairs CF Round 925
By KiZamaDo17, history, 9 months ago, In English

I attempted the D problem in JAVA 21 64bit with the simple logic of storing the remainder of a[i] in pairs along with their frequency in HashMap and check if (x-(a[i]%x)),(a[i]%y)) is already present, adding 1 to answer if it happens. I also make the remainder equal to x if it comes out to be zero.

Heres my solution

My Answer

but for some reason it fails the 12th test. I don't know what on God's Earth it is, but I then just convert the same logic to C++ and its accepted.

Where am I going wrong? What seems to be the problem here? Is there an alternative? A friend of mine suggested using a 2D array instead of a map an hence saving the trouble of creating pair class in JAVA but I could not fully grasp his concept. Please help me out here.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know much about Java but it looks like your "pair" implementation such return a 64-bit integer since to hash it in a * M + b then M should be greater than b.

In addition, the answer may get larger than 32-bit integers so consider using 64-bit integers in this case.

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

    Hey thank you for your reply. I am already using long data type. It's a 64 bit integer data type. For your hashing suggestion, let me try it real quick.

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

    I implemented all your suggestions and this is what is happening. When I use M in hashing function anything less than 64, it gives me a wrong asnwer at test case 12

    Using M=63 here

    and when I use M=64, it gives me a TLE at M=64 at test case 4

    When M is 64

    What to do now? Vladosiya any clues you can give mate?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Line 16: int ans = 0 ;

      it should be long ans = 0;

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        If that would actually be my only fault I swear to god I should quit. I will check it once CF allows me to. PS:- I saw your solution man. You actually just used a string instead of a pair. Why can't I think like you? That was so clever. Thank you for the help.

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

        I just realized the maximum no. Of pairs can be n(n-1)/2 and not n/2 which I was previously thinking so this just might be it.

        → Reply