Блог пользователя sidhant

Автор sidhant, история, 7 лет назад, По-английски

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!!

  • Проголосовать: нравится
  • +48
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Gentle Reminder: Contest starts under 5 minutes !!

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 ??

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

    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")

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    • 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

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

How to solve MAGA?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

      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';
      	}
      }
      
    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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)?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I tried it but getting WA. Link

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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;
     
    	}
     
    } 
    
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hints for MAGA?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 :)

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve FINDA?

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Editorial for MAGA has still not been released.