Toyota Programming Contest 2024#7（AtCoder Beginner Contest 362） Announcement

5 месяцев назад, # |

+22

Liked F but G ruined everything

→ Ответить

5 месяцев назад, # ^ |

G btw

→ Ответить

satyam343

5 месяцев назад, # ^ |

F btw

→ Ответить

5 месяцев назад, # ^ |

← Rev. 2 →

Damn that's just sad now

→ Ответить

nika-skybytska

5 месяцев назад, # ^ |

But it doesn't demand a certificate.

→ Ответить

myst-6

5 месяцев назад, # ^ |

This is very similar too.

→ Ответить

aryanc403

5 месяцев назад, # ^ |

-8

G btw

→ Ответить

not_insync

5 месяцев назад, # ^ |

+10

how did u do F was it Hungarian?

→ Ответить

5 месяцев назад, # ^ |

← Rev. 2 →

+22

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.

→ Ответить

SummerSky

5 месяцев назад, # ^ |

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)

→ Ответить

5 месяцев назад, # ^ |

Yes, it is the centroid

→ Ответить

ar_u

5 месяцев назад, # |

E took my energy

→ Ответить

FFTotoro

5 месяцев назад, # |

+43

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.

→ Ответить

alittlemiddle

5 месяцев назад, # ^ |

and like this: https://vjudge.net/problem/LightOJ-1427

→ Ответить

_trie_again

5 месяцев назад, # |

Is g some standard problem?

→ Ответить

nichke

5 месяцев назад, # ^ |

Yes, very standard. Either Aho or Suffix Array will do it.

→ Ответить

not_insync

5 месяцев назад, # ^ |

yep its a cses problem

→ Ответить

WORTH

5 месяцев назад, # ^ |

Yes

→ Ответить

Pirate_King

5 месяцев назад, # ^ |

How could you not know that with that username

→ Ответить

_trie_again

5 месяцев назад, # ^ |

I know trie but not aho corasik algo

→ Ответить

lucky_clover_

5 месяцев назад, # |

+40

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

→ Ответить

copyPasteCoder

5 месяцев назад, # |

how to solve E

→ Ответить

alittlemiddle

5 месяцев назад, # ^ |

very ez that dp

→ Ответить

DeadMan69

5 месяцев назад, # ^ |

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.

→ Ответить

drgrenkenstein

5 месяцев назад, # |

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

→ Ответить

alittlemiddle

5 месяцев назад, # ^ |

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

→ Ответить

al-ghoul

5 месяцев назад, # ^ |

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

→ Ответить

vector1024

5 месяцев назад, # ^ |

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

→ Ответить

al-ghoul

5 месяцев назад, # ^ |

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

→ Ответить

diobrando97

5 месяцев назад, # |

Can't believe so many people would SAM.

→ Ответить

jzcrq

5 месяцев назад, # ^ |

In fact,ACAM is enough.

→ Ответить

jzcrq

5 месяцев назад, # ^ |

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

→ Ответить

diobrando97

5 месяцев назад, # ^ |

Also can't believe so many people would ACAM. ==

→ Ответить

liujinrui

5 месяцев назад, # ^ |

You can also use ACAM to solve G.

→ Ответить

FeiWuLiuZiao

5 месяцев назад, # ^ |

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

→ Ответить

yeminghan

5 месяцев назад, # |

← Rev. 3 →

+100

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

→ Ответить

metelkov

5 месяцев назад, # |

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?

→ Ответить

hxu10

5 месяцев назад, # |

← Rev. 2 →

+29

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.

→ Ответить

GDCass1ni

5 месяцев назад, # ^ |

-10

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

→ Ответить

not_insync

5 месяцев назад, # |

← Rev. 2 →

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

→ Ответить

metelkov

5 месяцев назад, # ^ |

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.

→ Ответить

lgx57

5 месяцев назад, # |

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

→ Ответить

45_fortyfive

5 месяцев назад, # |

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

→ Ответить

par4dox

5 месяцев назад, # ^ |

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)

→ Ответить

lgx57

5 месяцев назад, # |

E is similar to this problem.

→ Ответить

Mango2011

5 месяцев назад, # ^ |

But their ideas are different.

→ Ответить

xiaoxiaoxiaoxiaoyyds

5 месяцев назад, # |

The G problem is not a original problem.

→ Ответить

UP84

5 месяцев назад, # |

Delete G.

→ Ответить

5 месяцев назад, # |

← Rev. 2 →

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; }

→ Ответить

5 месяцев назад, # ^ |

bhai, you are pushing same node multiple times in the PQ.

Lets say, graph,

lets say, the input is

4 5

10 10 10 10 

1 2 20

2 3 1

1 3 1

1 4 1

4 2 1

Please check, how many times you are pushing node value '2' in the queue.

→ Ответить

5 месяцев назад, # ^ |

Yeah I got my mistake,thanks a lot

→ Ответить

5 месяцев назад, # ^ |

← Rev. 2 →

You should create an array called bool vis[] which stores whether each node has already been processed. Without this array, sometimes a node can be processed multiple times. Although this doesn't result in an infinite loop, this still significantly adds to the execution time. (Processed multiple times means the neighbors of the node is relaxed multiple times, which isn't necessary.)

FYI the solution to this problem is that for every edge u->v with weight w, we simply add arr[v] to w. Then, we run a standard dijkstra and add arr[1] to our answer. Proof of correctness is fairly straightforward.

PS: It is recommended to send submission links rather than the whole code. This is not only more aesthetically pleasing but also gives us more information on the submission, whether it TLEs or WAs, etc.

→ Ответить

5 месяцев назад, # ^ |

Thanks I got my mistake, yes I'll paste the link next time onwards

→ Ответить

uday03meh

5 месяцев назад, # ^ |

← Rev. 3 →

can you share the submission link using visited array with this code ?

→ Ответить

u can check the submission here the mistake I was doing is that some there will be a lot of overhead so to prevent that you can add a condition if distance at that place is less than dd than just continue and avoid visiting it's neighbours at it would only increase the cost ...

5 месяцев назад, # ^ |

→ Ответить

uday03meh

5 месяцев назад, # ^ |

yeah, it works same as using the visited array before checking for it's neighbours, if the node is visited then continue

→ Ответить

lookcook

5 месяцев назад, # |

+11

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

→ Ответить

Iingfunny

5 месяцев назад, # |

← Rev. 3 →

-10

[DELETED]

→ Ответить

5 месяцев назад, # |

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.

→ Ответить

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

5 месяцев назад, # ^ |

Can you please check this submission ? why is this getting WA, just can't figure out. Can't figure out the error :| .

→ Ответить

5 месяцев назад, # ^ |

Breakcase:

10 13
1660 7612 4840 3444 6628 7079 9647 9324 803 9135 
8 2 6893
4 4 8584
10 5 4386
2 5 9772
10 8 3026
10 9 2303
9 5 3584
7 8 654
9 10 208
6 3 1571
1 2 6613
1 3 2485
1 4 9067

Your code gives:

15885 8985 14171 32285 17635 42403 32102 36672 46015

Correct answer:

15885 8985 14171 32285 17635 42403 32102 36672 44263

→ Ответить

5 месяцев назад, # ^ |

thanks a lot.

→ Ответить

0x0002

5 месяцев назад, # |

+55

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

→ Ответить

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

5 месяцев назад, # |

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

→ Ответить

siddhantnema

5 месяцев назад, # |

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?

→ Ответить

Algo_Phoenix

5 месяцев назад, # ^ |

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

→ Ответить

siddhantnema

5 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

Algo_Phoenix

5 месяцев назад, # ^ |

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..

→ Ответить

siddhantnema

5 месяцев назад, # ^ |

← Rev. 2 →

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!

→ Ответить

5 месяцев назад, # |

← Rev. 2 →

Problem G is a template of Aho–Corasick algorithm.

→ Ответить

incra

5 месяцев назад, # ^ |

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

→ Ответить

5 месяцев назад, # ^ |

But it's such a name in Wikipedia.

→ Ответить

incra

5 месяцев назад, # ^ |

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.

→ Ответить

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

5 месяцев назад, # ^ |

Yes you are right, its name is indeed this.

→ Ответить

Spartan-007

5 месяцев назад, # |

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

→ Ответить

5 месяцев назад, # ^ |

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

→ Ответить

Spartan-007

5 месяцев назад, # ^ |

← Rev. 2 →

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.

→ Ответить