abhinavvv306's blog

Invitation to CodeChef July Starters 50 (Rated for Div 2, 3 & 4) — 3rd August
By abhinavvv306, 22 months ago, In English

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!

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

Comments Comments (9)
| Write comment?
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Hopefully no error 403 this time

→ Reply
»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

The live rating graph is a very cool feature!

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

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.

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

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

    Basically it contains only powers of 4.

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

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

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

      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.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

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

How to solve Beautiful Array?

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

    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)

    → Reply