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

Make sure to have strong pretests this time ;)

Woah, Glebs and Zlobober. I haven't seen these two names in a long time.

Cool! Will this contest be rated for everyone?

How to solve Div2E/Div1C ? my idea was to sort the vector of vectors based on the max value of every vector and in case of equality i sort them by the one with the less number of inversions ,, i felt it is correct but getting WA on test2

No testers this time?

There appears to be a conflict with Atcoder Regular Contest 158. Pushing back the start of the round by 30 minutes will avoid the conflict.

Link to round: https://atcoder.jp/contests/arc158

Hoping to become specialist in this round, have been trying for specialist for quite a long time now, every time I was close there was one contest that would bring me down, this time for the past 5 contests, I have been gaining +ve delta, I am at my all time highest rating, need +23 to get to specialist. Sometimes, it demotivates me that I am not able to hit specialist despite all my other friends are already specialist but at the end of day, it's all about learning new topics and loving problem solving....

Why is this round (and some others) not numbered?

I don't even wan't to waste my time on these contests they are very hard.
Only one problem can be done hardly ever.
I advise you to not waste your time in this and help me with my " I wan't Div.5 " campaign.

Make sure to make the first question easy so that number of participants who solve the first question increases.

Nebius is an israeli company, so i will boycott the contest. I hope all arab do this as well

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

Hi. Is it a requirement to move to one of Belgrade, Amsterdam or Tel Aviv in case of job offer?

At my first glance, I read the round as Newbie Welcome Round — simple and friendly problems to welcome new people join Codeforces.

Will there be some classical problems?

Let's gooooooooooooo

When can we expect to see the score distribution?

8 problems in 2 hours!?

As a first-time tester, I'm sad I can't participate:(

magga orz

No Score Distribution ?

No Score Distribution?

Scores distribution???

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

As a tester, I'm really happy to test this contest. Zlobober's codes are super straightforward and easy to understand so I studied his codes when I was a candidate master. And Finally, I could become a master and His codes were really helpful to be a master.

Zlobober is my eternal idol, and I am really proud to test his contest.

Please, Let me become GrandMaster!

D is the Worst Problem I Have Ever Seen!..

is problem C literally just luck?

How to solve C ?? :((

ImplementationForces all the way

What was the logic for C ??

Hope my annealing simulation will pass systests in E.

Upd: it did!

How to solve E faster than (2^n)*(n^2)?

so for A my idea was to alternate with the longest side so it'll double up and reduce one and if both inputs share same pairty it's double

why didn't this pass ? ~~~~~ Your code here...

int a = sc.nextInt(); int b = sc.nextInt();

if(a == 0 || b == 0)
     {
         int res = Math.max(Math.abs(a) , Math.abs(b));
         System.out.println(res+res-1);
     }
     else
     {
        int x =  Math.max(Math.abs(a) , Math.abs(b));
        int y =  Math.min(Math.abs(a) , Math.abs(b));

           if((x+y) % 2 == 0)
           System.out.println(x+x);
        else
           System.out.println(x+(x-1));
     }

~~~~~

Oh no! I have been writing question D, but it continues to WA on pretest 5. Can anyone explain that? thanks!

My idea is to find two consecutive $$$1$$$ in a row and divide them into a group for the minimum value. For the maximum value, divide $$$01$$$ and $$$10$$$ into one group, in addition, divide $$$00$$$ into one group, and group the rest separately. If the number is not enough, divide the two into a group.

my code: https://mirror.codeforces.com/contest/1804/submission/197124751

Why was the rating change predictor( carrot or CF-Predictor ) not working for this contest ??

could someone please tell me ,why am i getting WA on this submission 197128613

rainboy finally rainboyed a contest, by being the only one to solve the hardest problem. Congrats!

How to solve D?

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

One of the nicest contests in a while. Very cool problems!

D was looking doable but i couldn't finish it :(

The worst D problem I've ever seen

this user BFU-marve is submiting in assembly, is this allowed?

Solved A-D. I passed pretest of E but I think my solution will be very likely getting FST. If it passed system test I'll get a large positive delta.

A: First, WLOG we can assume a>=0, b>=0 (by setting a=abs(a), b=abs(b)), and by looking for small cases we can get ans=a+b+max(0,abs(a-b)-1).

B: The problem is equvalent to "each pack of vaccines can be used on some patients with arrive time {t1, t2, ..., t_m}, where m<=k and t_m-t1<=w+d". Thus we can solve by greedy by finding maximal blocks of patients where they can get a same pack of vaccines.

C: Force f is good iff f*(f+1)/2 % n = (n-x) % n. Because (f+2*n)*(f+2*n+1)/2=f*(f+1)/2+n*(2*f+2*n+1), ( f*(f+1)/2 % n ) has a period of 2*n, so we only need to check for 1<=f<=min(2*n,p).

D: Consider for each floor separately. We need to put m/4 double-rooms at some places of the floor. Let the total count of bright windows of this floor is L, and the count of "11" double-rooms is t, then the number of occupied rooms is L-t. Therefore we need to minimize and maximize t. For maximization, we need to check every maximal block of consecutive 1s, and for minimization, we need to check every maximal block without "11". Be careful that we need to adjust t into range [0, m/4].

E: If there's a solution, we need to find a simple cycle in the graph, where the distance of every node and the cycle is at most 1. I used brute DFS to find the cycle, and it passed the pretests, but I think it could get TLE on some other tests.

Update: Now my submission of E has passed system test.

A VERY intresting problem C. Thanks!

Problem D : The Prince Of Ad-Hocs

Why my problem C skipped? I write it myself.It is easy for me.May be it is too short so it easily looks similar with others code?

Please, for the love of God, do not call an undirected edge a direct connection in the future :D

Each direct connection between a pair of distinct servers allows bidirectional transmission of information between these two servers.

Great contest overall, btw!

C has shitty pretests

wish me luck to become specailist after rating change.

Why did my code fail for problem D? Did I fail to consider an edge case or was my logic simply incorrect?

My idea for calculating min : If there are two lit up windows next to each other and we haven't hit the max amount of double apartments, assume it is a double apartment. Otherwise, treat it as a single apartment. And then, once I hit the max value for single apartments I treated every next pair of windows as a double apartment, and the same thing for single apartments.

My idea for calculating max : If there are two dim windows next to each other and we haven't hit the max amount of double apartments, assume it is a double apartment. If there is one dim window and a lit up window next to each other, treat it as a double apartment. Otherwise, treat it as a single apartment. And then, once I hit the max value for single apartments I treated every next pair of windows as a double apartment, and the same thing for single apartments.

My code : https://mirror.codeforces.com/contest/1804/submission/197105009

Thanks in advance for help.

Didn't like B, but C was cool ;)

Why I get wa on pretest 2 in that code in problem A:

https://mirror.codeforces.com/contest/1804/submission/197096441

I very much liked E, F and H!

This is the best contest I have ever seen, I guess. Here are my approaches:

I think this is a really good contest. Thanks for all the efforts. Upvoted :D

Nice E!And C,D are also interesting.

I have no idea why my C (197116314) got accepted. Pure luck I think.

Am I the only one, who thought that Question C was easier than Question B?

Link:- https://mirror.codeforces.com/contest/1804/submission/197135076 my solution for B question. It's giving TLE for test case 37. I think the time complexity of above code is 2*n which is O(N) but why I am still getting TLE. Please help me out.

ImplementationForces, ObservationForces, LuckForces all satisfy today's contest. What is going on with CF? No need to force for contest number instead I want quality over quantity. We want quality like older contests, now it's like we r just lucky to get through a ques or not at all. Not learning much stuff from contests nowadays. Pls just decrease the contests numbers and make some pretty questions. :/ pls

Can someone tell me the mistake in my logic of C ? https://mirror.codeforces.com/contest/1804/submission/197111331 Thanks in advance !!

I am checking for every cycle of n and updating the starting point after each operation. The moment a possibility arises inside p, or n goes beyond p, or a repetition in starting point arises(hence it is under O(n)), I am returning the answer. ( I know the simpler solution now, just want to understand mistake in my one)

Fun fact: 173 submissions passed pretest and got FST(30.8% among all submissions which passed pretests) at 1804E - Routing. Maybe they didn't see $$$O(N^3*2^N)$$$ solutions could pass pretests :(.

Can anyone help me find out what's wrong with my code? It fails for the maximum part.

I first find all the '01' and '10'. Then I find '00' until there is no double size room remained. If after this process, we still have remain double size rooms. Then these rooms should be occuppied by '11'. It passes the visible part of pretest5.

Python Code

PLEASE HELP ME, I dont know why my solution for C goes TLE if its o(N) only https://mirror.codeforces.com/contest/1804/submission/197134868

How many CPU days do rating changes take? (I'm guessing they are not rolling out because of cheaters)

why problem A is the same problem with the same solution from another contest!!

1452A - Robot Program

Why has my rating been decreased suddenly without any email or any error from 915?? And it's not showing rating of last two contest?? please reply

Just be notified that I'm being skipped for this contest due to the significantly coincides with jiangly's solutions 197093293 from mine 197126608 for problem F. Yeah the code is exactly the same to my surprise.

I suppose once figuring out the problem F, the solution is very limited: building graph with query stamp on the edge, writing a BFS lamdba and do several binary searches. These steps are independent, very standard which is easy to write the same code.

Finally, I don't think I have the ability to ask the round winner jiangly for the code sharing. Hope there will be a fair reply and judge, thanks.

Rating have rolled back for this round. What is the reason???

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

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.

import requests

contests = [1804]

# [1, rank_start) get tshirts with no random
# [rank_start, rand_end] get random tshirts
rank_start = 26
rank_end = 200

n_random_tshirts = 25

def is_eligible(contest, party_name, rank, points, problems, last_submission_time):
    #return problems >= 1 and (not (party_name in new_accounts)) and rank <= rank_end
    return (rank <= rank_end)

def get_new_accounts(contest_id):
    rows_to_fetch = 20000
    r = requests.get('https://mirror.codeforces.com/api/contest.ratingChanges?contestId=%d' % (contest_id))
    if r.status_code != 200 or r.json()['status'] != 'OK':
        print('Error: failed to fetch results of contest %d.' % contest)
        exit()
    parties = set()
    results = r.json()['result']
    for row in results:
        if row['oldRating'] == 0:
            parties.add(row['handle'])
    return parties

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 = []

new_accounts = get_new_accounts(contests[0])

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