We tried our hardest to make interesting tasks. We hope you will enjoy solving our problems as much as we did enjoy creating them (づ｡◕‿‿◕｡)づ

AIs not partipicating again?

I still have PTSD from the last round having cute text emoticons in the announcements.

Proposing to rename master rank to maestro for EvgeniyPonasenkov

As a tester I really enjoyed solving and upsolving problems from this contest. Hope you too!

(* ^ ω ^)

cutea

Programmers if the AI fails to beat them

I was looking forward to a rated round but then a notification reminded me that I tested a round recently ;(

GLHF everyone though, let us all :sip: at this special contest.

(づ｡◕‿‿◕｡)づ ❤

Mangooste orz for authoring two concecutive rounds.

Why is there no mention of XTX Markets in the announcement? (edit: now added)

I wish everyone to increase their rank)

Are AI accounts participating? Bet these AI bots did not recover well from the last round

Автокомментарий: текст был обновлен пользователем Mangooste (предыдущая версия, новая версия, сравнить).

Auto comment: topic has been updated by Mangooste (previous revision, new revision, compare).

Will it contain any interactive problem?

Good luck everyone!

Hope you enjoy the tasks ♡!!!

P.S. Actually, it takes a lot of hard work to prepare every task properly, so upvote the initial post as a sign of respect for the contest setters.

(づ｡◕‿‿◕｡)づ ❤

Waiting for AI to overpass my rating :-)

I add rating every time I join Global Round, hope you so. Really enjoy. :)

Will this round be rated?

Hoping for a nice round!

I will be not able to participate in contests for a long time after this round because of the new term. TAT

NANOGrav

I hope I will enjoy it！

hoping to first time get rank under 1500 in div 2.

Best of luck, all

Good luck

this one goes out to all my fellow noobs:

"The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest."

so she doesn't get any result?

Is registration during contest not allowed?

I wasted too much time on B and C ... overthinking sucks man!

Yeah, maybe this contest will make me a pupil

Solved C in 30 minutes, solved D in 80 minutes, and then solved E in 20 minutes. What a disbalance!! Problem D isn't quite good, because you need just guess, that you have to minimize |sum(a)-sum(b)|. Rest was good, Liked problem E

Somehow, you can pass pretests in E if you use unordered_map, but not gp_hash_table, is it intended? I thought gp_hash_table should be way faster... Also, my solution seems to be $$$O(n \log n)$$$ and is already quite close to the time limit, was it intentional that $$$O(n \sqrt n)$$$ doesn't pass? Or did it pass for others?

How to solve G?

wxhtzdy orz

never mind this is trash i had no time to think about it well

What's the ideal time complexity to solve E?

How to solve B?

Weak and useless samples!

Imagine implementing $$$O(n \sqrt{n})$$$ in E (and doing constant factor optimization to get it to pass) only to realize afterwards the easier $$$O(n \sqrt{n} \log{n})$$$ solution somehow runs faster — 146115870

E was only about realizing we need to keep max 2 elements per count (max O(sqrt(n)) candidates )? Such low number of submissions completely threw me off :/

For problem D, it took me a long time to realize that the given cost is $$$(a_1 + ... + a_n) ^ 2 + (n - 2) * (a_1 ^ 2 + ... + a_n ^ 2)$$$, and the second part doesn't affect the answer.

But if I just guess "minimizing $$$|sum(a) - sum(b)|$$$", which is actually intuitive, then I can submit a solution much quicker. However, I don't think guessing is a good way to solve problems.

Feedback on the problems:

• A: Ok.
• B: The idea is nice, the way you decided to transform the idea into a problem, so-so. Would have been cleaner with $$$n=100\,000$$$ and just asking for the value of the array (instead of the sum over whatever).
• C: Good problem. The moment I read it, I thought I was going to get stuck and in fact I got stuck (at least I am consistent). For me, this was much harder than D.
• D: Very standard, solved immediately after reading.
• E: Very good problem. I had to think and when I noticed that $$$cnt$$$ can have at most $$$\sqrt{n}$$$ values and this was sufficient to solve the problem, I was somewhat happy.
• F: Cute problem. This felt easy, most likely because I was lucky and noticed immediately that rooting the tree at the highest vertex is useful.
• G: (unexpectedly) Cool problem. The first thought reading it is "who cares?". Then, when I saw the point of the problem (which was shown to me by a backtracking), I changed my mind. I solved this in contest apart from the limit on the number of queries (because I was doing something incredibly stupid), solved 3 minutes after the end of the round. I enjoyed solving it.
• H: Not read.

I enjoyed a lot the contest because the problems at "my level" (i.e., E, F, G) were very nice. Thanks to the authors.

After this, I feel so dumb. :(

If we comment via the "ask a question" link during the contest, is it visible to everyone or just the commentor/ judges? I made a mistake where I thought there was a problem flaw where there was none and I didn't know whether or not to apologize because I didn't want to disrupt anyone who was still coding.

Also, if it is public, is there a better way to bring things like these up?

Thanks to all, and especially to the judges for a wonderful round (and for putting up with the annoyance I may have caused you.)

E is interesting in the sense that based con some conversations I bet there are a lot of people who wrote an $$$O((n + m) \log n)$$$ or similar non-sqrt solution without realizing it.

My solution is basically this:

1 for (int cx = 1; cx <= n; cx++) {
2   for (int x : wcnt[cx]) { // the list of things with cnt[x] = cx
3     for (int cy = 1; cy <= cx; cy++) {
4       // try the best non-forbidden y with cnt[y] = cy
5     }
6   }
7 }

Trivia question: how many times is line 4 hit? Answer: it is in fact $$$O(n)$$$. For a fixed $$$x$$$, the number of times line 4 is executed is the frequency of $$$x$$$, so in total we visit line 4 once for every element in the array.

I believe this proof can be adapted to several people who proudly claimed to have passed E in $$$O(n \sqrt n)$$$ or even $$$O(n \sqrt n \log n)$$$ with "no constant optimizations".

I enjoyed this contest, it required a lot of observation, and problem C felt like a troll :D

took many tries and observations to figure it out, but eventually i solved it.

In problem A. 3 2 1 4 5 can be sorted as 3 2 1 and 4 5 are sorted individually so ans will be no ,but many has written solution as if there is increasing array ans will be yes. can anyone explain me this test case .

Nice round! E was cute but I was a bit dumb on it.

For me, Problem C is harder than D and E. But liked the observation in C the most.

did the 700th upvote:) nice problems , loved problem D

pretest in E is so weak...

F is cool, create interesting&fresh task on tree is giga hard nowadays, so thanks to authors :)

Didn't use long long in C. (T_T)

MikeMirzayanov My submission on E got TLE on system test. But the exactly same code passed after the contest.

link: https://mirror.codeforces.com/contest/1637/submission/146139122
https://mirror.codeforces.com/contest/1637/submission/146157321

Could you rejudge the submission please? Thanks in advance!

Spent too much time on C but solution is concise and pleasant 146131266

How to prove that "minimum power of two at least n" is the minimum achievable value in G?

Fast Rating Change!!

Can somebody please point out whats happening? I used modified knapsack in D and here are two submissions Solution 1 AC Solution 2 WA The only difference between them is that I sorted arrays a and b before knapsack in solution 2 but that should not affect the answer. Can somebody point out the reason? Thanks in advance

Very cool round, thanks a lot to authors! Problems F, G were especially cool

Shout out to kal013 for becoming the highest rated Indian of all time on cf by beating amnesiac_dusk.

PS: I've been following both of them since I started cp :)

great round overall :)

If you believe that

• top-10 by cf rating as of now
• top-1 at codeforces global round 19 by atcoder penalty rules
• top-1 at being the most handsome guy in our ICPC team

legendary overtrained upsolver Maksim1744 will win the next ICPC WF, then make sure to join his official fan group!

When I take part in global round, it makes me feel sad every time.

The description of this contest's problem is very bad！

Truth be told,really really bad.I have never seen the bad description like this

Unofficial T-shirt winners list

Update 2: It looks like cheaters have been removed, and the standings have been updated. As such, the full list of winning handles has been added.

Going forward, I'll post only the list places of winners (in a compact format) shortly (~12h) after the contest. While not as useful, you can still check to see if you're close to becoming a T-shirt winner. Once the standings have been updated to remove cheaters, I'll post the full list of winning handles.

Update 1: Since cheaters have not been removed yet, the standings is not final and is subject to change. As a result, this list of winners will probably change significantly. The list place of winners won't change, but the winning handles will. For now, I have removed the winning handles outside the top 30, and I will update the list once cheaters have been removed.

Since the official announcement isn't here yet and I'm an impatient person, I've decided to find out who won the t-shirts for myself.

As always, you can do the following steps to get the t-shirts winners of Global Rounds:

1) Download testlib.h from Mike's github repo.

2) Use it to compile randgen.cpp :

#include "testlib.h"
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    if (argc < 4)
    {
        cout << "Command line arguments are: seed length prefix nwinners" << endl;
        return 1;
    }
    int seed = atoi(argv[1]);
    int len = atoi(argv[2]);
    int prefix = atoi(argv[3]);
    int nwinners = atoi(argv[4]);
    rnd.setSeed(seed);

    set<int> winners;    
    while ((int)winners.size() < nwinners)
        winners.insert(rnd.next(prefix + 1, len));

    for (int i = 1; i <= prefix; ++i)
        winners.insert(i);

    for (auto winner: winners)
        cout << winner << " ";
    cout << endl;

    return 0;
}

3) Run the Python script winners.py, replacing the number in contest = [] with the ID of the contest in question (in this case, 1637):

import requests

contests = [1637] # Replace this with the ID of the contest in question

# [1, rank_start) get tshirts with no random
# [rank_start, rand_end] get random tshirts
rank_start = 31
rank_end = 500

n_random_tshirts = 20

def is_eligible(contest, party_name, rank, points, problems, last_submission_time):
    return (rank <= rank_end)

def get_party_name(party):
    if 'teamName' in party:
        return party['teamName']
    else:
        return party['members'][0]['handle']

class Party:
    def __init__(self, contest, name, rank, points, last_submission_time):
        self.contest = contest
        self.name = name
        self.rank = rank
        self.points = points
        self.last_submission_time = last_submission_time

    def __lt__(self, other):
        if self.contest != other.contest:
            return self.contest < other.contest
        if self.rank != other.rank:
            return self.rank < other.rank
        if self.last_submission_time != other.last_submission_time:
            return self.last_submission_time < other.last_submission_time
        if self.name != other.name:
            return self.name < other.name
        return False

eligible = []

for contest in contests:
    rows_to_fetch = 20000
    r = requests.get('https://mirror.codeforces.com/api/contest.standings?contestId=%d&from=1&count=%d&showUnofficial=false' % (contest, rows_to_fetch))
    if r.status_code != 200 or r.json()['status'] != 'OK':
        print('Error: failed to fetch results of contest %d.' % contest)
        exit()
    results = r.json()['result']['rows']
    if len(results) == rows_to_fetch:
        print('Error: results are too long in contest %d, increase limit.' % contest)
        exit()
    for row in results:
        party_name = get_party_name(row['party'])
        rank = row['rank']
        points = row['points']
        problems = 0
        last_submission_time = 0
        for problem in row['problemResults']:
            if problem['points'] > 0:
                problems += 1
                last_submission_time = max(last_submission_time, problem['bestSubmissionTimeSeconds'])
        if is_eligible(contest, party_name, rank, points, problems, last_submission_time):
            eligible.append(Party(contest, party_name, rank, points, last_submission_time))

eligible = sorted(eligible)

for i in range(1, len(eligible)):
    if not eligible[i - 1] < eligible[i]:
        print('Error: unable to sort eligible at positions {} {}.'.format(i, i, i + 1))
        exit()

print('Eligible for tshirts are:')
for idx, party in enumerate(eligible):
    print('{} {} {} {} {}'.format(idx + 1, party.contest, party.rank, party.name, party.last_submission_time))


seed = eligible[0].points

print('Total %d eligible, seed is %d.' % (len(eligible), seed))


import subprocess
testlib_rand = subprocess.run(['./randgen', str(seed), str(len(eligible)), str(rank_start - 1),    str(n_random_tshirts)], stdout=subprocess.PIPE)
winners = list(map(int, testlib_rand.stdout.split()))

print()
print('Winners are:')
for place in winners:
    print('{} {} {} {}'.format(place, eligible[place - 1].contest, eligible[place - 1].rank, eligible[place - 1].name))

print()
print('| List place | Contest | Rank | Name |')
print('|--|--|--|--|')
for place in winners:
    print('| {} | {} | {} | [user:{}] |'.format(place, eligible[place - 1].contest, eligible[place - 1].rank, eligible[place - 1].name))

Both of these scripts are taken from the official winners announcements in previous Global Rounds, but if you have any doubts on their legitimacy you can always check these results against the official ones later.

With that out of the way, congratulations to the (unofficial) t-shirt winners:

P.S. If any contest organizer has any issue with early unofficial winners list like this one, feel free to contact me.