kalzor's blog

By kalzor, history, 4 weeks ago, In English

As the title says I need some help to find some test cases where my solution fails for the problem Cubes Sorting. My logic is simple, I first sort the array in decreasing order, then check if two elements are the same in the array. Then i check if the original array is in strictly decreasing order. If either the original array is not sorted in decreasing order or if there are two(or more) elements with the same value I print out YES else No. My Java Code:-

Spoiler

The logic seems right to me but it is still giving WA.Link to WA Submission 93757010. Any help is appreciated.

Update: Seems like the same code in C++ gives AC 93846515. Is there some error in my implementation of the solution?

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

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

I don't think you need to check the isSame boolean value.Just check if the array is strictly reverse sorted or not.

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

    But consider these two test cases :- 3, 2, 2 & 3, 2, 1.The first one will require two swaps but the second one will require three swaps. The first one can be sorted but the second one cannot be sorted so the output should be "YES" for first one and "NO" for second one.

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

Yes,So that's why all you need to check is the array is reverse sorted or not. Here is some kind of proof:-

1).the maximum number of swaps required would be if the array is reverse sorted i.e. summation of first n-1 numbers which is ((n-1)(n))/2 using formula for summation of natural numbers.The maximum number of swaps allowed are (((n-1)(n))/2)-1. This is just(previous formula-1).So only for that case we cannot do it.else always we can do it within the number of swaps allowed

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

    Yes, sorted ArrayList contains the array sorted in reverse order.So i check if array has any duplicates and then check if the array is sorted in reverse order.Also when I removed the part which checks for duplicates(isSame boolean variable) my solution fails on sample test case 2 where the array is 2,2,2,2. Am I misinterpreting something?

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

      Your solution is passing the sample tests(I checked on custom invocation) It is some other case which it is not passing

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

        My logic seems to be correct as the same solution gets AC in C++

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

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

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

If you write your code in IntelliJ Idea, it shows a warning about objects comparisons. Don't ignore warnings. Idea is smarter than you. Make sure you have a green icon in the top-right corner of the editor before submit.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I figured out the problem.I was trying to check for equality on Integers(Object) using == which checks if both the variables refer to same object .I used equals which compares the actual values of Integers and it solved the problem or casting to int works too. Thanks have a nice day. Now I am wondering how did it work on test cases on my local machine.

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

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