Ashishgup's blog

By Ashishgup, 3 years ago, In English

Hello Codeforces,

I am happy to invite you to GeeksforGeeks's Pan-India Coding Contest – Code India Code. Showcase your coding skills and win rewards up to INR 7 Lakhs.

Contest Details are as follows:

Qualification Round: (Register Here)

  • Sunday, 6th March 2022, 12:00 AM (IST) to 7th March 2022,12:00 AM (IST)
  • In order to qualify in the first round, the participant needs to solve a minimum of 1 question out of 4 in 24 hours.

Final Round:

  • Thursday, 10 March 2022, 7:30 PM to 10:00 PM IST
  • Only those who qualify in the first round will receive a link to the final round.

Prizes:

  • Rank 1: Macbook Pro + Course voucher worth INR 12,000
  • Rank 2: iPad Air + Course voucher worth INR 7,000
  • Rank 3: Smart Watch + Course Voucher worth INR 3,000
  • Rank 4-25: Tablets + Course Voucher upto INR 1500
  • Rank 26-100: Noise Earbuds + Course Voucher upto INR 1500
  • Rank 101-200: Noise Smartbands + Course Voucher upto INR 1500
  • Prize distribution is limited to those residing in India only.

Problem Setting Panel:

Even though the prizes are only for Indians, I would like to invite others to participate — the problem-set (specially the finals) contains some interesting and challenging problems :D

Good luck everyone. See you on the leaderboard!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Cool prizes!

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

reply challenge on same day

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Will the qualification round results be considered in any way while deciding the rankings for the prizes?

»
3 years ago, # |
  Vote: I like it +104 Vote: I do not like it

Top performers will be given course vouchers, but logically thinking, do the top performers need those courses???

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

    Right. I think they should provide the course voucher to those who perform average in the contest. So that they can enhance their skill with their expertise.

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Is using prewritten code allowed? The rules don't seem to address this.

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

Really Excited to participate.

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

are the prizes be for Indians in top-X, or top-X Indian contestants in a separate Indian ranklist?

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Is testcase of "MINIMUM MOVES" is wrong?

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

will we enter the ranklist only after clicking on finish test? Edit :No

»
3 years ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

Mass cheating is going on!

A youtube channel is revealing the solution for problem A and problem B.

Please ban the youtube channel as soon as possible :(:(:(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Please remove the links.

    you could have told this in private to any of the organisers.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can anybody share the solution of the last 3 problems.

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Don't know if it's intended or not but I solved Problem D(Special Number Count) with Digit Dp.

My dp solution has $$$13$$$ states which are as follows:

pos [0,19] -> position from left we are at
small[0,1] -> are we smaller than the input number or equal to it till the i position
start[0,1] -> have we started building the number
zero[0,1] -> is the product of digits equal to 0
sumg[0,2] -> is the sum of all quartic power of digits greater than 1 (helpful in handling cases like 1000) 
two[0,1] -> does the prime factorization of product of digit have 2 as a prime factor
three[0,1] -> does the prime factorization of product of digit have 3 as a prime factor
five[0,1] -> does the prime factorization of product of digit have 5 as a prime factor
seven[0,1] -> does the prime factorization of product of digit have 7 as a prime factor
mod2[0,1] ->  the mod of the sum of the quartic power of digits with 2
mod3[0,2] ->  the mod of the sum of the quartic power of digits with 3
mod5[0,4] ->  the mod of the sum of the quartic power of digits with 5
mod7[0,6] ->  the mod of the sum of the quartic power of digits with 7

In all the memory declaration for my dp looked like this

ll dp[20][2][2][2][2][2][2][3][5][7][2][3][2];

The recursive function looked like this

ll recursion(int pos,int small,int two,int three,int five,int seven,int mod2,int mod3,int mod5,int mod7, int zero , int sumg1 ,int start ,string &curr)

Each recursive call was somewhat like this

val+=recursion(pos+1,0,n2,n3,n5,n7,(mod2+k)%2,(mod3+k)%3,(mod5+k)%5,(mod7+k)%7,n0,nsumg1,0,curr);

My somewhat okayish implementation

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Heartfelt sincere orz!! 13 state DP

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

    I did the same basically, but you don't really need $$$13$$$ states. You can compress quartic sum modulo each prime into a single value upto $$$210$$$ ( using custom radix base $$$\{2,3,5,7\}$$$ ). Also, similarly you can compress whether product contains $$$2/3/5/7$$$ into a 4 digit bitmask.

    So my dp looked like dp[20][210][1<<4][2][2][2]

»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Downvoted for having the problem A in the contest

»
3 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Can anybody share the solution to the first problem :)). Tried everything.

  • »
    »
    3 years ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    It's similar to this Problem. The only difference I found is that you don't need more than 3 operations to convert A into B.

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

      But the solution is entirely different, and also here update operation is A = A | X where X could be any number >= 0

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

    Basically, if B <= A, we need to do |B-A| moves, as we can only increase B by 1. Otherwise, it is not difficult to see that we can always do it in at most 3 moves, as we will take the highest bit (say i) that they differ at, and in 1 move set all the bits in A smaller than i (by or-ing) and then increment A by 1, and then or the remaining bits smaller than i to make A and B equal. Now that we know the answer is always <= min(B-A, 3), we only need to check for answers 1 and 2. This is easy, as we only need to check for 4 cases, (A|X) = B, ((A+1)|X) = B, (A|X) = B+1, (A|X)+1 = B. For the last case, just reduce B by 1 and check.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      void solve(){
          int a, b;
          cin >> a >> b;
          if(b <= a){
              printf("%d\n", (a-b));
              return;
          }
          if((a|b) == b || a + 1 == b){
              printf("1\n");
              return;
          }
          bool i1 = ((a+1)|b) == (b);
          bool i2 = (a|(b+1)) == (b+1);
          
          if(i1 || i2 || (a + 2 == b)){
              printf("2\n");
              return;
          }
          printf("3\n");
      }
      

      Hey, this implementation handles all the cases you described. Why its giving WA?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think you have handled the last case, (A|X) + 1 = B

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

          Thanks got it.

          This case just took my entire SUNDAY.

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

    If B > A

    Somehow the main ambition is to make A a sub mask of B. Now, if A is already a sub mask of B, we can make them the same in only one operation!

    let i be the most significant bit where A and B are not the same

    update A = A | (2 ^ i - 1)

    for example A = 10101 and B = 11010, we update A = A | 7, now A becomes 10111

    update A = A + 1

    Now A becomes the sub mask of B for sure, and you will need only one operation to make both equal!

    So, at most, three operations are required to make A and B equal.

    We have to handle cases where only one or two operations are sufficient.

»
3 years ago, # |
  Vote: I like it +207 Vote: I do not like it

Am I the only one that is always bothered by statements like "win rewards up to INR 7 Lakhs"? Because it is not actually possible to win 7 lakh; the best you can do is a MacBook (which I can't imagine costing 7 lakh). 7 lakh appears to be the total value of the rewards; in addition, none of it is actually in the form of money, which is even more false advertising. Also, about 2 lakh comes from GFG course vouchers, which I suspect aren't really worth anything.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    Also, about 2 lakh comes from GFG course vouchers, which I suspect aren't really worth anything.

    Destroyed in seconds

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    GFG course vouchers are not only limited to programming/dsa courses, you can take any( OS, DBMS, etc.) course.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah you are correct it is rather a way of advertising it to suit their needs for greater participation

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve problem — The Duality Task?

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

    You can find duality by considering a common prime number for each element in a subsequence. Now, just take initial C as B and find its duality. ans = n — max(0, duality_A — duality_B)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B — “Split the Array”? I had nothing better than an $$$N^2$$$ DP…

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    It involved a bit of casework.

    Think along the lines of what will happen if k is odd/even and j is odd/even.

    The problem then reduced to a dp with $$$4$$$ states per element.

  • »
    »
    3 years ago, # ^ |
    Rev. 5   Vote: I like it +10 Vote: I do not like it

    That $$$O(n^2)$$$ is enough just to ensure that you don't create a segment of length more than 20. So it will become $$$O(20*N)$$$

    You can work on paper to see that if a segment has a length of more than 10 then you can split the first/last 4 elements into 2 segments of length 2 and it won't change signs. These 10/20 are the loose upper bounds, I didn't try finding exact values.

    Upd: Idk the reason for these downvotes, but it's correct. I have 100 points (and 6th rank) on the scoreboard using this solution and I'm confident about its correctness as well. See you all in Finals now.

    Code
»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Is there any way , to get notify on new blog in recent actions in Codeforces.

:(, feeling very bad not able to participate , I did not know about contest .

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Has anyone received any mail saying "Congratulations..etc and asking for details for sending the prize"?

It's been more than 3 days and not a single mail from gfg after the contest. Ashishgup any clue?

»
3 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Any updates on prize distribution Ashishgup,Omja?

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Will the contestants above rank 200 be included under 200 after removing overseas particpants.

Ashishgup