hope to solve even one problem in AGC...

Usually the first problem in AGC is very easy.

Hope to solve A in AGC...

.

any similar problem like A?? thanks in advance

How to solve B ?

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?

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,I don’t think I’m right.So Sad that I have 10 wrong submissions .

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

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

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,

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.

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

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

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

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

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

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

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 $$$O(KHW log(HW))$$$ 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 = 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)

Anyway, Can anyone solve E and F ?

Where is the English editorial of E and F?

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.