Блог пользователя abhinavvv306

Автор abhinavvv306, 2 года назад, По-английски

We invite you to participate in CodeChef’s Starters 50, this Wednesday, 3rd August, rated for Div 2, 3 & 4 Coders.

Time: 8 PM — 11:00 PM IST

Joining us on the problem setting panel are: - Setters: Utkarsh Utkarsh.25dec Gupta, Abhinav abhinavvv306 Sharma, Shanu ShanuSingroha Singroha, Tejas tejas10p Pandey, TheScrasse TheScrasse, Ashish Kryptonix Gangwar, Pratik i.am.pratik Kumar

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Also, if you have some original and engaging problem ideas and are interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Hopefully no error 403 this time

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

The live rating graph is a very cool feature!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to do ADDSUBTRACT ?

The idea I used is basically:

  • First subtract the minimum positive number from the whole array,
  • Then, find the maximum number (let's say $$$x$$$) which is $$$\leq max(a_i) / 2$$$, then add it to the numbers which are $$$\leq x$$$.

In this way, the whole range of numbers in array will get halved each time I will do these $$$2$$$ operations, thus a total of $$$2 \log(\max(a_i))$$$ operations.

But, I don't know where I am wrong. It is failing test cases $$$12, 13, 18, 19$$$.

Submission.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    If it helps, this was the test case: link.

    Basically it contains only powers of 4.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Dang it, I thought I am halving the range each time, but this isn't true in this test case. Thanks a lot, man!

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      I have optimized my operations a bit, and it passes test cases 12, 13, 19. However, it is still failing test case 18, what could be that test case ?

      I feel that test case 18 is a bit large one, because it's runtime is maximum..

      Submission.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Here is the test case: link

        As far as I remember it contains many numbers <=1000 and very few numbers closer to 1e5 and nothing in between.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Beautiful Array?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Observation: You have to check only for $$$A[i]\pm 2$$$ where $$$0 \leq i \leq n-1$$$. (Actually in the contest I took the value to be $$$\pm 10$$$ without thinking too much, but I tried now with $$$\pm 2$$$ and it worked, not sure why)

    So you would need a $$$2\times 5$$$ $$$dp$$$ array, where: $$$dp[1][j]$$$ $$$\rightarrow$$$ when you add $$$(j-2)$$$ to $$$A[i]$$$, what is the minimum possible answer from all the previously calculated answers (i.e. values calculate for $$$A[i-1]$$$, and stored in $$$dp[0][k]$$$) and such that the condition $$$GCD(A[i-1]+k-2, A[i]+j-2)=1$$$.

    Link to submission (I've tried to add comments)