Honestly, you should definitely participate in this contest. Problems are very good.

Also, as the only tester with sunglasses on, please give me contribution.

Is it possible to advance the start time of the contest to start at 13:00 UTC such that it does not overlap with the HackerEarth Circuits April'22 contest which starts at 16:00 UTC?

How do you become a tester as an unrated user?

unusual timings not so usual nowadays.

12:00 UTC — 13:40 UTC ABC249
14:05 UTC — 17:05 UTC GR20
16:00 UTC — 18:00 UTC SRM828

Busy day! (And the last hour of GR is the first hour of SRM (coding phase))

As a tester, good luck.

As the setter who did not get to write the announcement :(, please compensate me with more upvotes than the announcement.

As a tester, screw you maomao90

As a tester I can tell the problems are curated and very interesting. Shoutout to the authors and antontrygubO_o

All the best to everyone!

Could you please shift that at least one hour earlier to avoid clash with TopCoder round?

Good luck to everyone!

This contest will be my first step toward a sacred goal

9 problems and 3 hours! This will be tough

Eat Sleep get positive rating repeat

So Many contests back to back. Contest after iftar and My condition...

I hope I could get to 1500 again after this contest

As a stupidest tester, GLHF everyone :3

Is it rated?

No permutation problems since errorgorn is an author? :)

Congratulations rotavirus early-morning-dreams

All the best! May you get the color that you are looking for!

like for any other Codeforces contest, I am excited for this too!!

errorgorn thanks for the round!

Congratulations early-morning-dreams and rotavirus...

মানুষের সুখ কখনও চিরস্থায়ী হয় না, একদিন না একদিন তার বিয়ে হয়ে যায়...

May the joy of your new life be filled with laughter, smiles, kisses, hugs, respect, understanding, and faithfulness...

Happy Wedlock!

Should beginners take part in global contests?

Can anyone tell me why my submission is working fine locally but not in cf 154251073.
I know such things happens when we access unallocated memory, but not getting where I'm wrong here...

Congratulations rotavirus and early-morning-dreams

Is this contest Rated?

The only reason I wake up everyday is to be there when an unrated account called antontryvirus AKs a hard Codeforces Global as its very first round.

WAon2Forces :(

After the best result ever I go back to pupil. And I told myself that God will forgive me if one round is skipped.

Welcome Codeforces! I am mister Bebra.

ConstructiveForces

I just wanna say that problem C was Evil

Got a weird bug on D, thought my algo was correct :(

How to solve E?

Spent 11 minutes to solve A. Spent 26 minutes to solve F1.` Yes ! Welcome to the constructive algorithms hell!.

Isn't problem I just a simple application of Endless Road trick?

MikeMirzayanov check my bro fuckyou for code obfuscation of greatest caliber (i looked at his submissions on hacking), he also had submissions skipped in the past

In last hour, finally, I recalled I haved give the same idea with pH in codeforces round. (https://codeforces.com/contest/1329/problem/D). and antontrygubO_o ever said my problems is dirty. :(

Overall it was a nice contest, but I think problem H was too easy

I got stuck on D for exactly two hours and I didn't even pass it after passing E and F1. Holy ****ing ****.

Shouldn't the output of AAABABB is "NO" for problem B??

F1 was fun to try, but I couldn't do it after an hour. Hope to learn from solutions, good round!

So what exactly was there in Problem D's TC 3?

I am getting memory limit exceeded in F1, but everything looks fine.

I am using set with a custom comparator function. And yes, I am removing elements from the set as well.

void solve(){
  int k,i, j, q, x, y, n;
  cin >> n;
  auto cmp = [] (pair<int,int> a, pair<int,int> b){
    if(a.se != b.se) return a.fi < b.fi;
    return a.fi > b.fi;
  };
  set<pii, decltype(cmp)> s(cmp);
  for(i = 0; i < n; i++){
    cin >> x;
    s.insert({i,x});
  }
  vi ans;
  
  while(!s.empty()){
    ans.pb((*s.rbegin()).se);
    s.erase(*s.rbegin());
  }
  forn(i,n) cout << ans[i] << " ";
  cout << Endl;
}

submission link : https://codeforces.com/contest/1672/submission/154765626

The pretest of E is very weak. if you set the upper bound of binary search as 4e6, you will get FST because there is no maximum data in pretest. The correct upper bound is 2000*2000+2000-1=4001999.

There's no way my solution of E will pass! I just threw in some "if can't improve current answer" to decrease the number of queries in normal cases. It still probably has a countertest.

Too many FSTs in E afraid me :(

Note the unusual timing, it is 30 minutes earlier.

I didn't notice it -> came to contest 20mins late -> only managed to code and solve F1 5mins after contest end! What a sad day.

It's probably better to put the corner cases in pretests:(.

Thank you for maliciously and intentionally adding the test "1 1" to systests. Hope you sleep well at night.

Thank you author, after 18 months practicing on codeforces, now I have become master now, and will reach 2200+ rating, with only python language. So excited !

Maybe I should write a blog on how to practice in codeforces with python language and avoid TLE, anyone interested?

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

so i see that in problem B, if we replace every A with a ( and every B with a ), it becomes a "valid bracket sequence problem", why the solution works for both, can anyone elaborate ?, thanks in advance.

CF is the most right place for political manifests!!

rainboy was the first one to solve problem I, I just want to know why he does not skip problems from back and solve other problems? Even in Global contests.

Problem F1 be like I would like to explain the concept of derangement of a permutation.

Examples: A derangement of 1 2 3 can be 3 1 2, but 3 2 1 is not a derangement of 1 2 3 because 2 is still in its correct position.

Sometimes for an array, a derangement is not possible. Let us take an example.

Consider the array of numbers 1 2 1. Try writing the remaining permutations of this array, at least 1 element will retain its position.

Statement: If an element occurs more than 'half the size' number of times in an array then the derangement of that array is not possible.

Proof: Consider, an array of n elements. If there exists an element with a frequency that is greater than n / 2(take it as real division). Then the given array cannot be deranged because if we pick that particular element and try filling the remaining numbers into its original position, we will run out of numbers. For example, in the case of 1, 2, 2, 2, 3 In order for 2 to not be in its original set of positions, we need 1 and 3, which are the remaining distinct elements in the array, to fill in for 2. But there are 3 positions and only 2 numbers to occupy, hence every position will not be occupied, hence no derangement is possible. That concludes our proof.

When a derangement is possible, how do we construct it? Consider the case when elements are sorted. If we calculate the maximum frequency that a number has in an array, we can rotate the array by that amount and get the derangement of the given sorted array.

How is that possible?

Consider the n elements of a sorted array, a1, a2, ....., an. If we rotate the array by the maximum frequency, we are sure that the elements with the maximum frequency are not going to retain their original position as the series of similar numbers will be shifted ahead. For example, if we have, 1, 1, 2, 2, maximum frequency here is 2 and rotating by 2 yields 2, 2, 1, 1. In the forward direction, the ones are all ahead of the last one in the original permutation. So, in the forward direction, the array has kind of shifted right. No element will retain its position. You can try rotating 1, 1, 2, 2, 2, 3 by 3 to get a better feel or try out as many examples you want. As long as derangement is possible, and you rotate the array by maximum frequency, the new permutation of that sorted array is deranged.

Now how does this help in deranging an unsorted array? Simple, when you sort the array, keep the positions of each occurrence of the number with it. For example, for the array 1, 1, 6, 7, 8, 9, 1, 2, 2 the sorting would be (1, 1), (1, 2), (1, 7), (2, 8), (2, 9), (6, 3), (7, 4), (8, 5), (9, 6). Now when you rotate the sorted array by the maximum frequency, you will get the derangement of the sorted array, not of the actual one. So, keep an auxiliary array of the same size and go through the sorted array that stored the indices, sequentially from beginning and fill that index of the auxiliary array with the value of the rotated array that is equal to that retained index alongside the value(in the sorted array that is not rotated, look at the example). In a way, you are using the derangement of the sorted array to fill in the position of the numbers in the unsorted array. Let us consider an example. The array is 2, 1, 1, 2, 1, 3, 4, 5. If we sort the array and retain the indices, we have (1, 2), (1, 3), (1, 5), (2, 1), (2, 4), (3, 6), (4, 7), (5, 8). Now since the maximum frequency is 3(1 occurs thrice), we rotate this sorted array by 3, based on the first element. We now get, 3, 4, 5, 1, 1, 1, 2, 2.

3 goes to position 2 as in the corresponding array, the element is (1, 2)

4 goes to position 3 as in the corresponding array, the element is (1, 3)

5 goes to position 5 as in the corresponding array, the element is (1, 5)

1 goes to position 1 as in the corresponding array, the element is (2, 1) and, so on.

We get the following output, 1, 3, 4, 1, 5, 1, 2, 2 which is a derangement. If you observe carefully, the sorted version is just being modified, if a number x comes in position of y in case of sorted array, it just replaces y in its position in case of an unsorted array.

If you forget where you can see Global Rounds 2022 standings then I remind https://clist.by/standings/codeforces-global-rounds-2022-34697905/

The main idea of Problem G is the actually the same as this problem.

I'm so dumb that I didn't read the problem during contest...

Thanks

How can I know who will get the prize?

ค้ค้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้

Unofficial T-shirt winners list (FINAL)

Well, it looks like enough time has passed and the standings have been finalized, yet the official winners list hasn't been released yet, so it's time to farm contribution post the unofficial list again!

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, 1672):

import requests

contests = [1672] # 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://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.

It took a bit longer than usual, but congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

#!/usr/bin/python3

import requests

contests = [1672]

# [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://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(eligible[place - 1].name))

#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;
}