Hello, Codeforces!
Zlobober
and I are glad to invite you to compete in Nebius Welcome Round (Div. 1 + Div. 2) that will start on
12.03.2023 17:35 (Московское время)
. The round will be rated for everyone and will feature 8 problems that you will have 2 hours to solve.
I feel really thrilled and excited about this round as this is the first time I put so much effort in a Codeforces contest since I quit being a round coordinator in December 2016 (wow, that was so long ago)!
We conduct this round to have some fun and we also hope to find some great candidates to join Nebius team. Solving 5+ problems in our round will be a good result and will count as one of the coding interviews. Apart from that top 25 contestants and 25 random contestants placed 26-200 will receive a branded Nebius t-shirt!
Some information about Nebius. I have joined this new start-up in cloud technologies in November as a head of Compute & Network Services. It's an international spin-off of Yandex cloud business with offices in Amsterdam, Belgrade and Tel Aviv. We offer strategic partnerships to leading companies around the world, empowering them to create their own local cloud hyperscaler platforms and become trustworthy providers of cloud services and technologies in their own regions.
We know that competitive programming makes great engineers. It boosts your algorithms and coding skills, teaches you to write a working and efficient code. We aim to hire a lot of backend software engineers for all parts of our cloud technology stack that ranges from hypervisor and network to data warehouse and machine learning.
Here you can check
Nebius website
and
open positions
. If you feel interested in joining Nebius as a full-time employee, go on and fill the
form
.
Fill in the form →
Special thanks go to:
-
MikeMirzayanov
for his outstanding, glorious, terrific (you can't say enough, really) platforms Codeforces and Polygon
-
74TrAkToR
and
K
AN
for this round coordination (and for rounds coordination in general, good job lads!)
-
ch_egor
for his help with one of the problem that has a peculiar setting which we will discuss a lot in the editorial
-
UPD
Now that the list is complete we can say many thanks to all the testers!
dario2994
,
errorgorn
,
magga
,
golikovnik
,
Hyperbolic
,
Farhan132
,
IgorI
,
vintage_Vlad_Makeev
,
aymanriadsolh
,
Vladik
,
Junco_dh
,
dshindov
,
csegura
,
Eddard
,
Alexdat2000
,
kLOLik
,
wuruzhao
,
Aleks5d
,
Ryougi-Shiki
,
qrort
,
ak2006
,
AsGreyWolf
,
farmerboy
,
vladukha
,
usernameson
,
ZiXeL
,
DzumDzum
,
Java
,
samvel
,
mister
,
Tensei8869
, thank you for all your help on improving this round's quality!
Fingers crossed all will be well, you will enjoy the round and we will be back with a new one in several months!
UPD2
The scoring distribution is 500 — 1000 — 1000 — 1500 — 2000 — 2750 — 3500 — 3500.
UPD3
The editorial is
here
!
UPD4
Congratulations to winners!
1-st place:
j
iangly
2-nd place:
t
ourist
3-rd place:
U
m_nik
4-th place:
isaf27
5-th place:
O
rmlis
UPD5
T-shirts
winners
!
I have received a mail that my solution of C problem in Nebius Welcome Round is coinciding with Somebody else . In mail it was written , to post about the evidence .
C Problem was not too difficult for a person with average coding skills . The only trick in C was to get a control over the loop . I have seen many tutorials of past contests and in C problem , I used that for controlling the loop as the most common approach in these types get solved in nlog(n) or n root(n) . So I did it for n root(n) and then the code was simple a Brute force logic . It took me a number of contest and practice to reach specialist . Please reply me if i need to submit any supporting proof and what else can i upload . Please help
GlebsHP
,
MikeMirzayanov
. please do reply.
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....
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.
do brute force for every 1 <= k <= min(p,2*n) for the value f=k since if no f in this interval satisfy region 0 as result, it is guaranteed that there exist no k value such that with f = k <= p, it'll land on region 0 (guaranteed to work since sum of n from all test cases only reaches 200000) (also this works since the roulette is basically a mod n complete residue system)
Basically the problem asks for if there exists a value $$$1\leq i\leq p$$$ such that $$$x + \frac{i (i+1)}{2}$$$ is divisible by $$$n$$$.
Since For $$$i>n$$$ we can break the fraction into something like $$$\frac{(an+b)(an+b+1)}{2}$$$ you know testing $$$i$$$ until $$$n$$$ will be enough because you think it's just a repeating pattern afterwards — no, don't forget there is a 2 in the denominator, the pattern length can be as long as $$$2n$$$.
My approach:
Given $$$f$$$, the displacement is $$$\frac{f(f + 1)}{2}$$$. We want $$$x + \frac{f(f + 1)}{2} \equiv 0 \pmod n$$$. But this is equivalent to the existence of $$$q$$$ for which $$$x + \frac{f(f + 1)}{2} = qn \iff 2x + f(f + 1) = 2qn$$$. So we can simply try each value of $$$f$$$ from $$$1$$$ to $$$\min (2n, p)$$$ to see if $$$2x + f(f + 1) \equiv 0 \pmod {2n}$$$. We don't need to check beyond $$$2n$$$ because the LHS only contains multiplications and additions, which are invariant under modulo, i.e., trying $$$f$$$ yields the same result as trying $$$f \bmod (2n)$$$.
(Note that division is not modulo-invariant, so trying $$$x + \frac{f(f + 1)}{2}$$$ for $$$f$$$ from $$$1$$$ to $$$n$$$ is not sufficient; you have to try until $$$2n$$$)
Personal take: ImplementationForces sometimes is actually good! Many real-life problem only require brute-force, yet hard solutions. ICPC-style contests also features many implementation-heavy problems. You do not need crazy algorithms or math knowledge to solve C,D, yet the amount of solves are perfect for problems of that level. Stress testing for D to find the exact solution is also a skill we need to have in real-life programming... The problems are also not misleading, so the only person that you can blame if you WA is you, right?
Math knowledge: Sum from 1 to N is N (N + 1) / 2.
Modulo knowledge: T (T + 1) mod N = (T + N) (T + N + 1) mod N
Therefore, just check I from 1 to N for I * (I + 1) / 2 + X mod N == 0.
That's what I thought, but WA on case something... change for from 1 to N to 1 to 2 * N works, but I don't understand how :D
My intuition behind it is because of something like this :
If $$$\frac{d(d+1)}{2} mod N = T$$$, then at some point, it will produce some modulo cycle (e.g. adding movement with the value of $$$d_1$$$ will results in the same finish point for another value of $$$d_2$$$ for some value $$$d_1 < d_2$$$)
And the cycle will repeats every $$$2N$$$ times. Because when $$$d = 2N$$$, then the value of $$$\frac{d(d+1)}{2}$$$ will be $$$\frac{2N(2N+1)}{2} mod N$$$ or $$$N(2N+1) mod N = 0$$$ because $$$N(2N+1)$$$ is a multiple of $$$N$$$
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);
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);
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://codeforces.com/contest/1804/submission/197124751
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.
For problem E, i don't think you solution is correct.
Take care of this testcase:
7 8
The node $$$4$$$ can directs the calls only on one side. Am i missing something?
for problem B ... my idea was to let the patients wait as long as possible by add arrival time with w and make it the start of first session and add d to start time and make it the end of session ...... so every patient within that time slot get vaccinated ...... here's my submission can anyone tell me where i went wrong ?
https://codeforces.com/contest/1804/submission/197143526
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://codeforces.com/contest/1804/submission/197105009
Thanks in advance for help.
Thank you very much I understand now.
Int overflow issue with code, should have just accepted input as a string.
Appreciate the help.
Edit: still getting WA on test case 3 even after fixing input method. What else is wrong? code now works for your example case.
Edit: new code
https://codeforces.com/contest/1804/submission/197135065
Try this counter example:
1 100
0110001100110000110110111000001000010100000011011100011100110001011100101011010010010110110010000101
Answer:
30 44
And these:
1 60
101000011101110101111010011110110010001010000110111111111000
Answer:
22 34
11111100110111111110
Answer:
11 15
This is the best contest I have ever seen, I guess. Here are my approaches:
Solution for AProblem A is just greedy; if you have solved some grid problems like this, you would know this. It is good and optimal if we go only in 2 directions; for example, it can be up, left, up, left... or up, right, up, right.... or etc. But this is useful when the difference between absolutes of coordinates is at most 2. If you want the proof, just take two coordinates with the difference of absolutes at most 1 and check. If it is like this, then solution is abs(a) + abs(b). Else again, you go like this till when we reach the same line with the maximum coordinate, and we go remaining part twice to reach that coordinate.
Solution for BFor B, solved with binary search. Let's take the opening of one packet with a[i]. Now we need to vaccinate all patients. For this, we need to open a packet as late as possible, because we need to find the minimum number of packets. So, we try to open each packet as late as possible. Through this, we can take more people. Now we want to open a packet as late as possible, then we will push limits, we will open the packet at a[i] + w(the limit of the patient), and then the packets limit will be a[i] + w + d(the packet limit). So we just go to the upper bound here and calculate the answer.
Solution for CSo this is a nice math problem. In short, we need to check there is a value y which is 1 <= y <= p and x + y * (y + 1) / 2 mod n = 0 Here, if we loop till p, it will give TLE. So to avoid this: y * (y + 1) / 2 = (y^2 + y) / 2 (y^2 + y) / 2 = ((y + 1/2)^2 — 1/4) x + ((y + 1/2)^2 — 1/4) mod n == 0 => 2x + (2y + 1)^2 mod 4n == n Now we see that we can iterate from 1 to 2 * n and check if there is an answer. That is it.
I think this is a really good contest. Thanks for all the efforts. Upvoted :D
You'll find that the task is just find whether there's an $$$y$$$ that $$$\frac{y(y+1)}{2}+x\equiv 0\pmod n$$$.
If n is odd,it's obvious that there's no influence to calculate with $$$y$$$ or $$$y\bmod n$$$,using $$$\frac{y(y+1)}{2}$$$ or $$$2\times(n-x)$$$ because 2 has its inverse.In that case since you find one,then it is correct and ends with f=0
.So it's $$$O(n)$$$.
If n is even,it goes a bit complex.Set y as $$$kn+b$$$,where $$$1\le b\le n$$$,then recalculate the left and you'll get $$$\frac{k}{2}n+\frac{b(b+1)}{2}+x$$$,and in the first check both part were doubled so $$$+\frac n2$$$ has no influence.Then it has only 2 situations depending on $$$k\bmod 2$$$,so f
could only be $$$0$$$ or $$$1$$$ and there's a result.Also it's $$$O(n)$$$
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
I know concepts were there, but no one can deny that older contests were fun, they were less but had good concepts, but i dont see much now. A was simple maths for most of us, B was binary search?, I did sliding window only :/, and regarding C huh, I cant comment bcz I was mad after getting to the logic there. But all have perspectives and I wish they just add some different problems.
Can someone tell me the mistake in my logic of C ? https://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)
Well I couldn't understand your solution there. But I will try to explain an easier solution.
Basically we have to go from sector x to 0. By selecting a force f
the arrow moves (f*(f+1)/2)%n
sectors ahead. Or it moves from x to x + (f*(f+1)/2) % n
. So we need to find a particular f
such that the resultant sector is 0. We can find this f
by iterating over min(p,2*n)
and checking for every number i
whether it satisfies our condition
(i*(i+1)/2)%n = (n-x)%n
If the condition is satisfied we can be sure i
is our answer.
Why min(p,2*n)
?
Because the force f
to be applied must be smaller than p
. Also the remainders for the operation (i(i+1)/2 )%n
repeats after every 2*n
numbers for even n
and it repeats after every n numbers for odd n
. Hence if there is no number from 1 to 2*n
which will satisfy our condition then there is guarantee that there will not be any number > 2*n
which will satisfy the condition.
My submission: https://codeforces.com/contest/1804/submission/197106694
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
for the maximum, let's pick the double size rooms, the only bad pick is 11 because we lose a 1, so we count how many good picks we can do:
cnt = 0
for (int i = 0; i + 1 < m; i++)
if (s[i] != '1' || s[i + 1] != '1')
i++, cnt++;
then the numbers double size rooms left is max(0, m / 4 — cnt) each of these rooms will be 11 which means we will lose a 1. and to get the answer we just subtract this number from the number of ones in the string.
I have received a mail that my solution of C problem in Nebius Welcome Round is coinciding with Somebody else . In mail it was written , to post about the evidence .
C Problem was not too difficult for a person with average coding skills . The only trick in C was to get a control over the loop . I have seen many tutorials of past contests and in C problem , I used that for controlling the loop as the most common approach in these types get solved in nlog(n) or n root(n) . So I did it for n root(n) and then the code was simple a Brute force logic . It took me a number of contest and practice to reach specialist . Please reply me if i need to submit any supporting proof and what else can i upload . please do 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.
I have received a mail that my solution of C problem in Nebius Welcome Round is coinciding with Somebody else . In mail it was written , to post about the evidence .
C Problem was not too difficult for a person with average coding skills . The only trick in C was to get a control over the loop . I have seen many tutorials of past contests and in C problem , I used that for controlling the loop as the most common approach in these types get solved in nlog(n) or n root(n) . So I did it for n root(n) and then the code was simple a Brute force logic . It took me a number of contest and practice to reach specialist . Please reply me if i need to submit any supporting proof and what else can i upload .
Please upvote.
Please help MikeMirzayanov . please do reply.
I just went through both submissions and I think they are similar. But I don't think they should be treated as plagiarization.
Here are the reasons:
For this problem F, there are 3 parts, graph building from input, binary search to get the ans, BFS to get the max dis.
From submission 181795376, we can see the graph building and BFS are exactly the same,
From submission 122792860, we can see the binary search part is exactly the same.
So I think the similarity is just a coincidence just because sd0061 and jiangly having similar coding styles.
Besides that, I also don't think Codeforces is doing the right thing when 2 similar codes are found, Codeforces skipped sd0061 but not jiangly. I think if such a case is found, both side should be skipped.(in this particular case, I think both of them are innocent and should not be skipped)
If we just read the author's submission history that the coding style is consistent. And I think one seemingly possible reason (apart from code logic) for sd0061's code being detected as duplicate code of jiangly's code is that both:
- use
std::
prefix - use lambda instead of global defined functions
Basically, if two coders use mordern c++ features and have a good coding style, once the room for algorithm implementation is limited, it's quite possible that the codes reads similar. We should allow human re-evaluation for such cases, not blindly skip the submissions.
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.
get_tshirts.py
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://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://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))
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;
The only programming contests Web 2.0 platform
Server time: Aug/19/2023 08:31:40 (g1).
Supported by