Happy spring festival!

Have fun!

Screencast: https://youtu.be/I-7cw-uSXig (solving all problems)

Has anyone solved the Omelette Restaurant using a Deque...?

I got 23 AC and 7 WA. I'm very curious about those 7!

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

void solve()
{
    int n, d;
    cin >> n >> d;
    vector<int> buy(n);
    vector<int> use(n);
    int dayCount = -1;
    for (auto &it : buy)
        cin >> it;
    for (auto &it : use)
        cin >> it;
    deque<int> dq;
    for (int i = 0; i < n; i++)
    {
        dayCount++;
        // mrng
        dq.push_back(buy[i]);
        // aft
        dq.front() -= use[i];
        // evng
        // cout << "day: " << i << " " << dq.front() << " " << dq.back() << endl;
        if (i == d)
        {
            if (dq.front() > 0)
                dq.pop_front();
            dayCount = 0;
        }
    }
    int ans = 0;
    for (int i = 0; i < dq.size(); i++)
    {
        ans += dq[i];
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

Solved $$$F$$$ 13 min after contest ended :(

Good problems, thanks for the round math957963 sheyasutaka physics0523 sounansya and all testers.

Any body know how to get rating more than 1400, and what are tricks are there ?

Can someone please help? I am trying to solve problem F, this is my code. It passes 54/55 cases and I don't know why it fails one.

#include<bits/stdc++.h>
using namespace std;
#define db freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
 
 
/*
anything before a matching will become matched, so find the latest index where a matching is possible
*/
const int mx = 1e9;
void solve()
{
  int n, m;
  cin>>n>>m;
  vector<vector<int>>adj(n);
  vector<int>answer(n), lowest(n, mx), reachable(n);
  for(int i=0; i<m; i++)
  {
   int a, b;
   cin>>a>>b;
   a--;
   b--;
   adj[a].push_back(b);
  }
  //lowest node of starting node is always possible
  lowest[0]=0;
  queue<int>q;
  q.push(0);
  while(!q.empty())
  {
      int node = q.front();
      q.pop();
      //find all reachable nodes
      reachable[node]=1;
      for(auto c: adj[node])
      {
        //all nodes that are not reachable will have lowest = mx
         lowest[c] = min(lowest[c], node);
         if(reachable[c]==0)
         {
          //we dont push visited nodes again because nodes reachable from them will be explored
            q.push(c);
            reachable[c]=1;
         }
      }
  }


  for(int i=0; i<n; i++)
  {
   if(lowest[i]<i)
   {
      answer[lowest[i]]+=1;
      answer[i]+=-1;
   }
  }

  int biggest_node=lowest[0];
  for(int i=0; i<n; i++)
  {
    answer[i] = (i>0)? answer[i]+answer[i-1]: answer[i];
    biggest_node = max(biggest_node, lowest[i]);
    if(biggest_node > i)
    {
      cout<<-1<<"\n";
    }
    else{
    cout<<answer[i]<<"\n";
    }
  } 
}

int main()
{
   //db;
   // // int t;
   // // cin>>t;
   // while(t--)
   // {
   //    solve();
   // }
   solve();
}

A counterexample would be nice please

If we care about distinct subsequences based on indecies as well in G, is what's better than $$$O(N^2)$$$ ?