Thanks for the fast editorial.

Why was there a test case with K=0 in problem Yet Another GCD Problem? The constraint mentioned in the problem states that 1<=K<=1e9

umm , we came 2nd in our college and in top 100 overall, the first place team from our college had chosen amritapuri and one more region and we had only chosen amritapuri , so is there much chance of us getting selected or no? ;-;

How can we run backtrack for n=3000??

What is the proof for Small Indices problem that the proposed backtracking solution works in O(n^2). Also could you share the dynamic programming solution of the same?

Update:

The proof is as follows:

b[i] > level (b[i] > sum of 2 previous max numbers) can only occur about O(logn) times.

So at O(logn) times we have 2 choices to explore and hence works in the given time complexity

In small indices, if the array size is n then elements of array are <= 2*n and not <= 6000. right? Arpa Enigma27

So, solutions were tested against inputs which clearly defy given constraints in the absence of which many would've AC'd for Yet Another GCD (not to mention many teams saving enough time to attempt at least one more problem), and GPT written brute forces would pass Small Indices? And somehow both things flew under the radar during testing? That too in ICPC prelims, one chance a year for students which they've paid good money for? Must say, stellar work.

Can anyone identify where my code for unsatisfied array goes wrong?

ll n, k;
    cin >> n >> k;
    vector<ll> a(n + 1, 0);
    vector<set<ll>> bound(n + 1);
    for (ll i = 0; i < k; i++) {
        ll x, y, m;
        cin >> x >> y >> m;
        if (x < 1 || y > n || x > y || m < 1 || m > n) {
            cout << -1 << '\n';
            return;
        }
        for (ll j = x; j <= y; j++) {
            bound[j].insert(m);
        }
    }
    for (ll i = 1; i <= n; i++) {
        if ((ll)bound[i].size() == n) {
            cout << -1 << '\n';
            return;
        }
    }

    ll i = 1;
    while (i <= n) {
        ll t = 1;
        while (bound[i].find(t) != bound[i].end() && t <= n) {
            t++;
        }
        a[i] = t;
        i++;
    }
    for (ll i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
    cout << '\n';

where can i find the questions.?

how to solve the problem Small Indices? I cant understand Arpa's Solution.

This is Code foe Unsatisfied Array, can someone please point out why it is failing..
void solve(){
    int n,k;
    cin>>n>>k;
    vector<vector<int>> a(k);
    for(int i=0; i<k; i++){
        vector<int> temp(3);
        cin>>temp[0]>>temp[1]>>temp[2];
        a[i]=temp;
    }
    vector<vector<int>> data(n+2,vector<int>(n,0));
    for(int i=0; i<k; i++){
        int st=a[i][0];
        int en=a[i][1];
        int val=a[i][2];
        data[st][val-1]++;
        data[en+1][val-1]--;
    }

    for(int i=0; i<n; i++){
        for(int j=1; j<n+2; j++) data[j][i]+=data[j-1][i];
    }

    vector<int> ans(n+2);
    for(int i=1; i<n+1; i++){
        bool ch=0;
        for(int j=0; j<n; j++){
            if(data[i][j]==0){
                ans[i]=(j+1);
                ch=1;
                break;
            }
        }
        if(ch==0){
            cout<<-1<<endl;
            return;
        }
    }
    for(int i=1; i<=n; i++) cout<<ans[i]<<' ';
    cout<<endl;

}

I doubt the editorial solution for Equations is incorrect. The solution fails for the input

4 4 1 1 2 3 1 2 3 4 1 3 4 1 2 1 3

The editorial code's output is -1. The expected output for the test case is 1 since we can determine the value of a1 and a4 since a1+a4 = 0 and since the numbers in the array are non negative, a1 = 0 and a4 = 0.

Please add this test case and rejudge the solutions if possible.

Can someone share the contest link? Interested to check out the problems.

When will be the final standings be declared?

Why is this solution failing for Unsatisfying Array?

void solve(){
    int n,k;
    cin>>n>>k;

    V<vi> a(n+1,vi(n+1,0));
    set<int> sett;
    f(i,0,k)sett.insert(i);
    V<pair<pll,ll>> cond(k);
    vll ans(n,-1);
    f(i,0,k){
        int a1,b1,c1;
        cin>>a1>>b1>>c1;
        a[c1][a1-1]++;
        a[c1][b1]--;
        cond[i]=(mp(mp(a1,b1),c1));
    }
    fe(i,1,n){
        int tot=0;
        stack<int> st;
        f(j,0,n){
            tot+=a[i][j];
            if(tot==0&&ans[j]==-1){ // if tot==0, then it is not in the range whose min cant be i
                ans[j]=i;
                each(num,sett){
                    if(j+1>=cond[num].first.first&&j+1<=cond[num].first.second){ 
                        st.push(num); //remove the ranges which include this index
                    }
                }
            }
        }
        while(!st.empty()){
            sett.erase(st.top());
            a[cond[st.top()].second][cond[st.top()].first.first-1]--;
            a[cond[st.top()].second][cond[st.top()].first.second]++;
            st.pop(); // removing ranges or conditions as their minimum is already less than min.
        }        
    }
    bool done = false;
    f(i,0,n)if(ans[i]==-1)done=true;
    if(done){
        cout<<-1<<endl;
        return;
    }
    f(i,0,n){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}

To summarise:

1. AND Quest — same as this problem.
2. Small Indices — weak testcases, GPTable (Edit: GPT gets AC due to weak test cases).
3. Yet Another GCD Problem — unvalidated/wrong testcases.
4. Equations — wrong model solution (might have lead to false judging).

Where can we submit these problems for practice, kindly make this contest public.

great contest overall could have solved 4 problems but 3 is a very good result

• for the problem, Small Indices, would this work? I came up with a $$$O(n^2)$$$ solution, I haven't submitted it but I just wanted to discuss the idea. Do correct me if i have made any logical error.
• dp[index][count of good indices in prefix of i]

DP [i][j]

• consider first $$$i$$$ guys $$$(0..i)$$$. there are $$$j$$$ good indices
• return pair {mxsum , mxelement}
• {max sum formed by taking 2 elements, maximum element possible}
• if mxsum or mxelement is -inf, then (i,j) state is not possible

Note:

• mxelement and mxsum need not be from the same configuration, they can be from different configurations for the same $$$(i,j)$$$
• mxelement is among all possible configurations of j good indices in first prefix (0..i) which element can be maximum.
• mxsum is among all possible configurations of j good indices in first prefix (0..i), the maximum sum of 2 elements taken in all valid configurations

UPD: This approach is wrong.

There's a problem with AND Quest as well You are initializing with $$$cur = (1 \ll 30) - 1$$$, which would be incorrect if $$$k = cur$$$ and none of $$$A_i$$$ satisfy $$$A_i$$$ & $$$k$$$ $$$= k$$$. For example, consider the following case:

$$$k = (1 \ll 30) - 1$$$

$$$A = [1, 2, 3]$$$

your Output will be $$$YES$$$

here there is no subset of $$$A$$$ satisfying the constraint(your program assumes that null set gives cur leading to wrong answer)

When will the list of selected teams be declared for different sites?

Update Blog :)

Can someone give few testcases for unsatisfying array since mine fails on tc 5.

My approach is to put the minimum value possible at any given instance. If 1,2,3 and 6 cannot be used at a index, use 4 and remember 1,2,3 to not use them till their respective ending index and ignore condition for 6 since 4 is already smaller than 6.

here is the code:

int main()
{
    DRAMA;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

   int t;
   cin>>t;

    for(int o=1;o<=t;o++){

        ll n,k;
        cin>>n>>k;

        vector<pair<pair<ll,ll>,ll>> v;

        for(int i=0;i<k;i++){
            ll a,b,c;
            cin>>a>>b>>c;
            v.push_back({{a,b},c});
        }

        sort(all(v));

        ll j=0;

        vector<ll> ans(n);

        int r=0;


        vector<ll> temp(n+2,0);

        priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;

        for(int i=0;i<n;i++){

            vector<pair<ll,pair<ll,ll>>> temp1;

            while(j<v.size()&&v[j].first.first-1==i){
                temp[v[j].second]++;
                temp1.push_back({v[j].second,v[j].first});
                j++;
            }

            while(!pq.empty()&&pq.top().first-1<i){
                temp[pq.top().second]--;
                pq.pop();
            }

            ll res=mex(temp);

            if(res>n){
                r=1;
                break;
            }

            ans[i]=res;

            for(int i=0;i<temp1.size();i++){

                if(temp1[i].first<res){
                    pq.push({temp1[i].second.second,temp1[i].first});
                }
                else temp[temp1[i].first]--;
            }
        }

        if(r==1)cout<<-1<<endl;
        else {
            for(auto el: ans)cout<<el<<" ";
            cout<<endl;
        }

    }
}

how long until the results are finalized?

Hey guys, just wanted to verify my solution to Small Indices as my approach was different Arpa and Enigma27 could you please verify this since you both seemed active on here:

I did a O(N^2) approach by using the state as index and sum of the previous 2 maximum elements found. The final state has 12000 values as 0 <= A[i] and B[i] <= 2*N and N is maximum 3000 so 4*N => 12000.

This is what I submitted as Small Indices (It was accepted in contest but since there is a lot of speculation on the problem I'm not sure that even if it was accepted it is correct)

#include <bits/stdc++.h>
using namespace std;

int solve(int i, int &n, int m1, int m2, vector<int> &a, vector<int> &b, vector<vector<int>> &dp) {
    if(i == n) return 0;
    if(i == 0) {
        m1 = max(a[i], b[i]);
        return solve(i+1,n,m1,m2,a,b,dp);
    }
    else if(i == 1) {
        m2 = max(a[i], b[i]);
        return solve(i+1,n,m1,m2,a,b,dp);
    }
    
    if(dp[i][m1 + m2] != -1) return dp[i][m1 + m2];
    
    int ans1, ans2, tm1 = m1, tm2 = m2, add = 0;
    if(a[i] <= (m1 + m2)) add = 1;
    if(a[i] > m1 && a[i] > m2) {
        if(m1 > m2) {
            m2 = a[i];
        }
        else {
            m1 = a[i];
        }
    }
    else if(a[i] > m1) {
        m1 = a[i];
    }
    else if(a[i] > m2) {
        m2 = a[i];
    }
    ans1 = add + solve(i+1,n,m1,m2,a,b,dp);
    m1 = tm1;
    m2 = tm2;
    add = 0; 
    if(b[i] <= (m1 + m2)) add = 1;
    if(b[i] > m1 && b[i] > m2) {
        if(m1 > m2) {
            m2 = b[i];
        }
        else {
            m1 = b[i];
        }
    }
    else if(b[i] > m1) {
        m1 = b[i];
    }
    else if(b[i] > m2) {
        m2 = b[i];
    }
    ans2 = add + solve(i+1,n,m1,m2,a,b,dp);
    m1 = tm1;
    m2 = tm2;
    
    dp[i][m1 + m2] = max(ans1, ans2);
    return dp[i][m1 + m2];
}
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    
    vector<vector<int>> dp(n, vector<int>(12001,-1));
    
    cout << solve(0,n,-1,-1,a,b,dp) << "\n";
}

int main() {
 int t;
 cin >> t;
 while(t--) {
     solve();
 }
 return 0;
}