sidhant's blog

By sidhant, history, 6 years ago, In English

After the recently concluded January Long Challenge, I would like to invite you for some more interesting challenges to keep your coding schedule always packed!

Participate in the January Cook-Off 2018 and enjoy Chef’s tricky tests. Joining me on the panel are:

  • Problem Setter and Editorialist: sidhant (Sidhant Bansal), arjunarul (Arjun Arul)

  • Problem Tester and Admin: kingofnumbers (Hasan Jaddouh), mgch (Misha Chorniy)

  • Russian Translator: CherryTree (Sergey Kulik)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Vietnamese Translator: VNOI Team

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 21st January 2018 (2130 hrs — 0000 hrs Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: https://www.codechef.com/COOK90

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes:

  • Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])

According to me, the problems are very interesting and I am sure that you will have fun while solving these problems :)

Good Luck! Hope to see you participating!!

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +64 Vote: I do not like it

PS — In this cook off, we have changed the penalty from 20 minutes to 10 minutes. Enjoy!!

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

Gentle Reminder: Contest starts under 5 minutes !!

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

I just loved your problems! Hope you set more contests in the future! :D

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

How to solve far graphs when there are odd cycles. Also will the vertices always get -L/2,0,L/2 even in odd cycled graphs ??

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

    There is at most one cycle of length 3. After removing them and all edges which have an end point in that cycle, the resulting graph is bipartite. (Assume answer is "Yes")

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    • For now don't consider the equality in the condition |ai — aj| >= L/2. That is for now, there is edge if and only of |ai-aj| > L/2
    • Partition the nodes with values in [0, L/2] and [L/2+1, L]. Since the maximum difference achievable in each partition is at-most L/2. There can not be any edge.
    • This is means the graph is bipartite, with the above partition. With a special property that I will describe below. Also, if we have any bipartite graph with that property, we can always assign values in such a way that the above holds.
    • Now let's consider the equality -
    • Partition the graph as before. But we can have a edge between the first node and last node in the first partition — if sorted according to values. If there is then. Also in that case value of first node will be 0 and the last will be L/2.
    • Also, we can have at most one outgoing edge from the last node in first partition. This means last node of first partition must be a part of some simple odd-length cycle of the original graph and has degree 2.
    • So to solve this problem, we need to detect that special node. And then verify the special property that I mentioned above. And assign values greedily.
    • special property is nothing but if there is edge from a node to u and to v then there is edge from that node to every node u <= x <= v. If we consider the nodes according to sorted values.

    Disclaimer : I have coded this up but could not get accepted. Submission

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

How to solve MAGA?

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

    Simple dp, with extreme amount of case handling. Consider cases where the size of the array is even/ odd, the current index in dp you are at is even/odd and wether you performed swap in the previous step or not.

    States will be dp[last][idx], last indicating wether swap was performed for last index, and idx needs to move only until mid of the array.

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

      Yeah same here. My code exceeded 200 lines. I was wondering how people solved so fast.

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

      You just need to write a neat code :) Here's mine:

      #include <bits/stdc++.h>
      using namespace std;
      int A[100009];
      int D1[100009];
      int D2[100009];
      bool ok(int i)
      {
      	if (i % 2 == 1)
      		return A[i] < A[i + 1];
      	else
      		return A[i] > A[i + 1];
      }
      int N;
      int ans()
      {
      	int i = (N + 1) / 2;
      	int j = (N + 2) / 2;
      	int id = 0;
      	D1[id] = N + 2;
      	D2[id] = N + 2;
      	if (i == j)
      	{
      		D1[id] = 0;
      		D2[id] = 0;
      	}
      	else
      	{
      		if (ok(i))
      			D1[id] = 0;
      		swap(A[i], A[j]);
      		if (ok(i))
      			D2[id] = 1;
      		swap(A[i], A[j]);
      	}
      	while (true)
      	{
      		i--;
      		j++;
      		if (i < 1)
      			break;
      		id++;
      		D1[id] = N + 2;
      		D2[id] = N + 2;
      		{
      			if (ok(i) && ok(j - 1))
      				D1[id] = min(D1[id], D1[id - 1]);
      			swap(A[i + 1], A[j - 1]);
      			if (ok(i) && ok(j - 1))
      				D1[id] = min(D1[id], D2[id - 1]);
      			swap(A[i + 1], A[j - 1]);
      		}
      		swap(A[i], A[j]);
      		{
      			if (ok(i) && ok(j - 1))
      				D2[id] = min(D2[id], 1 + D1[id - 1]);
      			swap(A[i + 1], A[j - 1]);
      			if (ok(i) && ok(j - 1))
      				D2[id] = min(D2[id], 1 + D2[id - 1]);
      			swap(A[i + 1], A[j - 1]);
      		}
      		swap(A[i], A[j]);
      	}
      	return min(D1[id], D2[id]);
      }
      int main()
      {
      	int T;
      	cin >> T;
      	while (T--)
      	{
      		cin >> N;
      		for (int i = 1; i <= N; i++)
      			cin >> A[i];
      		int out = N + 2;
      		out = min(out, ans());
      		for (int i = 1; i <= N; i++)
      			A[i] *= -1;
      		out = min(out, ans());
      		if (out > N)
      			out = -1;
      		cout << out << '\n';
      	}
      }
      
    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I did something similar. got WA . I don't know why. Here's my code

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

For Problem B, "Multiple of 3", can it be solved using CRT?

It is possible to solve because gcd(10,3)=1.

I calculated 2 values, one for mod 10(a1) and other for mod 3(a2), eqn was n=(d0+d1)+(d0+d1)*(2^(k-2)-1).

Combined them using this eqn from wikipedia, n3=a1m2n2+a2m1n1 where n1=10, n2=3 and m1=1,m2=-3 which is derived from extended euclid gcd.

Now I just checked n3%3 and printed, but this gave a WA. Can someone please help me(show me de way)?

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

    You can calculate n3 mod 30 then check (n3 mod 30) mod 3 == 0

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

      I tried it but getting WA. Link

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

        Sorry, this idea is wrong. the correct one is notice that digit[i] = digit[i-4] for all i except first few ones.

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

          Can you please tell me why this idea won't work?

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

            because ( digit[0] % 10 + digit[1] % 10 + digit[2] % 10 ... ) % 3 is not equal to ( (digit[0] + digit[1] + digit[2] ...) % 10 ) % 3

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

              Okay! Got it, thanks!

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

          We can go further than this. I noticed that the repeating digits are always on the lines "2,4,8 6". The only corner case is when d0+d1=5, for which only 0 is appended always.

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

    first calculate (d0+d1)%10 and then divide into group of 4s . the pattern will repeat like ; 2,4,8,6 and lastly add those. for ex. d3 = 2*(d0+d1)%10 , d4 = 4*(d0+d1)%10 , d5 = 8*(d0+d1)%10, d6 = 6*(d0+d1)%10 , like this the pattern will repeat for K/4 groups , you have to add the remaining . here is the code:

    #include <bits/stdc++.h>
    using namespace std;
     
     
    #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
    #define pb push_back
    #define MP make_pair
    #define F first
    #define S second
    #define min(a,b) (((a)<(b))?(a):(b))
    #define max(a,b) (((a)>(b))?(a):(b))
    #define PII pair<ll,ll> 
     
     
     
    typedef long long ll;
    ll x;
     
    ll MOD = 1e9+7;
    #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
    using namespace std;
    typedef long long ll;
     
    ll modexp(ll a, ll b, ll mod){
    	ll res = 1;
    	while(b){
    		if(b&1)	res = (res*a)%mod;
    		b = b>>1;
    		a = (a*a)%mod;
    	}
    	return res;
    }
     
    int main(){
    	boost;
    	ll T,N,i,j,k,L,l,m,n,R;
    	ll K;
    	cin >> T;
    	ll S;
    	ll d0,d1;
    	while(T--){
    		cin >> K >> d0 >> d1;
    		ll sum = (d0+d1)%3;
    		ll s2 = 0;
    		if(K == 2){
    			if(sum%3 == 0)	cout << "YES" << endl;
    			else	 cout << "NO" << endl;
    			continue;
    		}
    		K -= 2;
    		K -= 1;
    		s2 += (d0+d1)%10;
    		//for(i = 0 ; i < K/4 ; i++){
    		s2 += K/4 * ((2*(d0+d1))%10+(4*(d0+d1))%10+(8*(d0+d1))%10+(6*(d0+d1))%10);
    		//}
    		K %= 4;
    		if(K){
    			s2 += (2*(d0+d1))%10;
    			K--;
    		}
    		if(K){
    			s2 += (4*(d0+d1))%10;
    			K--;
    		}
    		if(K){
    			s2 += (8*(d0+d1))%10;
    			K--;
    		}
    		if(K){
    			s2 += (6*(d0+d1))%10;
    			K--;
    		}
     
    		//s2 %= 10;
    		s2 %= 3;
    		if((sum+s2)%3 == 0)	cout << "YES" << endl;
    		else	cout << "NO" << endl;
     
    	}
     
    } 
    
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks sir, I implemented this during contest but pretty late because my first approach gave a WA.

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

Hints for MAGA?

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

    It's a straightforward DP problem :D DP1[i]=min swaps if not swapping [i, n-i+1] in interval [i, n-i+1] DP2[i]=min swaps if swapping [i, n-i+1] in interval [i, n-i+1] You can be a little clever and just count the numbers if a1>a2<a3... and then multiply every number by -1 and do it one more time :)

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

      Can you elaborate a bit more on the dp states?

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

      okk got it just to check for the other case ??

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

        Yeah :D It doesn't make sense to code the same thing again :D

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

How to solve FINDA?

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

Editorial for MAGA has still not been released.