We will hold AtCoder Regular Contest 165.

- Contest URL: https://atcoder.jp/contests/arc165
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230917T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: chinerist
- Tester: maspy, potato167
- Rated range: — 2799

The point values will be 400-600-600-700-700-800.

We are looking forward to your participation!

tough contest

C is tough!

Cool contest, especially $$$B$$$ & $$$C$$$. Maybe there is easier solution, i solved $$$B$$$ using segtree(it is straightforward to find such index $$$f$$$, that after an operation on $$$v[f : f + k - 1]$$$, $$$v$$$ is maximal. We can compare results of operations $$$v[x: x + k - 1]$$$, $$$v[y : y + k - 1]$$$ in $$$O(\log n)$$$.) $$$C$$$ is pretty cool too. Thanks!

How you solved C?

Binary search on asnwer. THe same as editorial.

There is a solution way easier than the editorial. Make a MST, and Color the vertices by the odd or even of its depth on the MST.

Share code, please.

My code

I did similar thing

https://atcoder.jp/contests/arc165/submissions/45689112

I solve B greedy: As it is sure that after sorting the array will become lexicographically <= of the original array. First I calculate the longest increasing subarray.

Case 1If this is longer than k then there is no need to do sorting as we can perform this operation on this subarray which is ready sorted.

Case 2In this case, it is optimal to sort the last k element. But we have to consider the case as for ex: "6 4 [3 4 6 5 1 2]" If we sort the last k elements — [3 4 1 2 5 6] which is not optimal. If we sift the k size window from the last k element to at max k-1 before such that the elements before that are all already sorted and lesser than the last remaining k size window elements. Here last k elements are [6,5,1,2] are remaining [3,4] which are already sorted so, we move the window to [3,4,6,5] which only affects the last two elements in sorting.

May be I am wrong but give me AC. submissions/45685014

I passed D in the last 2sec!!!!!

my submission

how to solve A

edit : solved

to make the elements a1, a2, ...., ak to have N as their LCM these should be the prime factors of the number N.

To make the sum equal to N, you need to check if the number of prime factors are atleast 3 because one of the prime factors would always be 1, and lcm(1, x) = x, which won't let the lcm to be equal to N.

for example consider the case N = 10, we find out the prime factors of 10 as 1, 2 and 5. We can add these as 5+2+1+1+1 == 10 and LCM(1,1,1,2,5)==10

Again consider the case N=8, prime factors of 8 = 1, 2 even though we can make the sum of prime factors equal to 8, we won't be able to make the LCM equal to 8 because LCM of 1 and 2 comes out to be 2.

is this code O(n^2)? https://atcoder.jp/contests/arc165/submissions/45684077 or did i make a error somewhere.

(I asserted some places, so i do think its O(n^2))

(The Solution is to find scc, condense them, refind scc. i pass a graph of size atmost m atmost n times and my m pointers also move atmost n times, so i believe its n^2)

Since you don't clear the graph fully I believe that it can have $$$O(nm)$$$ edges, so it will work in $$$O(n^2 m)$$$?

Towards the end of my solve function, you can check just before i call scc() i assert the graph has <= m edges

Oh, I didn't notice that you don't add a new edge if the pointer didn't move.

Well, asserts seem to confirm that it is $$$O(n(n+m))$$$. The general structure of the solution is correct.

Probably

`vector<vector<int>>`

is not a great idea. I generated a test: 223740510.unfortunate (and surprising since my friends have as low as 200ms) but thanks anyways

B test cases too weak

Passed with checking for the last 100 indexes and indices of elements 1...200 and taking the best of them

https://atcoder.jp/contests/arc165/submissions/45673283

The tests are not weak, maybe author don't even expect such fake solution:)

First time in Top 10!

Also, problem F is really similar to IOI19 arranging shoes. F just added "lexiographically smallest" to IOI19 shoes, but it made the implementation way harder.

Are tests for B too weak? Looking at first python AC solution: https://atcoder.jp/contests/arc165/submissions/45672082

It seems like it should fail for something like:

It outputs

`1 3 4 2`

. I think it should be`3 1 2 4`

Yeah, there seem to be a lot of solutions that should wa on similar testcases, but got ac in the contest.

Another such example (if I'm not mistaken): https://atcoder.jp/contests/arc165/submissions/45680434

My Solution outputs 1 3 4 2,too.

But it gets AC,too :)

I have little difference with editorial in solution to $$$C$$$. I calculate the maximum $$$x$$$, such that if we remove edges with $$$w \ge x$$$, graph is bipartite. I use binary search for it. Let it be $$$A$$$. But then I don't calcalute minimum weight of path with length $$$2$$$ for remaining edges. Instead, in the whole graph I calculate minimum weight $$$B$$$ of path with length $$$2$$$, only once. The answer is $$$min(A, B)$$$.

I wrote I solution to C using binary search and checking whether the graph bipartite. But is gets WA, I have no idea why. I was debugging it for an hour, then I wrote a DSU solution.

Code (WA)Graph can become disjoint after removing edges. And you check only one connected component of it.

Oh, thank you. I have to be more careful.

Why is this solution correct for B? On the following input

6 3

6 3 2 5 1 4

The program outputs

6 3 1 2 5 4

When we can obtain

6 3 2 1 4 5

By applying operation on the last 3 elements. Please can anyone tell me what i am missing?

You aren't missing anything. Tests are apparently weak.

How to (or, Can we) add hacks for B? Tests are too weak.

As some of you mentioned, tests for B were weak. We added a few extra tests as after_contest.

Will the solutions be rejudged(or perhaps rating recalculated)?

No, it doesn't affect in-contest submissions.

In second solution of C can someone explain me how to find the weight of the edge at which the graph first becomes non-bipartite when starting from a graph with N vertices and 0 edges and adding M edges in ascending order of weight. I wasn't able to understand how the approach given in the editorial works to find this.