Panasonic Programming Contest 2024（AtCoder Beginner Contest 375） Announcement

atcoder_official's blog

By atcoder_official, history, 19 months ago, In English

We will hold Panasonic Programming Contest 2024（AtCoder Beginner Contest 375）.

Contest URL: https://atcoder.jp/contests/abc375
Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20241012T2100&p1=248
Duration: 100 minutes
Writer: cn449, kyopro_friends, ynymxiaolongbao
Tester: MtSaka, sounansya
Rated range: ~ 1999
The point values: 100-150-400-400-450-550-575

We are looking forward to your participation!

atcoder

atcoder_official
19 months ago
41

Comments (23)

Show archived | Write comment?

Mahog

19 months ago, hide # |

Wow, the gap from B to C is huge o.O

→ Reply

SNX03

19 months ago, hide # ^ |

But gap btw D and E is low

→ Reply

yvmr33

19 months ago, hide # ^ |

I think C is not difficult to get the logic , understanding and implementation is little difficult.

→ Reply

xiaozha

19 months ago, hide # |

← Rev. 2 →

C 400pts？That's so amazing.

→ Reply

LHLeisus

19 months ago, hide # |

What is the Distribution of Problem Statements on the top page for?

→ Reply

FFTotoro

19 months ago, hide # ^ |

← Rev. 2 →

+14

AtCoder suffered DDoS attacks during some contests last year. During that period, Panasonic (also the sponsor of this contest) sponsored a contest, ABC301. To avoid the effect of the DDoS attack, they distributed the problem statements in PDF format during the contest.

Later, when Panasonic hosted contests again, they might have directly copied the problem statements from previous contests without any modifications, so the PDF version of the problem statements was retained—even though the statement was still from ABC301.

→ Reply

llc5pg

19 months ago, hide # |

375 is 3/8 times 1000.

→ Reply

harvey_wzy

19 months ago, hide # |

As a participant, I confirm that problems are problems

→ Reply

Mahog

19 months ago, hide # |

← Rev. 2 →

G is almost the same as 567E

→ Reply

then00bprogrammer

19 months ago, hide # |

Can someone explain C and G?

→ Reply

letsgetgood

19 months ago, hide # ^ |

← Rev. 2 →

C is just implementation, do what the question is saying to do. Note that the operation rotates a square submatrix each time. The size of this submatrix goes from n to 1. For every index, figure out how many times it will get rotated(distance from edge % 4), and just do the operation that many times.

Code

import sys

def main():
    n = int(input())
    mat = list(map(lambda s: list(s.strip()), sys.stdin.readlines()))
    mat2 = [[0] * n for _ in range(n)]
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            edge_dist = min(i-1, n-i, j-1, n-j)
            times = (edge_dist + 1) % 4 # how many rotations
            target_i, target_j = i, j
            for k in range(times):
                target_i, target_j = target_j, n + 1 - target_i
            mat2[target_i-1][target_j-1] = mat[i-1][j-1]
    
    for row in mat2:
        print("".join(map(str, row)))

→ Reply

infinitix

19 months ago, hide # ^ |

Nice implementation. I ended up writing a complex code for performing complete rotation on each outer strip of (n-i)*(n-i) square.

→ Reply

gabriel88766

19 months ago, hide # ^ |

← Rev. 2 →

For G I ran dijkstra and made a new graph based in all edges for all shortest path. an edge is part of a shortest path if it make the distance lower or keep the distance equal from 1 to some vertex when running dijkstra. Then I made a new graph based on this edges and found all bridges. bridges can make the new graph disconnected and then there won't be a path from 1 to N using that graph.

For C, I divided the grid in layers (like a onion). in layer 1 you will rotate 1, and in general in layer i you will rotate each cell i times. find i%4 and rotate i%4 times, because after 4 rotations the cell will be in the same place.

→ Reply

then00bprogrammer

19 months ago, hide # ^ |

Thank you, can you please also explain how to find edges which are part of all shortest paths?

→ Reply

gabriel88766

19 months ago, hide # ^ |

← Rev. 2 →

Let dist[x] be the distance from 1 to x, and w[a][b] = weight of the edge ab

if the distance from "1" to "b" is X, and dist[a] + w[a][b] = X, and b is in some shortest path, then ab is one of these edges.

First I ran dijkstra and keep a "parent" vector, then I ran a bfs from N to 1 to make the new graph

Code


vector<ll> adj[N], adjw[N], par[N], adj2[N];
ll dist[N];


void dijkstra(int src){
    memset(dist, 63, sizeof(dist));
    dist[src] = 0;
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    pq.push({0, src});
    while(!pq.empty()){
        auto d = pq.top().first;
        auto u = pq.top().second;
        pq.pop();
        if(d > dist[u]) continue;
        for(int i=0;i<adj[u].size();i++){
            ll v = adj[u][i], w = adjw[u][i];
            if(dist[v] > dist[u] + w){
                par[v].clear();
                par[v].push_back(u);
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }else if(dist[v] == dist[u] + w){
                par[v].push_back(u);
            }
        }
    }
}

//in main
queue<int> q;
vector<bool> vis(n+1, false);
q.push(n);
vis[n] =true;
while(!q.empty()){
    auto u = q.front();
    q.pop();
    for(auto v : par[u]){
        adj2[u].push_back(v);
        adj2[v].push_back(u);
        if(!vis[v]){
            vis[v] = true;
            q.push(v);
        }
    }
}

→ Reply

brave-kid

19 months ago, hide # ^ |

← Rev. 2 →

in problem $$$C$$$ I have to rotate for each $$$i$$$ upto $$$N/2$$$?Also how did you reach this observation?What was your observation?

→ Reply

gabriel88766

19 months ago, hide # ^ |

← Rev. 4 →

This way

image

Need to rotate all cells

This is just what I got after read the statement. The main observation to solve the problem is you don't need to rotate i times, only i%4 times. and the other observation is how to get the layer. the layer is the minimum distance from i to 0, from i to n+1, from j to 1, from j to n+1

int layer = min(min(i, n+1-i), min(j, n+1-j));
layer %= 4;
int ri = i, rj = j;
for(int r=1;r<=layer;r++){
    swap(ri, rj);
    rj = n + 1 - rj;
}
ans[ri][rj] = gr[i][j];

→ Reply

brave-kid

19 months ago, hide # ^ |

thanks

→ Reply

Astroflexx

19 months ago, hide # |

Parkinson's disease, Crohn's disease, Sickle cell anemia, Amyotrophic lateral sclerosis (ALS), Alzheimer's disease, Multiple sclerosis (MS), Cystic fibrosis, Lupus, Tuberculosis, Hepatitis C, Rheumatoid arthritis, Diabetes mellitus, Hypertension, Asthma, Ebola, Malaria, Lyme disease, Dengue fever, Psoriasis, Influenza.

These are the diseases I suffered while trying to solve problem C.

→ Reply

Madhav_1608

19 months ago, hide # |

← Rev. 4 →

Can somebody please help me understand my mistake in the submission for G? Submission Link-> https://atcoder.jp/contests/abc375/submissions/58739004

Edit: I got my error, my infinity value was not enough in dijkstra implementation.

→ Reply

wxy2010

19 months ago, hide # |

Well, G is weaker than a well-known problem in China called Bridge.

Link: https://www.luogu.com.cn/problem/P2685

The solution is to calculate any shortest path of the graph first, and get the point for each point v where the shortest path from 1 or n to v part from the shortest path from 1 to n. For each edge (u,v) which is not on the path, we can know the range it can influence. So that we can use a segtree to maintain the shortest path from 1 to n when we delete an edge on the former path.

BTW, I tried to modify the code I wrote for that problem to pass G but failed :(

→ Reply

wxy2010

19 months ago, hide # ^ |

← Rev. 2 →

I see the official editorial and it is easier than the problem I just mentioned so it have a simplier implementation. But I believe many of the people must have solved this problem before.

→ Reply

shinchankosen

17 months ago, hide # |

According to https://atcoder.jp/users/ynymxiaolongbao, his name at CF is YoshikaMiyafuji, not ynymxiaolongbao. If you just write the name on atcoder, wouldn't it be better not to connect it to the user's link like kyopro_friends?

→ Reply