We will hold AtCoder Beginner Contest 445.
- Contest URL: https://atcoder.jp/contests/abc445
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20260214T2100&p1=248
- Duration: 100 minutes
- Writer: KumaTachiRen, MMNMM, sheyasutaka
- Tester: physics0523, yuto1115
- Rated range: ~ 1999
- The point values: 100-200-300-425-475-500-600
We are looking forward to your participation!
First!
Second!
Third!
gl hf
RP++
Oh! AC abcde My rated is 1174 now!My rated is 1200+ after it.
F is similar to https://mirror.codeforces.com/gym/102644/problem/F
Good contest. $$$D$$$ and $$$E$$$ were good problems. How to solve $$$F$$$? It seems to be pretty easy or a well-known idea, judging by the solve count.
Well it's Luogu P2886
Consider the problem of finding the amount of paths from i to j with exactly k edges. This can be solved by finding the entrance i,j in the k-th power of the adjacency matrix. It is possible to adapt this idea.
Use as base the matrix in which the entrance (i,j) is the cost to go from i to j. Then, define a different operation (instead of the usual product) to apply the matrix exponentiation. Basically, to go from A^k to A^(2k) for each entrance i,j you need to find what is the minimum cost, which can be found by: minimum cost going from i to q in k moves + minimum cost going from q to j in k moves, iterate over q.
It's on CSES https://cses.fi/problemset/task/1724
Just instead of A^k[1][n] I print A^k[i][i] for each i
Screencast:
https://www.youtube.com/watch?v=JMyNwDUs-yo
Thanks!
What is the worst case for the sum of sum of ones in binary representation of all divisors of $$$k (1 \lt = k \lt = 10^9)$$$? I wrote solution in F that works $$$O(n^3*X)$$$, where $$$X$$$ is the sum I mentioned before. (My submission)
UPD: I figured out, that instead of using all divisors, I could just used $$$k$$$. But the solution above also passed.
1344 for k<=1e9, Refer here for different limits.
Yeah, I know that number of divisors is $$$O(\sqrt[3]{k})$$$. But I also interested in sum of ones in binary representation.
For example: k = 6
1: 001, number of ones is 1
2: 010, 1
3: 011, 2
6: 110, 2
So, $$$X = 1 + 1 + 2 + 2 = 6$$$. It seems in the worst case my solution should work in $$$O(n^{3} \sqrt[3]{k} \log{k})$$$ and get TL. Yeah, $$$O(n^3 \sqrt[3]{n})$$$ also shouldn't pass. (probably it passed, because of weak test cases).
Didnt solved even c Cuz i <= ai<=n I didnt saw lol
same, I didnt saw it and just start thinking about the binary representation of 10**100, trying to find pattern in base 2 representation of power 10, and many more not work idea :)
Same i was thinking hoe to solve it using binary lifting and having problem With 10^100
its strange how a simple constraint change guaranteed that every cycle Will have Ai = i
I did solved it using binary lifting..
yeah it will work just take d = 333 if you know that constraint is i <= ai <= n
if not then you must use some logic to convert 10^100 into binary which i dont know how , maybe you have some insight on it
Instead of jumping on progressive powers of 2, I jumped on progressive powers of 10. Solution link
Damn
I might be wrong but this soln only passed due to it applying 2^100 operation If there were no constraint Like i<=ai<=n this would not have passed
Yes, you are right. Although, we can still convert 10^100 into binary by storing them as strings and then apply binary lifting
Can someone please help me understand this MLE submission on E?
Initital submission
Tried some optimizations
in C . what if array is [ 3 1 2 4 ] ?
That's an invalid input, for each i, i <= a_i <= N
:) shit
omg this trap !!
This garantie there is no cycle. Why this not mention in editorial ?
It's still solvable but much more complex.
i solved the hard version.. i read it 1 <= Ai in stead of i<= Ai..
with help of python I got the bit representation of 10^100 && then using sparse table solved the problem..
in C i didn't see the (i <= Ai) during the contest.. still somehow solved it..
Yeah.., I too solved it using binary lifting, lol
It is the easiest Problem F in the ABC. AND D is much harder than F.
D has a similar idea to this problem.
How to do the division with mod stuff in E after taking LCM of all numbers? They are using their inbuilt library in editorial so no info. Btw great contest.
I found the questions to be fun atleast the A and B. I am rated 45 before the contest and now 78 as I solved A and B is 11:18 minutes, it was like a record time for me.
HI!!!!!!!!!!!!!!!!!!!!
hi
Is really interesting bro
not first, second and third
C just missed one test case to get the score, so frustrating!
do we get editorial for ABCs?
edited
i <= A[i] <= N, so the number on a cell is either that cell or a cell in front of it; you won't go backwards and won't have a test case like 3 1 2 because of this.