atcoder_official's blog

AtCoder Beginner Contest 446 Announcement
By atcoder_official, history, 2 months ago, In English

We will hold AtCoder Beginner Contest 446.

We are looking forward to your participation!

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

»
2 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Happy spring festival!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Have fun!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
2 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    #include<bits/stdc++.h>
using namespace std;
int t,n,m,x,y,ans;
struct f{
	int a,b;
}a[200005]; 
deque<int> q;
int work(){
	while (!q.empty()) q.pop_front();
	for (int i=1;i<=n;i++){
		q.push_back(a[i].a);
		x=a[i].b;
		while (x>=q.front()){
			x-=q.front();
			q.pop_front(); 
			if (x==0) break; 
		}
		if (x!=0){
			y=q.front();
			q.pop_front(); 
			y-=x;
			q.push_front(y);
		}
		while (q.size()>m){
			q.pop_front();
		}
	}
	ans=0;
	while (!q.empty()){
		ans+=q.front();
		q.pop_front();
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while (t--){
		cin>>n>>m;
		for (int i=1;i<=n;i++){
			cin>>a[i].a;
		}
		for (int i=1;i<=n;i++){
			cin>>a[i].b;
		}
		cout<<work()<<"\n";
	}
	return 0;
}
    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I solved it, but I didn't use any deque<int> structure. Here is my submission: Link to code

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    here's my code:

    Spoiler
    → Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I find this example hacked your code:

    Input: 5 9 4 5 4 3 3 4 1 2 2 5 4 5 5 4 5 3 4 3

    Expected Output: 1 1 -1 -1 0

    Your output: 1 1 -1 1 0

    I hope this can help you.

    → Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply