[Invitation, Prizes!] CodeRed and Humblefool Cup 2024 by IIIT Allahabad

»

itzzRaghav

3 года назад, скрыть # |

0

pvtr excited.

→ Ответить

»

Abhishek_Srivastava

3 года назад, скрыть # |

+9

Humblefool orz!

→ Ответить

»

JagguBandar

3 года назад, скрыть # |

+17

As Starters 122 tester, I bet problems will be fun.

→ Ответить

»

25-din-me-rating-double

3 года назад, скрыть # |

0

approach for B ?

→ Ответить

»

smit_384

3 года назад, скрыть # ^ |

0

dp with 3 states index, winner and loser

→ Ответить

»

kaisirius

3 года назад, скрыть # |

0

Can anyone tell the solution of I problem. My approach:- If number of indices where a[i]>a[i+1] is greater than equal to 3 then it should be NO and for 1,2 I am just choosing two indices greedily and brute forcing whether my array will be sorted or not but wrong on test2. If count of such indices is 2 then my operation will be on those indices and I am checking for all the combinations in those 4 indices (i,i+1,j,j+1 where a[i]>a[i+1] and a[j]>a[j+1]). Somewhat similar I am doing when count equal to 1 either i will be choosing min(x,y) or max(x,y) for that (i,i+1).

→ Ответить

»

Fremder

3 года назад, скрыть # ^ |

0

Failed Testcase

1
5 1 3
1 2 3 5 4

The intended solution is, you can fix at most two "bad" indices. An index $$$i$$$ is bad if $$$i \leq i + 1$$$, now try to make cases for the indices and check if the array can be sorted.

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define debug(x) cout << #x << ' ' << x << endl;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define exe(k,n) for(int i=k;i<n;i++)
#define exec(n) for(int i=0;i<n;i++)
#define endl '\n'
#define ss second
#define ff first
#define pb push_back
#define hii cout << "Hi\n";
#define int long long int
const int inf = 1e18;
const int N = 2*1e5+10;
bool is_sorted(vector<int> &v)
{
    for(int i=0;i<(int)v.size() -1;i++)
    {
        if(v[i]>v[i+1])return false;
    }
    return true;
}
signed main() 
{   fastio();       
    int T=1;
    cin >>T;
    while(T--)
    {   
        int n,x,y;
        cin >> n >> x >> y;
        vector<int> v(n);
        exec(n) cin >> v[i];
        int flag=1;
        vector<int> ind;
        for(int i=0;i<n-1;i++)
        {
            if(v[i]>v[i+1])
            {
                flag=0;
                ind.pb(i);
            }
        }
        if(x>y)swap(x,y);
        if(x<=y)
        {
            if(ind.size()==1)
            {
                int a=ind.back();
                if(a)
                {
                    swap(v[a],y);
                    if(is_sorted(v))flag=1;
                    swap(v[a],y);
                }
                swap(v[a],x);
                if(is_sorted(v))flag=1;
                swap(v[a],x);
                if(a<n-1)
                {
                    swap(v[a+1],x);
                    if(is_sorted(v))flag=1;
                    swap(v[a+1],x);
                }
                swap(v[a+1],y);
                if(is_sorted(v))flag=1;
                swap(v[a+1],y);
                //5 2 2 
                //1 2 3 5 4
                if(a)
                {
                    swap(v[a-1],x);
                    swap(v[a],y);
                    if(is_sorted(v))flag=1;
                    swap(v[a-1],x);
                    swap(v[a],y);
                }
                //5 4 4
                //1 2 4 5 3
                if(a<n-1)
                {
                    swap(v[a],x);
                    swap(v[a+1],y);
                    if(is_sorted(v))flag=1;
                    swap(v[a],x);
                    swap(v[a+1],y);
                }
                //5 5 5
                //1 2 5 3 4
                //1 2 5 4 3 
                if(a<n-2)
                {
                    swap(v[a+1],x);
                    swap(v[a+2],y);
                    if(is_sorted(v))flag=1;
                    swap(v[a+1],x);
                    swap(v[a+2],y);                    
                }
            }
            else if(ind.size()==2)
            {
                int a=ind[0];
                int b=ind[1];
                vector<int>temp[4];
                exec(4)temp[i]=v;
                temp[0][a]=x;
                temp[0][b]=y;
                temp[1][a+1]=x;
                temp[1][b]=y;
                temp[2][a]=x;
                temp[2][b+1]=y;
                temp[3][a+1]=x;
                temp[3][b+1]=y;
                exec(4)
                {
                    if(is_sorted(temp[i]))flag=1;
                }
            }
        }
        if(flag) cout << "Yes";
        else cout << "No";
        cout << endl;
    }   

 return 0;   
}

Also we found out in the contest that there are many easier dp solution as well, take states as index and status of the operation applied

→ Ответить