gkapatia's blog

Newton's Coding Challenge December 2020 Invite
By gkapatia, history, 4 years ago, In English

Greetings,

Newton School cordially invites you to be a part of our monthly coding challenge. This month, the challenge is going to take place on eve of 23rd December, 2020 at 9PM IST. The duration of the contest is 150 minutes.

Please follow below link to register. Contest page: https://www.newtonschool.co/contest-home

Highlights of contest:
- The Prize Money is ₹20k and candidates can win exciting prizes and goodies
- Newton School goodies and Rs 100 gift vouchers to top 50 participants
- Rs 100 gift vouchers to 50 randomly selected participants between ranks 51-500
- Exclusive Newton School workshop for the top 500 participants
- We receive more than 10K registrations in our contest from all engineering colleges pan India

Registrations for contest is open till start of contest. *Note: Prizes are for Indian Participants only.

I hope you all will participate and enjoy the contest.

Regards, Newton School Team.

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

Comments Comments (33)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

whats a Rs

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain solution of 4th question.

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

    Just do some simple math and you'll get the following formula
    number of different ways = $$$\sum_{l=1}^{n-2}\sum_{b=1}^{m-2}\sum_{i=0}^{n-l}\sum_{j=0}^{m-b}i(n-i-l)j(m-j-b)$$$

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Bro but in the given constraints, computing this naively wasn't possible

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

        Yeah obviously, by doing some math you can reduce the problem to this:
        $$$S=\sum_{l=1}^{n-2}\sum_{b=1}^{m-2}\sum_{i=0}^{n-l}\sum_{j=0}^{m-b}ij(n-i-l)(m-j-b) $$$

        $$$S={\sum_{l=1}^{n-2}\frac{(n-l)(n-l-1)(n-l-2)}{6}}*{\sum_{b=1}^{m-2}\frac{(m-b)(m-b-1)(m-b-2)}{6}}$$$
        ans this can be easily computed in linear time

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

          Even the last sum can be calculated in $$$O(1)$$$

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

            Yeah you can optimize it even further, but for the sake of time I decided to go with this only as the linear time solution was fitting the time limit

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

      Could you please elaborate how you got to this?

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    if 4th problem is rectangle one then solution is

    C(x+1,4)*C(y+1,4)

    where C is Combination

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

      Hey bro, can you please elaborate how you directly came up with this?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +30 Vote: I do not like it

        given a x * y cell . you need 4 horizontal lines out of x+1 lines and 4 vertical lines out y+1 vertical lines. so that topping is surrounded by rectangular cake in every direction

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Wow, this idea is very elegant :o Thanks for sharing

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

          Wow, that's really pretty neat n elegant bro, great!!

          → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Can someone please share their solution idea for the 6th problem?

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

    Is it possible for you to share your ideas for the 5th problem?

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

      Yes bro, I used FFT to solve the 5th problem.

      See first create a sort of frequency array of size N to store the frequency of each remainder. Then assuming it to be a polynomial, square it using FFT. And now the question had a condition that X<=Y, but here we'll obtain all possible pairs, to to handle that, separately add the cases where X=Y and then divide the count by 2.

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

        Thanks a lot! it would be great if you can share your code from my submissions section :).

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

          Hey, sorry for late reply bro, here's my code:

          //Nightmare05
#include<bits/stdc++.h>

using namespace std;

#define sp << " " <<
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define int long long
#define double long double
#define INF (1e18+13)
//#define PI 3.1415926535898

int power(int p,int j)
{
    int res=1;
    p=p%mod;
    while(j>0)
    {
        if(j&1)
            res=(res*p)%mod;
        j=j>>1;
        p=(p*p)%mod;
    }
    return res;
}


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dice(int d,int p)
{
    uniform_int_distribution<int> uid(d,p);//specify l and s.
    return uid(rng) ;
}
/*
int read()
{
       int cc = getc(stdin);
       for (;cc < '0' || cc > '9';)  cc = getc(stdin);
       int ans = 0;
       for (;cc >= '0' && cc <= '9';)
       {
          ans = ans * 10 + cc - '0';
          cc = getc(stdin);
       }
      return ans;
}

inline void print(int n)
{
  if (n == 0)
  {
    putchar('0');
    putchar('\n');
  }
  else if (n == -1)
  {
    putchar('-');
    putchar('1');
    putchar('\n');
  }
  else
  {
    char buf[20];
    buf[19] = '\n';
    int i = 18;
    while (n)
    {
      buf[i--] = n % 10 + '0';
      n /= 10;
    }
    while (buf[i] != '\n')
      putchar(buf[++i]);
  }
}

int n;

vector<vector<int>> mat_mul(vector<vector<int>> a,vector<vector<int>> b)
{
    int n=2;
    vector<vector<int>> ans2(n,vector<int>(n,0));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int k=0;k<n;k++)
            {
                ans2[i][j]+=((a[i][k]*b[k][j])%mod);
                ans2[i][j]%=mod;
            }
        }
    }
    return ans2;
}

vector<vector<int>> pow_mat(vector<vector<int>> mat_a,int p)
{
    if(p==1)
        return mat_a;
    vector<vector<int>> temp=pow_mat(mat_a,p/2);
    vector<vector<int>> res=mat_mul(temp,temp);
    if(p&1)
        res=mat_mul(res,mat_a);
    return res;
}
*/

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
}

vector<int> multiply(vector<int> const& a, vector<int> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size())
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<int> result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("elimination_validation_input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    vector<int> a(n,0);
    for(int i=1;i<n;i++)
        a[(i*i)%n]++;
    vector<int> b=multiply(a,a);
    for(int i=n;i<b.size();i++)
        b[i%n]+=b[i];
    int dp=0;
    for(int i=0;i<n;i++)
    {
        dp+=a[i]*b[i];
        dp+=a[i]*a[(2*i)%n];
    }
    cout << dp/2;
    return 0;
}
          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you tell the exact problem(where you used FFT)?

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

          PROBLEM STATEMENT

          Screenshot-2020-12-24-172355 

          Sample Input 1
4
Sample Output 1
5
Explanation: required triplets are:
(1, 2, 1)
(1, 2, 3)
(2, 2, 2)
(2, 3, 1)
(2, 3, 3)
Sample Input 2
7
Sample Output 2
18

          PS: Sorry for these huge screenshots, I don't know why spoilers are not working

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

            Thanks, I also think it can be done with FFT only.

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

    Did you get how to solve the 6th problem or any thoughts on how to solve it?

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have problem statements for the 5th 6th problem, please share

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Can anyone share the code of 2-nd problem please.

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

    What was the second problem bro?

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

    PROBLEM STATEMENT

    Screenshot-2020-12-24-140355

    AC_CODE :

    #include<bits/stdc++.h>
using namespace std ;
signed main(){
  string s ;
  cin >> s  ;
  int mx = 0,n=s.size() ;
  vector<int>c(26) ;
  for(char x:s)
    c[x-'a']++,mx=max(mx,c[x-'a']) ;
  cout << (mx<=n/2?n:2*(n-mx)) ;
}

    P.S: Does anybody know why spoilers are not working?

    → Reply
»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Heyy this ain't fair!! Why can't we see the problems after the contest ends :(

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    If you've participated, only then you can see the problems

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      I did participate, still the problems are locked for me... Also it makes no sense...It was my first time participating and I couldn't see the previous contests problems then how am I supposed to figure out the problem difficulty n all...

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

        Just go to the "My submissions" Section and click edit, you'll be able to see the problems you attempted Screenshot-2020-12-24-180052 Screenshot-2020-12-24-180212

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I didn't say anything wrong, why downvotes then can someone clarify?

      → Reply