We will hold HHKB Programming Contest 2023(AtCoder Beginner Contest 327).
- Contest URL: https://atcoder.jp/contests/abc327
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20231104T2100&p1=248
- Duration: 100 minutes
- Writer: Nyaan, math957963, evima
- Tester: cn449, yuto1115
- Rated range: ~ 1999
- The point values: 100-200-250-400-475-550-650
We are looking forward to your participation!
Hello.I wish luck to everyone in this contest!
You too. Good Luck.
AtCoder isn't working? It shows 403 on my browser. Is it my problem?
It is working,but the problems are to difficult!
i do a,b,c but d to g is too hard
Actually d is very simple.
But g is also too hard for me.
$$$G$$$ is hard for many GMs as well.
well, don't discuss anything before this contest ends!
Hey, This is my first contest. Where can i find the answers after the contest is finished? I heard atcoder contests are suitable for beginners. But, this is too overwhelming!!
Wait for the end of the contest!
When the contest ends a button for editorial appears at each problem page.
How u solved E?
with dp!
If you observe in the given equation only the numerator for the first term makes any sense (changes for different sizes of subsequence).
So we can find the maximum value of a subsequence of length K (for K = 1 to N)
we will use this dp value as a numerator of the first term and the rest can be substituted easily and we can find the maximum ans over all subsequences of different lengths!
My submissions
okay
E is even more simpler than D
But I spent 5 mins on D, and 50 mins on E qwq
4x'wa' at problem D, 6x'wa' at problem E...
Me either…
okay... problem D I used BFS, but one little mistake. problem E I did not setprecision(10).
is problem E a dp Problem ?
Yes
Why finding cycle in D doesnt work? it failed on 3 test cases
becoz its bipartite graph problem
hmm got it, my bad, idk how it passed 24 test cases lol
i implement detection of cycle graph as well , i got 24 tests AC and only 3 WA.
can you give a counter example where detection of cycle graph is not working ?
cycle will not work if you have cycle of odd length
Just check for bipartiteness for the nodes given in the sequences for each component also make a check for S[i] == T[i] as that also leads to a no answer. Nothing more required.
In D, you have to tell if the graph formed by the edges $$$(X_{A_i}, X_{B_j})$$$ is bipartite or not. Note that, even cycles are also bipartite graphs.
were you finding cycles of all lengths or only odd lengths ?
it works for even cycles (and not for odd ones) so just because a cycle exists doesn't mean the ans should be no
I only WA on 3 tests!What a pity!
I think F is a famous problem in Luogu named "Stars in the Window".
Problem's link:https://www.luogu.com.cn/problem/P1502.
How to solve E?
Why does my D-question program have a test point wrong? I treat a[i] and b[i] as two nodes of a graph to determine whether they are bipartite graphs. https://atcoder.jp/contests/abc327/submissions/47266143
https://atcoder.jp/contests/abc327/submissions/47276048 Added 1 line in your code
Thanks.
I liked the overall problem set !!
D and F were my favorite. However, it would have been better if the input in F were like $$$X_i, T_i$$$ instead of $$$T_i, X_i$$$, got some wa's due to that lol.
Why does this give wrong answer on 3 cases? submission
for (lli i = 1; i <= N; i++) { for (lli j = 1; j <= N; j++) { dp[i][j] = max(dp[i-1][j], 0.9*dp[i-1][j-1] + P[i]); } } Here, I think $$$j$$$ should loop from $$$1$$$ to $$$i$$$ (instead of $$$N$$$).
bfsof Orz! This is not the main reason. The main reason that this guy misses the cases where $$$j=0$$$ for $$$i \geq 1$$$.
Corrected here: https://atcoder.jp/contests/abc327/submissions/47279921
I am failing the same 3 test cases even after checking for $$$K = 0$$$ case. I suspect it is due to some overflow / precision issues, or something in my implementation.
https://atcoder.jp/contests/abc327/submissions/47281611
Isn't case j=0 already covered when I made the dp array?
you omitted the case dp[i][0] is transferree from dp[i-1][0].
Lesson learnt. On AtCoder, I can try
unordered_mapwhenmapcauses TLE. I didn't do so so far because on Codeforces,unordered_mapis subjected to hacking. On AtCoder, there is no such concern.My TLE solution on E with
map: submissionMy AC solution on E with
unordered_map: submissionI ended up replacing the
mapbyvectorduring contest though.How to send a solution
did i have to know bipartite graphs and segment trees to tackle d,e,f and g?
No need for e
Pls explain why f cannot be solved using map<int, vector> and then lower bound etc
G need 30 rows, but A117279 only provides 25 rows....
Same :(
In task E, can someone explain why picking maximum K elements for each k greedily doesn't work ????
Order of the performance numbers matters. It is a penalty when the performance numbers show a downwards trend.
In G — Many Good Tuple Problems Editorial(English Version)
g(n,m):= (the number of simple connected graphs with n vertices and m edges, where each vertex is painted either white or black, and no edge connects vertices with the same color).
should be
h(n,m):= (the number of simple connected graphs with n vertices and m edges, where each vertex is painted either white or black, and no edge connects vertices with the same color).
And I think that the calculation formula for $$$f(n, m)$$$ should be
I think you are right cause C(n-1,i-1) are not symmetric about n. Maybe just a typo.
Also 'b(M,k) equals M! times the Stirling number of the second kind, S(M,k)' should be k! times S(M,k) right?
Why wasn't my rating changing!!!
can some one point out what is wrong in my code . It's failing on 4 test cases.Your text to link here...
E's solution is dp, right guys?
yes.
easier than 325,326,but still cant do D.
HELP, Anyone can explain the F solution? Editorials become somewhat complex to understand. Just explain the part, what you are storing, updating, query..... in the data structure, and why.