rng_58's blog

AtCoder Grand Contest 039 Announcement
By rng_58, history, 5 years ago, In English

We will hold AtCoder Grand Contest 039. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

  • Vote: I like it
  • +32
  • Vote: I do not like it

Comments Comments (113)
| Write comment?
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

hope to solve even one problem in AGC...

→ Reply
»
5 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Usually the first problem in AGC is very easy.

→ Reply
»
5 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Hope to solve A in AGC...

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -41 Vote: I do not like it

.

→ Reply
»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

any similar problem like A?? thanks in advance

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B ?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -7 Vote: I do not like it

    Do bfs by starting a node in first set.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      The same conclusion is that the answer is satisfied when the graph is a bipartite graph. Maybe it's easier to understand.

      → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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.cpp command to compile and gcc version is 5.4.1

It 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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    The AtCoder server probably does not have a CPU that supports avx2 instructions (it may be too old), so it probably is getting RTE from an illegal instruction.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for your kind explanation!

      → Reply
»
5 years ago, # |
  Vote: I like it -32 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    how to solve A..

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Solve for $$$f(s)$$$, $$$f(s+s)$$$ and $$$f(s+s+s)$$$ separately. That helps in knowing how much extra cost you have to pay for adding $$$s+s$$$ to $$$s$$$ (from $$$f(s+s+s)$$$ — $$$f(s)$$$). Now how many $$$s+s$$$ is needed to get $$$(k-1)$$$ copies? Add them. If you still need one more s to add (since $$$k$$$ is even), add $$$f(s+s)$$$ — $$$f(s)$$$

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    C was hard too, in 2 hours I could only figure out I had to check odd factors of $$$N$$$ (each odd factors had $$$factor * 2$$$ as answer but $$$(factor - 1)/2$$$ times if even and $$$(factor+1)/2$$$ times if odd) but then the problem of counting upto $$$X$$$ needed more pattern to be observed.

    → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve A,I don’t think I’m right.So Sad that I have 10 wrong submissions .

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -13 Vote: I do not like it

    If you got $$$AC$$$ you are right as systest happen during the contest not later.

    → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +26 Vote: I do not like it

Apparently, D is formula bashing. Why????

Basically, for each point $$$A$$$ and each pair of other points $$$B, C$$$, we want to sum up

$$$\dfrac{\mathsf{A}_x \cdot |\mathsf{B}-\mathsf{C}|}{|\mathsf{A}-\mathsf{B}|+|\mathsf{B-C}|+|\mathsf{C-A}|}$$$

and take their average to get the $$$x$$$-coordinate of the incircle. This is just using a standard formula. We can fix $$$\mathsf{A}$$$, rotate the circle so that point $$$\mathsf{A}$$$ is $$$(1, 0)$$$, find the average of the $$$x$$$-formula for this fixed $$$\mathsf{A}$$$ (so $$$\mathsf{A}_x = 1, \mathsf{A}_y = 0$$$), de-rotate to get some point $$$\mathsf{EI}_\mathsf{A}$$$ and take the average of these points to find the resulting point $$$\mathsf{EI}$$$.

Since the points lie on a circle and $$$\mathsf{A}$$$ is fixed, we can use the angle between points $$$\mathsf{B}, \mathsf{A}$$$ (angle $$$x$$$) and between points $$$\mathsf{C}, \mathsf{A}$$$ (angle $$$y$$$) instead. Then, $$$|\mathsf{A}-\mathsf{B}| = \sin\frac{x}{2}$$$, $$$|\mathsf{A}-\mathsf{C}| = \sin\frac{y}{2}$$$ and $$$|\mathsf{B}-\mathsf{C}| = \sin\frac{x+y}{2}$$$. Simplifying with sum formulas,

$$$\sin\frac{x}{2} + \sin\frac{y}{2} + \sin\frac{x+y}{2} = \sin\frac{x}{2} (1 + \cos\frac{y}{2}) + \sin\frac{y}{2} (1 + \cos\frac{x}{2}) \\ = 4 \sin\frac{x}{4} \cos\frac{x}{4} \cos^2\frac{y}{4} + 4 \sin\frac{y}{4} \cos\frac{y}{4} \cos^2\frac{x}{4} \\ = 4 \cos\frac{x}{4} \cos\frac{y}{4} (\sin\frac{x}{4} \cos\frac{y}{4} + \sin\frac{y}{4} \cos\frac{x}{4}) = 4 \cos\frac{x}{4}\cos\frac{y}{4}\sin\frac{x+y}{4} \,,$$$
$$$\dfrac{|\mathsf{B}-\mathsf{C}|}{|\mathsf{A}-\mathsf{B}|+|\mathsf{B-C}|+|\mathsf{C-A}|} = \dfrac{2\sin\frac{x+y}{4}\cos\frac{x+y}{4}}{4\cos\frac{x}{4}\cos\frac{y}{4}\sin\frac{x+y}{4}} = \dfrac{\cos\frac{x+y}{4}}{2\cos\frac{x}{4}\cos\frac{y}{4}} = \frac{1}{2} - \frac{\sin\frac{x}{4}\sin\frac{y}{4}}{2\cos\frac{x}{4}\cos\frac{y}{4}}$$$

which is $$$(1-\tan\frac{x}{4}\tan\frac{y}{4})/2$$$; finding the average of this over all $$$x, y \neq 0$$$, $$$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 $$$0 < x < y < \pi$$$; points with angle $$$\pi$$$ can be handled separately. If $$$\mathsf{B}$$$ and $$$\mathsf{C}$$$ are both on the same side ($$$\triangle \mathsf{ABC}$$$ is obtuse), then we need $$$2\pi-y$$$ instead of $$$y$$$, which just means we divide by $$$\tan \frac{y}{4}$$$ instead of multiplying. The code is still simple though.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    There is a somewhat obscure olympic-math-folklore theorem that renders the problem trivial. The correct search engine query is "incenter complex numbers".

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +83 Vote: I do not like it

    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)

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +48 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      and the orthocenter is a+b+c

      with a simple angle-chase that I is the orthocenter of DEF

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        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.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Was this some test if a person calculates geometry in complex numbers often?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That gave me back my 2013 :)

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can deal without complex numbers but I don't know if that's simpler.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I've read your comment, complex numbers solution is significantly simpler

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Dude, wat o0? That code is even much shorter than mine.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +28 Vote: I do not like it

          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

          $$$\exp\left(i\frac{\varphi_1+\varphi_2}{2}\right) - \exp\left(i\frac{\varphi_1+\varphi_3}{2}\right) + \exp\left(i\frac{\varphi_2+\varphi_3}{2}\right)$$$

          is the incenter of the triangle with vertices $$$a$$$, $$$b$$$ and $$$c$$$.

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -27 Vote: I do not like it

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)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +116 Vote: I do not like it

    Now I realized that I don't even know super basic fact :(

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    I prefer solving problems about world history rather than OM geometry

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      solving problems about world history

      by going back in time?

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Well, I prefer solving problems about world history rather than ones about strings and data structures

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +93 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +33 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it +20 Vote: I do not like it

          Me too. At least, I don't want study about some complex formula of triangle...

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        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!

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it +23 Vote: I do not like it

          Even if you recieve good data structures problems, you still won't use them?

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    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)

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Now let’s select all points uniformly inside the unit circle, N up to 10^100 :)

→ Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    high school math

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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)

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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" (논증기하))

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Maybe call it Euclidean geometry XD

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          East Asian countries have more advanced high school math

          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.

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you give me an estimate of the ratio of problems about segment trees to problems about IMO-style geometry?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +40 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it +10 Vote: I do not like 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.

            → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it -20 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like 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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it -18 Vote: I do not like it

                This is just your feeling.

                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.

                E is not straightforward when people believes that the intended solution requires exponential time.

                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?

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it -12 Vote: I do not like it

                  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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Your arguments are completely meaningless.

                  Every single one of my arguments ever is more meaningful than this.

                  People who managed to solve the problem tends to say that is easy.

                  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?

                  The combination of basic techniques may produce difficult problems

                  Yes, and I don't believe it's the case here (or in D, for that matter).

                  Explaining "why this should be easy" is easy.

                  Not at all. Assessing problem difficulty is a difficult skill to learn just like solving problems or making problems.

                  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.

                  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.

                  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?

                  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.

                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it +28 Vote: I do not like it

                I don’t think any sane people will try exponential solution when 2N <= 40. Anyway thanks for EF. I think they are interesting.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it +10 Vote: I do not like it

                  Well, that sounds like very productive thinking.

                  → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Xellos rng58 is imo gold medalist 3 times. so its very easy for him. thats why they look to him like high school maths

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -12 Vote: I do not like it

        If he really thought it is easy for competitive programmers, he should have made it 500-pt problem.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          This argument doesn't make sense.

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A ? Couldn't figure out the last two cases which i was getting wrong during whole contest

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Maybe try “ aaa 3” will help you. Or even “ a 7”

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was an Awesome contest , though i was unable to solve a single problem but i will be waiting for next one ...

→ Reply
»
5 years ago, # |
  Vote: I like it +78 Vote: I do not like it

I just bought a textbook for the Mathematical Olympiad.

img

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Screencast

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Linux: timeout -m 500 your_program to limit memory (this timeout), your_program | head -n N to limit the output to the first N lines and terminate your program after it prints them.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I just use sublime as an editor. You probably need to learn how to work in a normal terminal for Linux tricks like | head.

              → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, can anyone explain me how to solve problem C?

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Where is editorial page 4?

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

When and where to expect the English editorial?rng_58

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    A-D are uploaded. Please wait a bit for E-F.

    → Reply
»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

How is AtCoder allowed to publish tasks of their AGC if they are from IMO 2019 Shortlist?...

→ Reply
»
5 years ago, # |
  Vote: I like it +64 Vote: I do not like it

I wish that CF problem's statements can be simple and readable like Atcoder's.

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I finally solved problem F in $$$O(KHW log(HW))$$$ and got TLE ;(

code : https://atcoder.jp/contests/agc039/submissions/7897660

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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 = input()
K = int(input())
L = len(S)
sum = 0
x = 1

if L == 1: # i)
  print(K // 2)
elif L == 2 and S[0] == S[1]: # ii)
  print(K)
elif L == 2: # iii)
  print(0)
elif S[0] != S[-1]: # iv)
  for i in range(0, L-1):
    if S[i] == S[i+1]:
      x += 1
    else:
      sum += (x // 2)*K
      x = 1
  sum += (x // 2)*K
  print(sum)
else: # v)
  for i in range(0, L-1):
    if S[i] == S[i+1]:
      x += 1
    else:
      sum += (x // 2)
      break
  y = x
  x = 1
  for i in range(y, L-1):
    if S[i] == S[i+1]:
      x += 1
    else:
      sum += (x // 2)*K
      x = 1
  sum += (x // 2)
  sum += ((x+y) // 2) * (K-1)
  print(sum)
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    S = aaa , K = 1 , it will output 0?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Wow, you're a genius! I fixed my code and it finally passed all test cases! Thank you so much for your help!

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyway, Can anyone solve E and F ?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the English editorial of E and F?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Huh. My solution for E is $$$O(N^7)$$$ 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, $$$i \le k \le j$$$.

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 $$$i \le a < l \le k \le r < b \le j$$$, split $$$[i, j]$$$ into subtrees $$$[i, l-1]$$$ (subtree of $$$a$$$), $$$[l, r]$$$ and $$$[r+1, j]$$$ (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.

→ Reply