atcoder_official's blog

Toyota Programming Contest 2024#7（AtCoder Beginner Contest 362） Announcement
By atcoder_official, history, 3 weeks ago, In English

We will hold Toyota Programming Contest 2024#7（AtCoder Beginner Contest 362）.

We are looking forward to your participation!

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

»
3 weeks ago, # |
  Vote: I like it -53 Vote: I do not like it

Can you give the topics for each question

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

    A-Brute Force

    B-G- Segment Tree and Binary search problems.

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

Good luck, my friends!

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

GL&HF!

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

..

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

Liked F but G ruined everything

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

    G btw

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

    how did u do F was it Hungarian?

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

      My logic:

      Let the root of the tree be 1, you will notice that the most optinal way to the make the matchings is to make pairs between nodes such that they are in subtrees of different children of 1.How you make the matching doesn't matter since the total weight of the matching=sum of distances of all nodes from root i.e. 1.

      Now, if any children of the root of the tree i.e. 1 have subtree size > $$$n/2$$$ where n is number of vertices in tree. You can't make matchings for all the nodes in the optimal way mentioned above. To overcome this, reroot the tree such that the subtree size of all the children of the root is <= $$$n/2$$$. This root always exists and can be found using dfs.

      Now, To implement the construction of the matching there are many ways. What i did was make a set of the subtree sizes of children of the root and then take a node from both the subtree with smallest and largest size and pair them up, it doesn't matter what node you take as long as each node is taken once. Do this till all nodes have been matched.

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

        I just find that I have almost the same idea as yours (but failed finishing it during contest), thank you so much for sharing your solution! By the way, in the step of "reroot the tree ...", is the new root just the centroid of the tree? (I think it is but not quite sure)

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

E took my energy

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

Are you kidding? Why is task G the template of the Aho-Corasick Automaton?

Here is the template task in Luogu. They are the same.

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

Is g some standard problem?

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

Please stop giving problems that can be solved by just copying the template like G.

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

how to solve E

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

    very ez that dp

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

    I did it using 3d dp.

    This is my submission :https://atcoder.jp/contests/abc362/submissions/55562909 (was my first contest at atcoder :))

    I set dp[i][length][diff] = number of such sequences such that the ending position of subsequence is i , the length of subsequence is length and the difference of the AP is diff , i kept diff in a dictionary(map) as the value of diff could reach upto 10^9.

    After that just used dp[i][length+1][diff] += dp[j][length][diff]

    Since if there is subsequence of length k with difference diff and the current element minus j th element is equal to diff , then we could make a new subsequence of length legth+1

    Then for the final answer , just printed the summation of length for all i and diff.

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

How do you solve C? I managed to solve D and E but couldn't solve C

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

    The minimun sum u can construct is sum of all l[i] and maximun is sum of all r[i]

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

    lmfao I wish I skipped C then coz by the time I finished it I had no time for either D or E

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

    Yes,me too.D is a standard problem and E is a DP problem.But C is harder than D.

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

    To construct the Xs you can initialize them to the maximum sum they can give, then decrease them until the sum is 0. You can also probably go in the reverse direction as well, start with minimum sum and increase

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

Can't believe so many people would SAM.

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

    In fact,ACAM is enough.

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

      Perhaps a more appropriate statement would be "KMP on Trie".

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

    You can also use ACAM to solve G.

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

    Most of them just copy the others' code. There is a similar problem on a Chinese OJ and there are published solutions with code.

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

Atcoder, if you aren't able to set Gs then just remove them.

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

Solved F a couple of minutes after the contest has ended, eternal pain and suffering

Should have taken a hint from the problem name. Btw what's the actual way to do a matching in a case like this, without bruteforcing and abusing move-semantics?

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

Problems such as problem G shouldn't appeared in the contest. It is too original, and you just need to copy and paste without any thinking. Even worse to make G 575 but F 550, it should be reversed. It's super unfair for candidates who can solve F but doesn't know anything about AC automation.

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

    Don't know ACAM means too weak. Just practise more.

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

how to do F ?

I could get somewhat idea to use Hungarian but that O(n^3) then whats the way to solve F or am i overthinking and using something which is useless like Hungarian in this case

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

    I kind of guessed F, if you find a centroid and start matching nodes from different subtrees of centroid then the actual pairs do not matter since they won't affect the answer, ie sum of all distances should stay the same (at least it feels like it). Then you have reduced the problem to matching integer values from different sets.

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

I don't like this round. It has a template problem like G, it makes this round boring and unfair.(just my opinion)

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

Solved E after 3 mins the contest ended... Fortune enough to notice G is suffix array to cover the loss in E.

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

    Can you tell me why this code fails

    I have a counter case I am not able to figure out where I am wrong 5 1 1 1 1 1

    (Code)

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

E is similar to this problem.

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

The G problem is not a original problem.

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

Delete G.

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

Can anyone help I am getting tle on last 2 test cases of problem d int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); lli n,m; cin>>n>>m; vectorarr; arr.push_back(0); for(int i=0;i<n;i++){ lli x; cin>>x; arr.push_back(x); } vector<pair<lli,lli>>mp[n+1];

for(int i=0;i<m;i++){ lli x,y,z; cin>>x>>y>>z; mp[x].push_back({y,z}); mp[y].push_back({x,z}); } vectordis(n+1,1e18); dis[1]=0;

priority_queue<pair<lli,lli>, vector<pair<lli,lli>>, greater<>> pq; pq.push({arr[1],1}); while(pq.size()>0){ lli dd=pq.top().first; lli vv=pq.top().second; pq.pop(); for(auto it:mp[vv]){

if(dis[it.first]>dd+it.second+arr[it.first]){
        dis[it.first]=dd+it.second+arr[it.first];

        pq.push({dis[it.first],it.first});
    }

}

} dis[1]=0; for(int i=2;i<=n;i++){ cout<<dis[i]<<" "; }

return 0; }

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

I copied pasted my solution to G from CSES and changed 0 lines. I don't think problems like this should appear in a rated round. If problems like this are to appear, it should be in an unrated educational round (similar to the Atcoder DP contest a long time ago).

Link: https://cses.fi/problemset/task/2103

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

[DELETED]

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

This round was particularly frustrating, because I haven't seen G before and therefore spent a substantial amount of time on G. Hence, I finished the contest with ABCDE_G. However, I realized the greedy solution for F merely 5 minutes after the contest. If I had seen G before, I could focus on F and would have definitely full-solved. Not only did I not full-solve, my rating is probably going to be affected too, due to the fact that so many people have seen G before. I think many people are having the same thoughts, so atcoder_official, if you can't set G's, then don't. Having a contest with 6 problems is better than having a template question as the highest-point problem.

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

In fact, problem F is so similar to 1387B2 - Village (Maximum).

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

can someone please help me figure out the mistake in this ?

https://atcoder.jp/contests/abc362/submissions/55580896

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

Does Dijkstra with Min Heap priority queue not work for anyone for D? It gives TLE for me. So is the solution using Fib Heap? Or is it some optimization issue?

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

    It worked for me with just some slight modification - At line 52, 53 and 69, 71 --> rest the whole algorithm will be normal djikstra

    You can check — My submission

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

      Ohh it looks very similar to my approach too!

      Can you check this submission out: https://atcoder.jp/contests/abc362/submissions/55586366

      I'm not sure of the TLE in this. The approach is more or less the same. Also in my previous version of reply I had a silly mistake of not including V,U edge which caused WA

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

        Inside the solve function --> you are creating a self loop => which may cause both TLE and Wrong answer

        graph[u].push_back(Edge(v, b)); graph[u].push_back(Edge(u, b)); --> v must be there

        I think it should get accepted, feeling bad for the typo..

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

          Lol yea saw that. That was silly haha. Still TLE tho.

          Edit: Turns out my visited array I was using for not doing repetitive computation was not doing the trick. I should've used the dist array itself. Got it now. Thanks for helping me out bro!

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

Problem G is a template of Aho–Corasick algorithm.

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

    By the way, it's not Aho–Corasick algorithm but Aho–Corasick Automaton.

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

      But it's such a name in Wikipedia.

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

        Well, you see,Aho-Corasick is not a Algorithm but a data structure based on trie, so I think there might be an error in Wikipedia.

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

Hello there!. Please help me with this submission why TLE!!

https://atcoder.jp/contests/abc362/submissions/55595549

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

    Hi!You should add if (vis[u]) continue; to 145th line.

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

      Yeah I got it. Thanks

      But why exactly this works. You can see that I am checking for vis while traversing for all the neighbors.

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

        Possible reasons for this are that a point's neighbor is placed on the back end of the priority queue, causing the point to not be marked in time, and it can also cause a node to queue many times and time out.

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

          Ok I see. Traversing the neighbors of the same node more then once is a problem. If the node enters in the pq then it will get it neighbors checked this may happen multiple times. Now I get it.

          Thanks mate!!. (Mentioning this to not follow the same in future).

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

Can anyone please spot the mistake in my code for C question I am getting 2 Wrong answers rest all accepted.

My submission: https://atcoder.jp/contests/abc362/submissions/55602146

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

t o y o t a

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

Edit — solved

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

how come my O(n^5) code is running for problem e https://atcoder.jp/contests/abc362/submissions/55674291 I think it shouldn't... someone please correct me if i am wrongly calculating complexity or the constraints are just too loose

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

Can anyone explain me the approach Jinagly used for problem G. https://atcoder.jp/contests/abc362/submissions/55526066 What does the array fail indicate?

→ Reply