We will hold AtCoder Grand Contest 039. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc039
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20191005T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 6
- Writer: DEGwer
- Rated range: All
The point values will be announced later.
We are looking forward to your participation!
hope to solve even one problem in AGC...
Is it so hard for my level?
Roughly speaking, the difficulty of AGC is similar to that of CF Div1.
That's not true :)
Is AGC harder?
In my opinion, yes.
may you success
I solved A & B, thank you!
my solves are same to you
Problems in AGC are too much "Thinking oriented".
Usually the first problem in AGC is very easy.
As Swistakk in the previous AGC can attest. Same with me and AGC034.
Hope to solve A in AGC...
.
any similar problem like A?? thanks in advance
this problem helped me solve A: 1108D - Diverse Garland
How to solve B ?
Do bfs by starting a node in first set.
For B, I think the important observation is this: if I have a odd cycle, the condition can never be fulfilled as if we assume that one of the nodes, v, is in partition k, we must get k by adding or subtracting 1 an odd number of times from k to satisfy the condition stated in the question, which is impossible. Hence, I run an algorithm to check for odd cycle (bipartite checking). Then, I claim that the maximum possible value of k is the diameter of the graph, as in the longest "shortest path" between two nodes in a graph. The proof of this requires the assumption of the following lemma: if I put node x in partition 1, the largest partition number is the distance of the furthest node from node x. Thus, I simply run Floyd-Warshall's algorithm to solve this problem.
https://atcoder.jp/contests/agc039/submissions/7862739 (my code)
The same conclusion is that the answer is satisfied when the graph is a bipartite graph. Maybe it's easier to understand.
Hello, I have encountered really strange bug.
When I submitting simple below code on AtCoder, it gives RTE.
--------------- # pragma GCC optimize ("O3")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
int main(void) {
queue<int> q;
}
(https://ideone.com/grUdW7/ to highlight)
Atcoder uses
g++ -std=gnu++1y -O2 -I/opt/boost/gcc/include -L/opt/boost/gcc/lib -o ./a.out ./Main.cppcommand to compile and gcc version is 5.4.1It seems pragma option conflict with STL queue or stack but I cannot understand what's going on. Also, it works well in gcc version 5.4.0 and 8.1.0. Is there anyone who knows the reason?
The AtCoder server probably does not have a CPU that supports
avx2instructions (it may be too old), so it probably is getting RTE from an illegal instruction.Funny thing: I tried #pragma GCC target("avx2") recently in custom test and it worked fine, the code was even faster so it couldn't have been noop'd. The CPUs there could have been different though.
Thank you for your kind explanation!
Omg, D was so hard x_0. Took me 1,5h. Then thought for a few minutes about E which turned out to be really easy dp which I did in sth like 20 mins xd.
how to solve A..
Solve for $$$f(s)$$$,
Unable to parse markup [type=CF_MATHJAX]
andUnable to parse markup [type=CF_MATHJAX]
separately. That helps in knowing how much extra cost you have to pay for addingUnable to parse markup [type=CF_MATHJAX]
to $$$s$$$ (fromUnable to parse markup [type=CF_MATHJAX]
— $$$f(s)$$$). Now how manyUnable to parse markup [type=CF_MATHJAX]
is needed to get $$$(k-1)$$$ copies? Add them. If you still need one more s to add (since $$$k$$$ is even), addUnable to parse markup [type=CF_MATHJAX]
— $$$f(s)$$$Yes, and by a similar argument, you can see Berlekamp-Massey also works. But the greatest thing of BM is that you never have to argue it works :)) my code
C was hard too, in 2 hours I could only figure out I had to check odd factors of $$$N$$$ (each odd factors had
Unable to parse markup [type=CF_MATHJAX]
as answer butUnable to parse markup [type=CF_MATHJAX]
times if even andUnable to parse markup [type=CF_MATHJAX]
times if odd) but then the problem of counting upto $$$X$$$ needed more pattern to be observed.How to solve A,I don’t think I’m right.So Sad that I have 10 wrong submissions .
If you got $$$AC$$$ you are right as systest happen during the contest not later.
Apparently, D is formula bashing. Why????
Basically, for each point $$$A$$$ and each pair of other points
Unable to parse markup [type=CF_MATHJAX]
, we want to sum upUnable to parse markup [type=CF_MATHJAX]
and take their average to get the $$$x$$$-coordinate of the incircle. This is just using a standard formula. We can fix
Unable to parse markup [type=CF_MATHJAX]
, rotate the circle so that pointUnable to parse markup [type=CF_MATHJAX]
is $$$(1, 0)$$$, find the average of the $$$x$$$-formula for this fixedUnable to parse markup [type=CF_MATHJAX]
(soUnable to parse markup [type=CF_MATHJAX]
), de-rotate to get some pointUnable to parse markup [type=CF_MATHJAX]
and take the average of these points to find the resulting pointUnable to parse markup [type=CF_MATHJAX]
.Since the points lie on a circle and
Unable to parse markup [type=CF_MATHJAX]
is fixed, we can use the angle between pointsUnable to parse markup [type=CF_MATHJAX]
(angle $$$x$$$) and between pointsUnable to parse markup [type=CF_MATHJAX]
(angle $$$y$$$) instead. Then,Unable to parse markup [type=CF_MATHJAX]
,Unable to parse markup [type=CF_MATHJAX]
andUnable to parse markup [type=CF_MATHJAX]
. Simplifying with sum formulas,Unable to parse markup [type=CF_MATHJAX]
Unable to parse markup [type=CF_MATHJAX]
which is
Unable to parse markup [type=CF_MATHJAX]
; finding the average of this over allUnable to parse markup [type=CF_MATHJAX]
, $$$x \neq y$$$ is reasonably simple, since the tangents are now independent, but reaching this point is ew.UPD: Ok, the last part is a bit more complicated since we need to watch out for how we choose angles $$$x$$$ and $$$y$$$. Let's say that
Unable to parse markup [type=CF_MATHJAX]
; points with angle $$$\pi$$$ can be handled separately. IfUnable to parse markup [type=CF_MATHJAX]
andUnable to parse markup [type=CF_MATHJAX]
are both on the same side (Unable to parse markup [type=CF_MATHJAX]
is obtuse), then we needUnable to parse markup [type=CF_MATHJAX]
instead of $$$y$$$, which just means we divide byUnable to parse markup [type=CF_MATHJAX]
instead of multiplying. The code is still simple though.There is a somewhat obscure olympic-math-folklore theorem that renders the problem trivial. The correct search engine query is "incenter complex numbers".
I absolutely dislike problem D tbh. Is there any solution that doesn't use bashing or some obscure knowledge about MO geometry? (I think your "standard formula" is obscure enough, but it may be standard for some)
There's a simpler formulation (this can be found in v_Enhance's whitepaper at http://web.evanchen.cc/handouts/cmplx/en-cmplx.pdf).
Lemma 1: For any three points $$$a,b,c$$$ on the complex unit circle ($$$\lvert a \rvert = \lvert b \rvert = \lvert c \rvert = 1$$$), the circumcenter is $$$0$$$ (by the unit circle), the centroid is $$$(a+b+c)/3$$$ (by center-of-mass), and the orthocenter is $$$a+b+c$$$ (by the Euler line, or alternatively by checking perpendicularity).
Now, consider the incenter $$$I$$$ of triangle $$$ABC$$$. Note that $$$AI$$$ is an angle bisector; let it intersect the circumcircle at $$$D$$$. Then, $$$D$$$ must be the midpoint of arc $$$BC$$$, because it's an angle bisector. If we define $$$E$$$ and $$$F$$$ symmetric, we can show with a simple angle-chase that $$$I$$$ is the orthocenter of $$$DEF$$$. Thus, by the lemma, we're just trying to find the expected value of sum of the midpoints of the arcs $$$AB$$$, $$$BC$$$, and $$$CA$$$. The rest is just probability.
These are the kind of observations that most skilled programmers wouldn't guess without experience in synthetic math. You can also guess right away that the answer is the sum of midpoints. It's nice when said like this, but to find "what kind of point is this?" instead of showing "it's this point", you need to try out special points one by one and hope it works, or just bash out the coordinates.
Yeah, this is relatively well known MO geometry, so there's a huge advantage for people who've seen this before, particularly if you've learned how to complex-bash.
There are cool facts for $$$n=4$$$ Link, which i think is the motivation of this problem. I found them by google search and i think its cool. I also had a solution based on that.
When $$$n=4$$$, plot the points $$$A,B,C,D$$$ in complex plane. Then the answer is the intersection of two lines, one passes through $$$A \times B$$$ and $$$C \times D$$$ ($$$\times$$$ is multiplication), another passes through $$$A \times D$$$ and $$$C \times B$$$. Also, these two lines are perpendicular. We can do some simple deduction and realise that the answer is $$$(AB+BC+CD+DA)/2$$$
For $$$n \geq 4$$$, we can just count the average of the above value for any 4 points, so we can just count the contribution to the answer for every pair of points in $$$O(n^2)$$$
For $$$n = 3$$$, just copy formula from somewhere :P $$$n=3$$$ was hardest for me...
Hmm, can't you use your solution for n=4 for points A, A, B, C in order to get solutions for points A, B, C? You have 4 incenters, two of them are incenters of ABC, two of them are A.
Was this some test if a person calculates geometry in complex numbers often?
That gave me back my 2013 :)
You can deal without complex numbers but I don't know if that's simpler.
I've read your comment, complex numbers solution is significantly simpler
Dude, wat o0? That code is even much shorter than mine.
If $$$0\leq\varphi_1<\varphi_2<\varphi_3<2\pi$$$, and $$$a = \exp(i\varphi_1)$$$, $$$b = \exp(i\varphi_2)$$$, $$$c = \exp(i\varphi_3)$$$, then
is the incenter of the triangle with vertices $$$a$$$, $$$b$$$ and $$$c$$$.
I don't mean code. I mean ideas, how to arrive at that point. The code based on my comment's conclusion is also very short.
In order to not be misunderstood, I actually really liked D. I think my code is short, cute and neither my code nor my solving process included any formula bashing or complex numbers (I mean, I tried some formula bashing but that led to nothing, what I needed was math olympiad style insight). But it just seems much harder to me than 1000 pt and I am amazed by how fast some people got this right.
EDIT: My solution is based on a very common trefoil lemma: https://en.wikipedia.org/wiki/Trillium_theorem (it's super basic fact) Key insight that follows from this + some angle chasing is that the thing that we need to accumulate is sum of points on the interval with angles halved. After we get it we just do some rotations, scaling and translations. My code can be found here: https://atcoder.jp/contests/agc039/submissions/7873571 (mentioning ko_osaga , you may be interested)
Now I realized that I don't even know super basic fact :(
I also have math olympiad style insight. The insight in geometry is called choosing a good coordinate system that makes the crazy calculations less crazy :D
This isn't by far the worst geometry I've bashed, it didn't take hours (plural). When I was at IMO, there was an easy-level geometry problem. I didn't even bother thinking about some nice theorems and just started by writing out all formulas that seemed meaningful. That wasn't the hardest geometry I've bashed either and it only took hours because of triplechecking.
I'm fine with this problem being in the contest, but it should've been placed higher and I don't like it for the same reason as "transform into linear program, copy-paste ILP solver" problems or FFT back in ye days of olde: you need to know some very specific theory, like your background in olympiad (synthetic) math, to arrive at the main point, and the rest is easy — or you need to derive that theory from scratch. It just doesn't give anything to people who don't know that theory because it's so obscure it's not worth remembering and it doesn't give anything to people who know it because they know it. I'm in the best position to learn something actually useful from this problem and it's still just that sum of sines can simplify to something reasonably nice.
UPD: I've never heard of Trillium lemma in all my math-surrounded life.
I prefer solving problems about world history rather than OM geometry
by going back in time?
Well, I prefer solving problems about world history rather than ones about strings and data structures
I consider competitive programming as a way to practice discrete algorithms and CS theory, but it's just my philosophy, and market will decide :)
And this partly explains why I consider AGC as overrated.
I prefer to solve other types of problems, like at ICPC or IOI too, but probably it is just because I too stupid for AGC.
Me too. At least, I don't want study about some complex formula of triangle...
I think it's fine that different contest sites have different tastes of problems. You can participate in the ones you like.
Anyway, as long as I'm the admin of AtCoder, math problems will appear in AGC, and implementation / data structures / world history problems won't appear in AGC. If you have specific topic you want to see in AtCoder, please let me know!
Even if you recieve good data structures problems, you still won't use them?
A well-known source in the US on this lemma: http://web.evanchen.cc/handouts/Fact5/Fact5.pdf
(linking v_Enhance twice in the same thread :O)
Now let’s select all points uniformly inside the unit circle, N up to 10^100 :)
Well, I knew D will be controversy, but I liked it a lot and decided to use it in AGC.
This is very easy to code, no advanced knowledge is required (just high school math), and all you need to do is to think on paper. It perfectly matches AGC's style.
There are four topics in IMO: A(lgebra), C(ombonatorics), G(eometry), N(umber Theory). C and N frequently appear in competitive programming. I tried A here. And now this problem is a nice way to use IMO-style G in competitive programming.
Yes, this is solvable both by elementary geometry or bashing, just like other IMO-G problems.
Mathematical Olympiad math. It would be high school math if $$$O(N^3)$$$ was enough. Calculating distances between points on a circle is high school math. The existence of an incircle is high school math, the formula for coordinates of the incenter is on the edge of college math. How many high schools even teach that there are summation formulas for sin/cos?
Everything that has ever been solved is solvable only using elementary knowledge, given enough centuries. You're downplaying the difficulty. If you mention this problem side by side with IMO problems, then people should be at IMO level to solve it. That's not an insanely high level but it's still pretty high.
This is a situation where someone who's badass at IMO will see the solution as much easier than someone who isn't because they see advanced knowledge as basic.
Mfw our high schools here teach summation formulas for sin/cos but never talked about the existence of incenter (or any other triangle center tbh)
I attended a high school for gifted students in STEM fields in Korea. I can confirm that none of that OM geometry madness is in my school curriculum.
On the other hand, we do learn what is incenter/circumcenter in grade 8, and the summation formula for sin/cos is taught in grade 10~11 math class, for all high school students in Korea.
(I'm sorry for calling it "OM geometry". I just don't know how to call that kind of geometry. In Korean it's called "logical argument geometry" (논증기하))
Maybe call it Euclidean geometry XD
Synthetic geometry (as opposed to analytical geometry) is the term I know. The theorems it uses are a synthesis of other theorems or analytical statements to reach conclusions expressible in normal language.
East Asian countries have more advanced high school math, probably all other countries have less and many probably don't have as much even in private schools or schools for exceptional individuals. As a reasonable median, I'm taking what used to be taught in Slovak schools some years ago, since I've heard about as many "that was easier than X now" as "that was harder than X now" comparisons — a lot of years ago, summation formulas would've clearly been there near graduation, now they clearly aren't, so it's currently borderline material. Math in countries that are trying hard to become more modern (like here) keeps dropping...
Clearly yes. And it's good sometimes, but I think it's too off. Learning about synthetic geometry (thanks!) in 8th grade is the biggest reason why I hated math until going to university.
People who know Segment Tree have huge advantage on people who don't in problems on Segment Tree. You don't have problems with this, right? So, the only difference is that YOU consider school geometry out of your imaginary CP Syllabus and Segment tree in.
Of course this problem is easier for rng_58 and AtCoder writers (sorry, I'm not sure if DEGwer is an IMO medalist or not). But they don't have other means of estimating difficulty (and points) of a problem.
Can you give me an estimate of the ratio of problems about segment trees to problems about IMO-style geometry?
So the problem is just they are rare? Guys, we need more problems on IMO-style geometry so Xellos will have motivation to learn it.
Well, yeah. When an advanced topic is becoming common in CP, then it's totally fine to use it in CP problems. If geometry problems became more on synthetic math and less on tricky case handling and precision handling and long ugly formulas, I'd gladly learn synthetic geometry.
The way it stands now, I successfully bashed out that I need sums of tangents and sums of squares of tangents without any math insight. If I encountered a similar problem again, I'd bash out a formula again, just with more confidence. Looking for a nicer solution isn't worth the extra effort.
Aside from that, seems like you're admitting that I'm not applying a purely subjective standard to what problems are suitable for programming contests.
One of the reasons why I put this problem is that this fact is not widely known in CP community. I think elementary geometry can be suitable for CP format (like the construction problems with no algorithmic operations are widely accepted) but the community doesn't know much about elementary geometry. I wanted to "import" the knowledge in MO to present another possible direction of the problems in CP.
Sure. That's totally fine, although I'm not sure if such problems could catch on. It should've definitely been swapped with E though — as I mentioned, it's easy to misjudge the difficulty for someone with experience in IMO-style geometry.
Generally, it is very difficult to correctly estimate the difficulty of te problems. It very often occurs that higher-scored problems are solved more. Thus saying like "the problem X should have aligned before the problem Y" after the contest doesn't make sense.
And in this case, D is solved more than E. Yes, I agree that large percentages of people who solved D has MO-background. But CP is open for the people with arbitrary backgrounds, so "difficult for non-MO background people" is not a reason of that the difficulty should be too highly estimated.
D is solved more than E because more people read D and don't read E. If they were flipped, the current E would have more solutions simply because more people would try to solve it.
This is just your feeling. It is not clear what happened when D and E are swapped. E is not straightforward when people believes that the intended solution requires exponential time. It seems easy just for the people who are used to high-dimensional DP.
No, it's more than that. The solution combines common concepts — tree DP and DP on a circle, where you need to observe that each range of points is a subtree (states: subtree, its root = range, point inside it) and that for each subtree, we can pick a pair of its rooted subtrees at the borders of the corresponding range. With problems about connecting points on a circle, DP with state = range of points is a very common approach. That's perfectly fine as a 1000-pt D in an AGC contest. When I compare to last contest's D, it seems even easier. Plus, the code is also short, there aren't any tricky cases, special handling of something in DP, you don't even need to think about cyclic ranges "l..r" where l > r, so you can't argue that D is simpler to implement.
D is even more "not straightforward" when people believe that the intended solution doesn't require olympiad math (including the formula bashing approach), which is an assumption that's much easier to make since how many people even know olympiad math compared to 3-dimensional (the number of states) DP?
Every problem is hard to solve when you work from a wrong assumption. What are you even trying to say by that?
Your arguments are completely meaningless. People who managed to solve the problem tends to say that is easy. The combination of basic techniques may produce difficult problems, when many people do not aware of the problem structures. Explaining "why this should be easy" is easy. Yes, according to your argument, E seems easy. When people read the editorials, people will think E is easy. But during the contest, there are no editorials. You said E is less solved because E is latter than D, but I don't sure what happened when they are swapped: And even if the new D is solved more than the new E, according to your argument, that is not a proof of that new D is easier, is it?
Generally judging the difficulty of the problems is a difficult task. When this happens, I confirm E is easier than D. But in this case, the relation of difficulties are not clear.
Every single one of my arguments ever is more meaningful than this.
I solved C during the contest and I think it's kinda hard for C. Same with A. Yet you're implying that if I solve a problem, it makes my view on it somehow invalid? WTF?
Yes, and I don't believe it's the case here (or in D, for that matter).
Not at all. Assessing problem difficulty is a difficult skill to learn just like solving problems or making problems.
My argument is basically "first ideas when I tried to solve it". I definitely didn't need the editorial — that would, of course, warp my view on difficulty.
We could judge based on the change in the number of solutions for D and the change for E if they'd be consistent (more for D, less for E when swapped), but yeah, we can't know that anyway.
The funny thing is that AGC034 D is about transforming the problem into a theoretical thing with often copypasted solver (mincost maxflow), so it's also harder due to requring knowledge of some specific theory.
I don’t think any sane people will try exponential solution when 2N <= 40. Anyway thanks for EF. I think they are interesting.
Have you heard about meet-in-the-middle? Algorithms with complexity depending on number of partitions of $$$n$$$? Some clever observations that reduce the number in the exponent? I once saw a problem with limitations like $$$n \le 300$$$ which had non-polynomial complexity.
Well, that sounds like very productive thinking.
Xellos rng58 is imo gold medalist 3 times. so its very easy for him. thats why they look to him like high school maths
If he really thought it is easy for competitive programmers, he should have made it 500-pt problem.
This argument doesn't make sense.
My opinion is:
I don't agree with the opinion that MO problem shouldn't appear in CP contest.
By the way, I agree with the opinion that this problem was not great as a MO&CP problem.
How to solve A ? Couldn't figure out the last two cases which i was getting wrong during whole contest
Maybe try “ aaa 3” will help you. Or even “ a 7”
It was an Awesome contest , though i was unable to solve a single problem but i will be waiting for next one ...
I just bought a textbook for the Mathematical Olympiad.
Screencast
could you please share how to change flag for avoiding infinite loop in ubuntu in sublime text, i have faced many times issue, like computer getting stuck and not working , so i have to restart it, thanks in advance.
Just don't code infinite loops lol.
If your computer keeps crashing, that's not just an infinite loop, it's allocating infinite (or too large) memory. You can run it in some way that limits memory usage so when it tries to allocate too much memory, it'll just crash the program and not the whole system.
In windows, i guess you can't allocate much memory on stack, also, there is option of end task, but in ubuntu, it gets stuck completely, there is mention of such flag online, but i don't know how to change it in xyz.build format, that is in ubuntu, also, obviously i try to avoid infinite loop by using some predefined counter, but when you are in hurry you sometimes forgot things, by mistake.also if stuck it produces large output like 700 MB in seconds. Any kind of help will work for me.
Linux:
timeout -m 500 your_programto limit memory (this timeout),your_program | head -n Nto limit the output to the first N lines and terminate your program after it prints them.could you please share your sublime build file, as i don't know how to include flags in that, if you use sublime for building.
I just use sublime as an editor. You probably need to learn how to work in a normal terminal for Linux tricks like
| head.Hey guys, can anyone explain me how to solve problem C?
Where is editorial page 4?
When and where to expect the English editorial?rng_58
A-D are uploaded. Please wait a bit for E-F.
How is AtCoder allowed to publish tasks of their AGC if they are from IMO 2019 Shortlist?...
Wait, really?
Calm down. The problems in IMO shortlist are much harder.
I wish that CF problem's statements can be simple and readable like Atcoder's.
Video analysis of contest has very good sketches and though I don't know japanese I do get some ideas from their sketches, I wish they were added in editorials too.
I finally solved problem F in
Unable to parse markup [type=CF_MATHJAX]
and got TLE ;(code : https://atcoder.jp/contests/agc039/submissions/7897660
Would someone help me figure out why my code for problem A: Connection and Disconnection is wrong? I wrote my code in Python3 but it doesn't pass test cases 1 and 2.
Below is the code that I've written. I've separated the problem into 5 cases.
i) S is a single letter.
ii) S is two letters and they are the same.
iii) S is two letters and they are different.
iv) S is more than two letters and the first and last letters are different.
v) S is more than two letters and the first and last letters are the same.
S = aaa,K = 1, it will output 0?Wow, you're a genius! I fixed my code and it finally passed all test cases! Thank you so much for your help!
Anyway, Can anyone solve E and F ?
Uploaded E/F editorial too.
Where is the English editorial of E and F?
Huh. My solution for E is
Unable to parse markup [type=CF_MATHJAX]
and it's simpler DP: the states are "number of ways to make $$$[i, j]$$$ a subtree of an edge to $$$k$$$ from a point outside $$$[i, j]$$$". Obviously,Unable to parse markup [type=CF_MATHJAX]
.As the DP transition, I pick the "topmost" line segment that crosses the one from $$$k$$$, i.e. with endpoints that are farthest from $$$k$$$. All other such line segments can't cross this one, so this it's well-defined. If it's between points $$$a$$$ and $$$b$$$, I then pick a point $$$l$$$ and a point $$$r$$$ such that
Unable to parse markup [type=CF_MATHJAX]
, split $$$[i, j]$$$ into subtreesUnable to parse markup [type=CF_MATHJAX]
(subtree of $$$a$$$), $$$[l, r]$$$ andUnable to parse markup [type=CF_MATHJAX]
(subtree of $$$b$$$), just multiply the answers for them and add the result to the state $$$i, j, k$$$.It seems like overkill complexity, but the constant is great and there's a lot of nonsense transitions — any state with odd $$$i-j$$$ is invalid, for example.