atcoder_official's blog

AtCoder Beginner Contest 376 Announcement
By atcoder_official, history, 4 weeks ago, In English

We will hold AtCoder Beginner Contest 376.

We are looking forward to your participation!

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

»
4 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

my first

→ Reply
»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

The first three questions this time...

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G scores 650. It sounds a lot harder. Anyway,

$$$ \Huge{\text{Good Luck & Have Fun!}} $$$
→ Reply
»
4 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

I was study in Daymayuan OJ.Small wowo is my teacher.I was L3.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that this time the question is easier than last time. Good luck!

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    contest ended.

    You're right, this is the first time I've achieved a ranking within 4000.

    Wishing everyone a better ranking in the next ABC.

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are right.

    this is the first time that I 've achieved a ranking within 4000 and aced 4 questions (ABCD)

    I extend my best wishes that everyone get a better rank in the next ABC.

    → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it -45 Vote: I do not like it

$$$\Huge\text{ABC376 RP++!}$$$

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck & Have Fun!

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

only ONE NOOOO！！！！！

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Somebody is cheating by discussing the solutions

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my code for D ???

//Author:RasShalGul
#include <bits/stdc++.h>
#define int long long
using namespace std;
int find_minimum_cycle(int N,int M,vector<pair<int,int>>&edges){
	vector<vector<int>>graph(N+1);
	for(const auto& edge:edges){
		graph[edge.first].push_back(edge.second);
	}
	vector<int>dist(N+1,-1);
	vector<int>parent(N+1,-1);
	queue<int>q;
	q.push(1);
	dist[1]=0;
	int min_cycle_length=LONG_LONG_MAX;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int v:graph[u]){
			if(dist[v]==-1){
				dist[v]=dist[u]+1;
				parent[v]=u;
				q.push(v);
			}else if(v!=parent[u]){
				min_cycle_length=min(min_cycle_length,dist[u]+dist[v]+1);
			}
		}
	}
	return (min_cycle_length==LONG_LONG_MAX)?-1:min_cycle_length;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N,M;
	cin>>N>>M;
	vector<pair<int,int>>edges(M);
	for(int i=0;i<M;i++){
		cin>>edges[i].first>>edges[i].second;
	}
	int result=find_minimum_cycle(N,M,edges);
	cout<<result<<"\n";
	return 0;
}
→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Perhaps you may find a cycle that doesn't include the root. Like, 1 -> 2 -> 3 -> 4 -> 2.

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F is a nice problem, thanks.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why greedy doesn't work for problem C?

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> toys(n), boxes(n-1);
    
    for(int i = 0; i<n; i++) {
      cin >> toys[i];
    }
    
    for(int i = 0; i<n-1; i++) {
      cin >> boxes[i];
    }
    
    sort(toys.begin(), toys.end());
    sort(boxes.begin(), boxes.end());
    
    int count = 0;
    
    int i = n-1, j = n-2, ans = -1;
    
    while(i >= 0 && j >= 0) {
      if(toys[i] <= boxes[j]) {
        i--; j--;
      }
      else {
        ans = toys[i];
        i--;
        count++;
      }
      
      if(count > 1) {
        ans = -1;
        break;
      }
    }
    
    cout << ans << endl;

    return 0;
}
→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are just missing an edge case:

    n = 4 toys = 1 2 3 4 boxes = 2 3 4

    you should add this at the end of the code to handle this case:

    if(i==0) ans = toys[0]

    also whenever posting code in comments, try to wrap it in a code spoiler

    → Reply
»
3 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

G is the answer of https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3646 divides $$$\sum_{i}a_i$$$.

WHAT are you doing,Mr.Atcoder?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hii,

Did anyone tried to solve D with dfs for cycle detection in directed graph?I tried but it is failing for half of the test cases.I know it is not efficient solution but just wanted to find the case where it can fail

Link to my submission

Thanks

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's say the graph contains two cycles. First 1->2->4->1 and Second 1->2->3->4->1. Since you are performing dfs it may be possible that you explore the second cycle first and thus all of 1,2,3 and 4 will be marked visited. Now you can no longer explore the first cycle as while trying to branch to node 4 from node 2, you will find that node 4 has already been visited. In all such scenarios you will not get the cycle with minimum edges.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, that was the point I was missing. Thanks

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D if the graph was undirected?

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

    Currently I just have $$$O(n^2logn)$$$ solution. I will post again if I got better solution.

    Let $$$S$$$ be the set of nodes which are directly connected to $$$1$$$ and remove all the direct edges between $$$1$$$ and $$$s$$$ where s belongs to $$$S$$$. After that our task is to find the value of $$$min(dis(i,j))+2$$$, where $$$i,j$$$ belongs to set $$$S$$$ and $$$dis(i,j)$$$ means distance between nodes $$$i$$$ and $$$j$$$. which can be done in $$$O(n^2logn)$$$.

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain why my code could not pass problem C or give me a test case?

n = int(input())
toys = [int(c) for c in input().split()]
boxes = [int(c) for c in input().split()]

toys.sort()
boxes.sort()
ans = 0
for i in range(n - 1, -1, -1):
    if ans == 0:
        if i == 0:
            ans = toys[i]
            break
        if toys[i] > boxes[i - 1]:
            ans = toys[i]
    elif ans != 0:
        if toys[i] > boxes[i]:
            ans = -1
        break
print(ans)
→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be nice to have a separate leaderboard for rated/unrated participants similar to what Codeforces has with a checkbox "show unofficial".

snuke Do you know if a single leaderboard is intentional or there're plans to implement something similar to what I've described?

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, in fact there is a Show rated only button in Customize.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Indeed, thank you for pointing this out!

      Anyway, the button Customize is hidden enough that it either requires prior knowledge or pure luck to find it :)

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

In problem D. How could more than a cycle contain the same vertex if the vertices each have a single outgoing edge? At least that's what I interpreted by the problem statement

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There's no condition in the statement that the outgoing edge has to be single. It just says: "There is a simple directed graph with N vertices numbered from 1 to N and M edges. The i-th edge (1≤i≤M) is a directed edge from vertex a_i to vertex b_i".

    FWIW, this blog which conveniently was in "Recent actions" just before the start of the Atcoder round helped me to solve this problem — although final solution requires a small modification to the original graph.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I interpreted it wrong. Honestly this contest was easier than most ABCs, right? Like during contest I got A and B right (attempted C but it got runtime error on some tests down the line), but I was able to understand and implement all but the last 2 problems. For example that graph question was just a direct application of BFS, which is pretty weird for a D problem in ABC tbh

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this the initialization of the dp in problem F? 

int ph = 0, pp = 0;
dp.assign(Q + 1, vector<int>(N, INF));
dp[0][1] = 0;

This assumes that the other hand is at position 1, but it could be at 0, shouldn't it depend on the first query?

→ Reply