We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2023(AtCoder Beginner Contest 299).
- Contest URL: https://atcoder.jp/contests/abc299
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230422T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: leaf1415, MMNMM, evima, Nyaan
- Tester: math957963, PCTprobability
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
We have implemented a contest mode for our DDoS protection. Please read the following article before starting the contest.
we cannot access standings during ABC/ARC/AGC/AHC but can access standings after the contest ends right?
I sometimes use the number of accepted solutions to predict the difficulty of a problem. Oh...
Why can't we access standings during contest? Is it because of it takes a lot of load or sth?
I guess that AT rating predictors are useless now xD
Really useless indeed, now that every contest is unrated.
Not being able to access standings during the contest really sucks!
Can we see number of accepted submissions for a particular problem???
+
At least consider this
I don't understand how not being able to view standings protects against DDoS
502 again:(
Is the platform stable enough? why 502 all the time?
Why 502? Does the contest mode work?
502 Bad Gateway?? I thought you guys added DDoS protection.
Edit: I can still view standings btw.
Obviously the hackers are targeting at the Atcoder. I think it would be better to extend some time and publish the problems here instead of just making unrated. And, add cloudflare please!
Unrated again :(
Why are people attacking AtCoder? Do they really have nothing better to do?
I think they are targeting at Chokudai. After Chokudai announces the improvement of the Anti-DDOS system, the attackers want to "show up" their muscles.
The contest mode doesn't work...
Unrated???!! Two weeks in a row! I wait the entire week to give contest and now both weeks were wasted. Its not like other sites where contests are held multiple times a week, only one contest a week for which we clear our schedules. There should have been an improvement after the last contest got unrated. Both atcoder and codeforces need to have some serious server upgrades.
Stop caring about your rating
Whenever my contest is going good
Le Atcoder: Lets make it unrated
Same!! Thats why I am so angry, last week might have been a mistake but they should have been prepared this time. Atcoder holds only one or two contests a week, not easy to free time on weekends to attend these. This is completely unacceptable
likely half of the rage are the ones who got notified of the contest going unrated while they were doing well, and the other half are the ones whose mindset got fucked by a hundred 502s
Another unrated. Nooooooooooooo
If the problem of DDOS on the programming competition platform cannot be solved, it will affect the entire programming competition field. I hope AtCoder can resolve this issue as soon as possible and provide a better participation experience for the vast number of participants.
How to solve problem G? My idea was something like this :
Define $$$cnt_i$$$ : number of unique element from $$$i, i+1, ..., n$$$
Now we iterate through $$$i$$$ from $$$1, 2, ..., n$$$ and do the following :
We can add $$$A_i$$$ to $$$B$$$ if and only if :
So I'm searching an interval using a binary search for an index $$$j$$$ such that all numbers between $$$i$$$ and $$$j$$$ are add-able to $$$B$$$
Pick the minimum index $$$idx$$$ between $$$i$$$ and $$$j$$$ (inclusive) such that $$$A_{idx}$$$ has the smallest value between $$$A_i, A_{i+1}, ..., A_j$$$
Add $$$A_{idx}$$$ to $$$B$$$
Since we're taking $$$A_{idx}$$$ to $$$B$$$, therefore we can find the rightmost position of $$$A_{idx}$$$. Name this index as $$$last$$$, then we can subtract $$$cnt_{last}, cnt_{last+1}, ..., cnt_n$$$ (since now one element is taken to $$$B$$$, therefore number of unique element is decreased)
But I'm getting WA https://atcoder.jp/contests/abc299/submissions/40877152
Could someone point out : 1. The mistake on my idea 2. The bug on my code if my idea is correct ?
Does problem F require DP or there exists a non DP solution?
Problem G is a nice implementation problem
It is very similar to this problem: remove duplicate letters
In the problem E, Nearest Black Vertex, how they are claiming this
“The minimum distance from vertex v to a black vertex is exactly d” if and only if “there is a black vertex whose distance from vertex v is less than or equal to d” and “there is a black vertex whose distance from vertex v is strictly less than d.”
I am not getting this, could someone help me with this problem . As of now i have done kind of brute force stuff My Solution
it should be “there is no black vertex whose distance from vertex v is strictly less than d.”
Thanks for clarification, That was my interpretation too.
What i did is that
I know this will give TLE as for a pair of (node,dist) we have checking for all d < dist if we have a black node or not but dont know how to optimize that
Any help is appreciated. Thank you
I would suggest understanding the editorial
I think problem F is very difficult for me, and I still can not fully understand the editorials. Would anyone like to share your ideas about this problem? Thank you so much.
Maybe I'm a bit late but I'm sharing my solution anyways since it is a bit different from the editorial and I thought it was simplier. Maybe if you understand mine the editorial will be easier.
The editorial restricts the problem with a procedure, a procedure in which we will always extract the left-most characters of $$$S$$$ as we check for a subsequence.
In that way for each string $$$T$$$ there will be a unique pair $$$(i, j)$$$ of positions of $$$S$$$ that will be picked when forming a subsequence of $$$TT$$$ and will correspond to the positions of the first characters of each $$$T$$$ in the said procedure. In particular $$$i$$$ will be the first occurence of the first character of $$$T$$$, so the important part is $$$j$$$.
Now when counting $$$T$$$ we know that it will correspond to a specific $$$j$$$. Finding all such $$$T$$$ for a specific $$$j$$$ and summing up is now possible, since doing so we will eventually cover all strings.
Let $$$n_c(i)$$$ be the index of the first occurence of $$$c$$$ in $$$S[i\dots N]$$$ ($$$N = |S|$$$)
Also let $$$I(c)$$$ be the array/set of all indices $$$i$$$ such that $$$S[i] = c$$$.
The main idea is that we want to count the number of strings $$$T$$$ such that $$$TT$$$ is a subsequence of $$$S$$$ and which start with $$$c\in\Sigma = \{a, \dots, z\}$$$, and we will sum the answers iterating $$$c$$$ through all of $$$\Sigma$$$.
Obviously if $$$T=cT'$$$ then $$$TT=cT'cT'$$$ so if $$$TT$$$ is a subsequence of $$$S$$$ then there is a pair $$$(i, j)$$$ with $$$i<j$$$ such that $$$S[i], S[j]$$$ are the first character of each $$$T$$$ in $$$TT$$$. Wlog we can assume that for finding a subsequence for $$$TT=cT'cT'$$$, we will always pick the first $$$c$$$ of $$$S$$$ so $$$i=i_0=n_c(1)$$$ in that pair (and it is fixed).
(Note that we will overcount, but will sieve later)
Let's iterate through all $$$j\in I(c)\setminus \{i_0\}$$$ (through all other positions of $$$c$$$). We fix $$$j$$$, now if $$$(i_0,j)$$$ is the pair corresponding to the first $$$c$$$-characters of each of $$$T$$$ in $$$TT$$$ then how many different $$$T'$$$ are there such that $$$TT = cT'cT'$$$ is a subsequence of $$$S$$$? First of all we can count the case where $$$T' = \emptyset$$$ but then there may be non-empty $$$T'$$$. Notice that the first $$$T'$$$ will be a subsequence of $$$S[i_0+1\dots j-1]$$$ and the second will be a subsequence of $$$S[j+1\dots N]$$$, in fact we can count all such strings and each one of those will result in a different $$$TT$$$. It is easier to count such strings than in the original problem since the segments for each repetiotion of $$$T'$$$ are disjoint. There are $$$G_{j-1}(i_0+1, j+1)$$$ such strings, where $$$G: [N]^3 \to \mathbb{Z}$$$ is defined as follows:
Let $$$G_m(i, j) = ($$$number of strings $$$T'$$$ such that $$$T'$$$ is a subsequence of both $$$S[i\dots m]$$$ and $$$S[j\dots N])$$$ We can recursively compute the function as
by applying same logic as before, i.e count the number of strings for each different starting character $c$, but now we will suppose that we pick the first occurence of that character in each of the two disjoint segments in the procedure of finding subsequences. That way we will not overcount in the computation of $$$G$$$. The total computation time is $$$\Theta (|\Sigma|N^3)$$$ [ $$$=\Theta (N^3)$$$ since $$$|S|=26$$$ ] which is the most costly part of the solution and so the solution itself has the same time complexity, which is identical to the editorial.
Just summing the answers for pairs $$$(i_0, j)$$$ will result in overcounting. How much? Suppose that for a character $$$c$$$ (and $$$i_0 = n_c(1)$$$) you count the contribution of the pairs $$$(i_0, j)$$$ and $$$(i_0, k)$$$ with $$$i_0 < j < k$$$. Every string $$$T'$$$ will be counted in both cases if and only if it is a subsequence of $$$S[i_0+1\dots j-1]$$$ and $$$S[k+1\dots N]$$$ (you can draw a picture to see this, even though it seems trivial I was confused about this at first).
So in order to count the number of string $$$T$$$ in the original problem we can do the following
For each $$$c\in\Sigma$$$ ($$$i_0 := n_c(1)$$$) iterate $$$i$$$ through all positions of $$$c$$$ (excluding $$$i_0$$$) from smallest to largest and add the "overcounted contribution" of the pair $$$(i_0, i)$$$ as described with the function $$$G$$$. After the first iteration of $$$i$$$ we will also remove the contribution we may had also counted with the previous pair as described above. Doing so, one can prove that in each stage of iteration of $$$i$$$ we will not have overcounted, and we will eventually count all strings starting with the character $$$c$$$ (since each string will corespond to some pair $$$(i_0, \cdot)$$$.
Here is my submission where I use more or less the same notation (maybe with some minor differences).
This solutions is awesome, your intuition is very natural as opposed to the editorial's solution.
I think there's been some miscommunication. Standings page was clearly visible for the duration of the contest! It's sad that the round went unrated. I don't know the reason for the DDOS, but could it be related to the round being sponsored? Both this and previous round were sponsored rounds, so maybe next one won't be targeted? In any case, AtCoder would need some stronger mechanism to deter the DDOS attack. CF added cloudflare check, but it's terrible right now, it slows access to contest pages, and checks every time you open a link. It's also costly. I hope there's some other way to solve this problem.
Actually the upcoming ABC is also sponsored, by UNIQUE VISION this time*
I don't think it is straightforward to have an optimal solution for anti-DDOS unless some experienced experts exist in AtCoder. Imagine in a real company what a anti-DDOS project would cost? I guess the development cycle is surely longer than one week. Just give them some time. But I still don't get how/why AtCoder is the target. Maybe attack is aimless.
I don't think so. They grasped the contest time so accurately. They started attacking after the contest and stop attacking just after the contest is announced unrated. That is the cheapest way. Besides, these guys do not give chokudai any chance to test the real-world attacks during the contests. The more countermeasures chokudai take, the more AtCoder would be attacked, the hackers (actually script guys) are showing off their muscles. If I were chokudai, I would publish the PDF version files on CF, dropbox. When the attacks happen, just extend some time.
Any simple explanation for problem F?
Maybe Knapsack.
During ABC, ARC, AGC, and some AHC contests, access to all pages except for the contest will be restricted.
Does that mean we can view the standings of the running contest, but not past contests?