Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

atcoder_official's blog

Panasonic Programming Contest 2024（AtCoder Beginner Contest 375） Announcement
By atcoder_official, history, 2 months ago, In English

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

We are looking forward to your participation!

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

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

Hoping to get more active on AtCoder starting from this ABC

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

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

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

    But gap btw D and E is low

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

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

    → Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

C 400pts？That's so amazing.

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

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

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

    Same question

    → Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    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
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, 400 points problem C!

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

375 is 3/8 times 1000.

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

It seems that problem C will be very hard this time.

GL!

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

I hope we can all get a high score in the competition. Good luck!

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

Wow, C and D have the same score this time, both are 400 points

GL&&HF

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

400 points problem C? It must be difficult!

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

As a participant, I confirm that problems are problems

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

Hoping to get 0.

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

Hoping it is easy enough......

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

Is there a bit of water in the data of question E, I can still AC if I write the DP transfer wrongly.

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

G is almost the same as 567E

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

Can someone explain C and G?

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    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
    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

    To solve C, is helpful to visualize each operation as a 90 degrees clock-wise rotation in the square. Then, the border of the complete square N*N will be rotated once, the border of the centered square of N-2*N-2 will be rotated two times and so on. You can only implement a function that performs rotation, and then have in count that each 4 rotations you get the original values in the border of the square.

    → Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    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
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

        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
        → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        2 months ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        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
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

where will the editorial for the problems be published?

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

A little confusion on C. It took me a while to realize that: all pairs {x, y} between a and b means: a << x <= b and a <= y <= b.

Otherwise, the problem setting is excellent as usual.

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

For G , consider all edges which are part of smallest path from 1 to N . Now we need to find all the bridges in the final graph . Its implementation heavy.

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

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
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I left C after reading the statement cause C and D gave me same points but D's statement was much simpler.

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

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
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$C$$$ $$$\gt\gt$$$ $$$E$$$

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

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
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this contest's F is quite interesting, despite I haven't got it during the contest.

→ Reply
»
25 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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