Balajiganapathi's blog

By Balajiganapathi, history, 2 months ago, In English,

We are going through an unprecedented situation currently. There are lockdowns and quarantines in many parts of the world. We feel the best way to cope with everything that is going on is to keep ourselves occupied.

To help with that, we at CodeDrills have something for all the competitive coders out there. On 25th March, we launched our own online judge and also launched the CodeDrills covid 21 days challenge. Every day, for the 21 days starting from 25th March, we will upload 1 problem. Just visit codedrills.io, login and start solving! The launch coincided with the start of a full lockdown in India.

Since the situation was unexpected, we rushed to put up the site as soon as possible, so there might be issues. If you find any bugs or want to request a feature, please write to us at hello@codedrills.io with as much details as possible.

Here is our mascot Ufu wearing a mask (if you are unable to see him here, head over to our page):

Here are the problems launched so far:

Day Problem link
1 Beating Shell sort
2 Curfew delivery
3 Book stacks
4 Square-free subarrays
5 Cookie supply
6 Count of arrays with given LIS length
7 Longest balanced symmetric subsequence
8 String with palindromic substrings
9 Can the spider jump
10 Road decorations
11 Each edge MST
12 Sufficiently different strings
13 Minimum meeting rooms
14 Harshad number
15 Sufficiently different vectors
16 Friends meeting
17 Seats and students
18 Subsegment xor sum
19 Count of palindromic strings
20 Max xor pair subarray queries
21 Repeated string compression

PS: The old code-drills site is still available at https://recommender.codedrills.io

PPS: We don't have all the 21 problems yet, if you have a problem idea please contact us

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

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

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

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Why a new platform instead of using an existing one? You could conveniently prepare problems in Polygon and publish them in CF GYM.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    We are planning much more than algorithm problems (e.g. AI/ML, cloud etc.). So we felt it was better to build our own platform from scratch. It will not be exclusively for competitive coding.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Why the only allowed language is C++ ?

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

    Since we launched in a hurry, we could not add more languages. We will add Python support soon.

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

Have you just marketed another platform on coderforces?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Not exactly marketing. We shared something we thought a lot of competitive coders would be interested in and codeforces is the best places to share it — just like there are posts of contests on Hackerearth, Atcoder, Topcoder etc. :)

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I'm getting WA on every task I try except for "Apples and Bananas" (the a+b task). Are you sure they are correct? I tried every task except for "Beating Shell sort" and "Book stacks".

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

    Hi, I took a look at your solutions. Here are my observations:

    For Square-free subarrays, the idea seems wrong (though the direction of idea is correct). You have to consider indices of other numbers in the array with divisors matching the current number.

    For Curfew delivery, the idea seems correct but the implementation has some bugs (e.g. The starting node can have curfew, curfew start time is inclusive etc.)

    For Cookie supply, I did not understand the approach

    For count of arrays with LIS, the direction of solution is correct but details seem wrong.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it +9 Vote: I do not like it

      For Square-free subarrays, I used a two pointer solution (keeping the biggest interval that is currently valid). I'm sorry if I'm misunderstanding your idea, but it's not enough to only consider indices of other numbers in the array with divisors matching the current number.

      For the following case: 4 5

      When we consider the 5, we can only take 5 in the answer (one subarray ending at 5). Since 5*4 is divisible by 4. But if you only consider numbers with the same divisors as 5, you would not consider the 4, which is wrong.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Correct. I did catch that in my solution but missed cases like this:

        2, 2, 5 (i.e. the divisors were split across elements).

        I have fixed the test cases. Please try submitting again now. It should pass.

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

          It works now. Nice!

          Btw. in "Curfew delivery" I think I handled both of the things you said. But there is a good chance I missed something else. I also fixed my bug in LIS (I was returning int instead of long long).

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve Count of arrays with given LIS length?? Can you drop some hint??

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Read about the efficient algorithm to solve LIS and notice that we can calculate if we somehow maintain the M array from the algorithm. Due to a property of the M array and the small constraints this should be possible.

    I have intentionally kept the hint vague so as not to spoil the full solution. Let me know if you need a more detailed hint.

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Should tasks be original for 21 days challenge?
I can share some of my favourite cf problems.

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

    Since this is unplanned and sudden, it is okay if you take an existing idea and create your own problem. However, it should not be an exact copy of an already existing problem.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Will an editorial be published for the problems after 21 days?

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

    We do not have plans for releasing editorials. Since this is not really a contest, feel free to ask for hints or discuss approaches here.

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

A feature request: Please add time limit too for every problem.

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

    Done! Added time limit and memory limit after the statement. Submission History is also available now.

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

      It shows only first 10 submissions for a problem, and my solution was AC after like 20-25 submissions later. I do not have access to my AC solution. Can you something about it?

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

For problem Beating Shell sort, I'm pretty sure the problem is not correct. I got AC on the problem, but the statement is not correct. The real text of the problem should be:

Find the number of integers in range from 0 to 4999 that can not be represented as a combination of the given gaps. So like if we had gaps g1,g2 and g3, we need to count the number of integers that can not be written in form a*g1+b*g2+c*g3 where a,b and c are natural numbers including 0.

For the current statement, the second test case is not correct. Look at the number 12, sure it can be written as 3*4, but the shell sorting algorithm will move it from position 12 to position 2 when it goes with gap 10, and it will stay on position 2 (The array will not be sorted). The actual answer for test case 2 with the current statement should be 3452.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I was reading about Shell sort and saw the theorem that if an array is g1 and g2-sorted then it will be a*g1 + b*g2 sorted. From there I mistakenly thought it implied the first version of the problem (i.e. not represented as a combination of given gaps).

    Thanks a lot for the explanation, I understood how it is not the case. I have now changed the samples and tests to match the second version (i.e. not changed the statement, but changed the tests). Have verified it locally with brute-force. Please check now.

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

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

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

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

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

How to solve B ?

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

How to solve A ?

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

Any hint for Max xor pair subarray queries and solution of Count of arrays with given LIS length if possible?