By Anadi, 4 years ago,

I would like to invite you to participate in the rated Codeforces Round #519 by Botan Investments. Date and time of the round: Oct/28/2018 18:35 (Moscow time).

This is a combined round having 7 problems and lasting 2 hours, and it will be rated.

Tasks for you were prepared by Anadi, Grzmot, isaf27 and Rzepa. Also thanks for:

KAN and cdkrot for help in preparing the problems; pavel.savchenkov, Nerevar, map, GR1n, rutsh, AlexFetisov and winger for testing the round; MikeMirzayanov for Codeforces and Polygon platforms.

The round is supported by Botan Investments.

Prizes! Top 50 participants and 20 random participants with rank from 51 to 500 will receive personalized hoodie with CF handle.

Scoring distribution will be announced later. I wish you a high rating and looking forward to see you at the competition!

UPD: I'll be on the community Discord server shortly after the contest to discuss the problems.

UPD: Scoring: 500 1000 1500 2000 2250 2750 3500

UPD: Editorial

The round is over, congratulations to the winners!

• +544

 » 4 years ago, # |   +142 Clashes with El Clasico:(
•  » » 4 years ago, # ^ |   -58 Why do all residents of Kazakhstan like La Liga?
•  » » 4 years ago, # ^ |   +55 El Clasico clashes with CF #519, not other way around :(
•  » » 4 years ago, # ^ |   +75 Leo messi is injured, so he has chance to get a hoodie :))
•  » » » 4 years ago, # ^ |   +74 Messi it is your chance.
•  » » » 4 years ago, # ^ |   +4 we can see Messi and ronaldo both getting hoodies ! :D Good luck for all !
•  » » » » 4 years ago, # ^ |   +136 Even in CP Messi is better than Ronaldo.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Hmm, I guess you meant only in CP!
•  » » » » » 4 years ago, # ^ |   +11 Ronaldo plays in Juventus...
•  » » » 4 years ago, # ^ | ← Rev. 4 →   +8 Leo had brought his laptop to the stadium! :))
•  » » 4 years ago, # ^ |   +7 El clasico has started
 » 4 years ago, # |   +71 Wow, top 500 will have the opportunity to receive personalized hoodie with CF handle. Hope to receive it. Good luck.
 » 4 years ago, # | ← Rev. 2 →   -38 Mr Anadi what will you do during contest? watching your favorite team match or answer participants questions ???!
•  » » 4 years ago, # ^ | ← Rev. 2 →   -63 FCB stands for something else. ;)
•  » » » 4 years ago, # ^ |   +56 I am curious. For what my nick stands?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   -50 We have just talked about it yesterday, don't you remember? I won't announce it publicly cuz I'm a well-behaved person, but others can still guess :p
•  » » » » » 4 years ago, # ^ |   +110 I always thought it is FC Barcelona :/.
•  » » » » » » 4 years ago, # ^ |   +22 It can be FC Bayern :D
•  » » » » » 4 years ago, # ^ |   +11 You know I don't like to guess.Just tell me which one is it?? :|
•  » » » » » » 4 years ago, # ^ |   +9 friends of canadian broadcasting
•  » » » » » » 4 years ago, # ^ |   +19 First one, as I wrote above. But kostka has some ugly thoughts about it.
•  » » » » » » » 4 years ago, # ^ |   -49 Fuck club barcelona?
•  » » » » » 4 years ago, # ^ |   -22 Frequency Channel Blocking?
 » 4 years ago, # |   +6 "Prizes! Top 50 participants and 20 random participants with rank from 51 to 500 will receive personalized hoodie with CF handle." -- That's awesome, I wish to get under 500. Ah! But i still struggle with Div 2 C :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   -16 0.044 is not bad percent :P good luck wish you the best
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +25 actualy 20 / 450 = 4.4%
•  » » » 4 years ago, # ^ |   +68 Er, if this contest is Mathforces I wish you good luck.
 » 4 years ago, # |   +44 Wish a hoodie be with you (and me) :D
 » 4 years ago, # | ← Rev. 2 →   +10 why can't I register for the contest? it says I must have a rating between 9 and 9,999UPD: it's fixed now !!
 » 4 years ago, # |   +2 I'm glad to invite you to take part in Codeforces Round 519. Actually it will be two separate rounds "Codeforces Round #519 (Div. 1 Only)" and "Codeforces Round #519 (Div. 2 Only)". The division problemsets will share many problems, but not all of them will be the same. So, Div. 1 users should register on "Codeforces Round #519 (Div. 1 Only)" while Div. 2 users should register on "Codeforces Round #519 (Div. 2 Only)".This is what is written in the invitation mail I received.
•  » » 4 years ago, # ^ |   +3 Email is wrong a bit, this is going to be a combined round.
 » 4 years ago, # |   +17 Awesome idea for giving hoodie to random guys, chance for non-red guys get a hoodie.
 » 4 years ago, # |   +68 Could we get a picture of what the hoodies look like (for extra motivation)?
 » 4 years ago, # |   +35 I like these random gifts, as usually all of the prizes only go to the same top users.
 » 4 years ago, # |   -31 unfortunately , The contest will be at the same time as the Clasico match .
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 If a red said this would it still be -22 contribution dont be rankist!
 » 4 years ago, # |   +87 What do the hoodies look like?
•  » » 4 years ago, # ^ |   +8 Congrats Michael!
 » 4 years ago, # |   -28 Anadi, are you Indian?
•  » » 4 years ago, # ^ |   0 He´s polish
 » 4 years ago, # |   0 It's a great pity that I cannot join in the match because I have to get up early tmorrow.
 » 4 years ago, # |   +1 Look at my registration date. Do you see it too?
 » 4 years ago, # |   +1 Good Luck on contest!
 » 4 years ago, # | ← Rev. 2 →   +28 Is there any way to buy these hoodies ?
 » 4 years ago, # |   -46 I don't understand why make it today and in same time with big football game that many people want to watch ?It is not a round with onsite contest in same time, it is a normal round that can be delayed or shifted one day, there are many people here includes me that want to watch the game and take part in the contest why we can't do both ?I think it is not late to delay it to tomorrow or just today after the game
 » 4 years ago, # | ← Rev. 2 →   0 try a try, ac is ok. Fighting!
 » 4 years ago, # |   +10 I have never been so confused. Can't decide whether to give contest or watch El Classico.
 » 4 years ago, # | ← Rev. 3 →   +75 The random winners will be determined with these two scripts:Where seed is the number of points of the winner of the next contest, length is 450 (500 - 50) and nwinners is 20. randgen.cpp#include "testlib.h" #include using namespace std; int main(int argc, char *argv[]) { if (argc < 4) { cout << "Command line arguments are: seed length nwinners" << endl; return 1; } int seed = atoi(argv[1]); int len = atoi(argv[2]); int nwinners = atoi(argv[3]); rnd.setSeed(seed); set winners; while (winners.size() < nwinners) winners.insert(rnd.next(1, len)); for (auto winner: winners) cout << winner << " "; cout << endl; return 0; }  get_ranklist.pyimport requests contests = [1043] def is_eligible(contest, party_name, rank, points, problems, last_submission_time): return 51 <= rank <= 500 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 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.') exit() for idx, party in enumerate(eligible): print('{} {} {} {}'.format(idx + 1, party.contest, party.rank, party.name)) print('Total %d eligible.' % len(eligible)) exit() # comment to see winners winners = list(map(int, input().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)) 
•  » » 4 years ago, # ^ |   +4 What would happen if some concestants share the place and it would be choosen by generator?
•  » » » 4 years ago, # ^ |   0 they are tied by the time of the last accepted as i know
•  » » » » 4 years ago, # ^ |   0 This does not make sense in cf :) Only in acm :)
•  » » » » » 4 years ago, # ^ |   0 i remember this was used previous times when there were random prizes
•  » » » » » » 4 years ago, # ^ |   0 Then I have no chance :) One person submitted before, one after :D
•  » » » » » » » 4 years ago, # ^ |   +8 If I understood it correctly, you do have chance. I think each person is untied by the time of the last submission, so every one gets a different ranking.
•  » » » » » » » » 4 years ago, # ^ |   0 HaHa
•  » » 4 years ago, # ^ |   +55 Why was seed not taken as max points by winner in this contest? Any reason?
•  » » » 4 years ago, # ^ |   0 Probably more for historical traditions. Maybe it won't be true for the new random's :)
•  » » 4 years ago, # ^ |   +8 but is it determined?
•  » » 4 years ago, # ^ |   -8 Is it normal, that randgen.cpp can give number less than 20? For example, with seed 1234, it give 17. There is invalid syntax in get_ranklist.py in line 59. My python don't now —
•  » » » 4 years ago, # ^ |   +8 rangen.cpp generates numbers from 1-450, and in get_ranklist.py 50 is added Replace all — s to — signs. It's a formatting error by copying from somewhere.
•  » » 4 years ago, # ^ |   +23 There will be 3 parallel contests, which's score will be the seed?
•  » » » 4 years ago, # ^ |   +10 The onsite round will be used
 » 4 years ago, # | ← Rev. 3 →   -83 Please shift the round by 1.5 hrs. El classico comes only twice every year. Please I beg you! cdkrot Anadi
 » 4 years ago, # | ← Rev. 2 →   -15 Expect problem statements to be short in size. Wishing everyone high ratings. :)
•  » » 4 years ago, # ^ |   +1 I'll hack you down!
•  » » » 4 years ago, # ^ |   +11 I will be more than happy if you hack me down, at least I will have a chance to recorrect rather then failing on sys test. :)
•  » » » » 4 years ago, # ^ |   +3 But what if he performs the hack at 1:59 :)
•  » » » » » 4 years ago, # ^ |   +16 Even if he did not, it would not pass sys test. No harm in him hacking my code :D
•  » » » » » 4 years ago, # ^ |   0 glad to meet ya at the dark side
 » 4 years ago, # |   +43 First time participating in a contest. Hope to solve atleast one
 » 4 years ago, # |   +14 Score distribution?
 » 4 years ago, # |   -22 Lol. Why is there an unusually large number of reds and nutellas participating in this round?
•  » » 4 years ago, # ^ |   0 will receive personalized hoodie with CF handle That's why.
 » 4 years ago, # |   -8 likle adn subvurncwe
 » 4 years ago, # |   -16 which one is more important elclasico or contest? ;)
•  » » 4 years ago, # ^ |   +7 football is for monkeys :D
 » 4 years ago, # | ← Rev. 2 →   +14 Lol, dotorya_.dotorya is the last person you should've done this with though.
 » 4 years ago, # | ← Rev. 2 →   +4 To those football fans competing in this round, I am not saying that you are making a wrong decision, but unfortunately it seems like you have just missed an epic El Clasico match :'(But well, I am probably missing my chance for hoodie as well, so yeah.
 » 4 years ago, # |   0 Barca 5 — 1 Real :))
 » 4 years ago, # |   +83 >those names in A
•  » » 4 years ago, # ^ |   0 Also in F. It is pure gold indeed.
 » 4 years ago, # |   +41 How to solve F?
•  » » 4 years ago, # ^ |   +19 Maybe this strategy will help: https://cs.stackexchange.com/questions/10249/finding-the-size-of-the-smallest-subset-with-gcd-1
•  » » 4 years ago, # ^ |   +12 it can be observed if the answer exists, then it's no more than 7. For each possible answer, check if it's valid by Mobius inversion.
•  » » » 4 years ago, # ^ |   0 Why is the answer guaranteed to be no more than 7?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +16 Actually, it should be no more than 6, since 2 * 3 * 5 * 7 * 11 * 13 * 17 > 300000, and if the gcd = 1 can be reached, one should at least be able to remove at least one prime divisor for each move(i.e, add another element).
•  » » » » » 4 years ago, # ^ |   0 That makes sense. Thank you!I have one more question, you said, "For each possible answer, check if it's valid by Mobius inversion." There are N^6 possible answers so how do we check them?
•  » » » » » » 4 years ago, # ^ |   0 Say if you want to check if it's possible to choose a subset of size k such that their gcd equals to 1. Let f(x) denote the number of possible choices such that the gcd of the subset equals to x, and g(x) denote the number of possible choices such that the gcd of the subset is a divisor of x, so that one can apply Mobius inversion on it. The time complexity is O(6 × 300000). All precomputations can be done in linear time.
•  » » » » » » » 4 years ago, # ^ |   0 Could you please provide the explicit formulas? What I've extracted from your code is that g(x) stands for the number of choices such that gcd is divisible by x (but is not a divisor of x).
•  » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +16 Let f(x) denote the number of possible choices such that the gcd of the subset equals to x, and g(x) denote the number of possible choices such that the gcd of the subset is a divisor of x, then Mobius inversion states that , and the answer lies in f(1). So you have to compute to g(x), which only requires one to for each ai, add all its divisors by one.
•  » » » » » » » » » 4 years ago, # ^ |   0 Ok, thank you.
•  » » » » » » » » » 4 years ago, # ^ |   0 Your algo is very fast , wow!!!45032590
•  » » » » » 4 years ago, # ^ |   +31 Actually it is 7. Take 2 * 3 * 5 * 7 * 11 * 13 * 17 and delete each number once. You will have 7 numbers and each must be choosen.
•  » » » » » » 4 years ago, # ^ |   +5 Oh. That's correct. My bad.
•  » » » » » 4 years ago, # ^ |   +3 Actually, the answer can be 7, since 3 * 5 * 7 * 11 * 13 * 17 < 300 000.Note that you have to also count the initial integer. 1 (initial) + 6 (removing divisors) = 7.
•  » » » » » » 4 years ago, # ^ |   0 Can you give us a actual test case?
•  » » » » » » » 4 years ago, # ^ |   +44 7 30030 39270 46410 72930 102102 170170 255255 
•  » » » » » » » » 4 years ago, # ^ |   0 Thanks!
•  » » 4 years ago, # ^ |   +10 I built a graph where each vertex is a product of distinct primes and there's an edge from a product to a subset-product whenever there is an input number coprime to the subset-product. How many input numbers are there coprime to x? That can be computed using inclusion-exclusion (you need to compute how many are divisible by each number first).
•  » » 4 years ago, # ^ | ← Rev. 2 →   +13 first the do the basic checks and also remove duplicate primes in each number. For each value in 1 to 300000 count number of numbers which have gcd!=1 with that value(lets call gg[val])(using mobius function this is easy). Now we can construct graph with edges between two numbers(x and y) if x divides y/x and gg[x]!=n.Answer is shortest distance to a vertex from 1 in this graph +1.
•  » » 4 years ago, # ^ |   +5 Use dpx — amount of numbers to get 1 if you took already some numbers with gcd = x.To calculate dpx, we need to check for each divisor dj of x: is there a number ai such that gcd(x, ai) = dj. To do this, we calculate another DP dqx, a (a is divisor of x)— amount of ai in the array such that gcd(x, ai) = a. Calculation of this dp looks like this (suppose wx is amount of numbers in ai which have x as a divisor): for i in rev(divisors[x]): # divisors[x] are in ascending order dq[x, i] = w[i] for j in divisors[i]: if i != j: dq[x, j] -= dq[x, i] It's easy to see that recalculation of all the dq's take no more than (faster in practice)Of course, we will keep only one dimension of dpx, a for current x to fit into memory limit.And, in the end, we solve the original dpx in the following way: dpx = min(dpy) + 1, where exists ai such that gcd(x, ai) = y.
 » 4 years ago, # |   0 how to solve c ?
•  » » 4 years ago, # ^ |   +3 Have a variable cur = array[0]. Loop from 1 to n-1. if(cur == a and array[k] = b and array[k+1] == a), then you should swap at k and set cur to b. If cur == b and array[k] == a and array[k+1] == b, then you should swap at k and set cur to a. If you finish and cur == b, then you should swap at n-1.
•  » » 4 years ago, # ^ |   +8 You can always rearrange the string to make every 'a' stands before all 'b's.To do this, we will traverse through the string and find substrings (consisting of consecutive characters) that all characters of it are 'a'. Let's denote the substring S[L, R].It's easy to say we will reverse prefix L - 1 (if it exists) and prefix R.Total complexity is O(N) with two-pointers. Naive solution in O(N2) is still acceptable with the given constraints.
•  » » » 4 years ago, # ^ |   +16 There is also DP solution: for every prefix of length i store lexicographically minimal and maximal string obtainable by doing first i rotations.
•  » » 4 years ago, # ^ | ← Rev. 4 →   +5 With regexes. To substitute all a+ or b+ (but not b+ (longest) at the ending of the string) by '0' * length_of_a_match + '1' — Perl code: 45056981. Or, Algo_Rhythm's variant with regexes: 45058519
 » 4 years ago, # | ← Rev. 4 →   +94 Am I the only one who didn't read The string s consists only of characters 'a' and 'b'. in problem C, and solved it for general strings?
•  » » 4 years ago, # ^ |   +5 I've noticed it just now by reading this comment. I was blown away when I saw so many people solved C so fast. Damn!
•  » » » 4 years ago, # ^ |   0 I was just astonished by so many submissions, until I went into hacking room and saw a 3 lines code :(
•  » » 4 years ago, # ^ |   0 I did the same :( Btw, how can it be solved for general strings?
•  » » » 4 years ago, # ^ |   +24 Our operations are equivalent to appending each character in order to either the beginning or end of the string. In the lexicographically smallest string, we want to put all a's into the beginning of the string. This means that after the first 'a', we put everything but a's into the end. Before the first 'a', we want to put nothing but b's to the beginning of the string, and so on.So Greedy still works, you just check if the current letter is smaller than or equal to all previous letters. If it is, add it to the beginning, otherwise add it to the end.
•  » » » » 4 years ago, # ^ |   +1 Could you describe more in terms of reverting or not reverting a prefix. For example for string bazab how would you iterate over this string and make greedy decisions? If we iterate from last to first char in the string, once we find a we want to reverse the prefix baza and it also means that we want to maximize prefix baz. And to maximize prefix baz we want to reverse it and minimize prefix ba, so we want to reverse ba too. Would it work if we store char[] maxOnPrefix and char[] minOnPrefix to make decisions greedy? During contest I solved this problem for generic string with dp.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 Our operations are equivalent to appending each character in order to either the beginning or end of the string.Consider "bazab", iterate over each character."b"append a in begining "ab"append z in end "abz"append a in begining "aabz"append b in end "aabzb"
•  » » » » » » 4 years ago, # ^ |   +3 Ok, but how to produce the answer out of this? How to know what prefixes we want to reverse?
•  » » 4 years ago, # ^ |   0 Bruh me too xD
 » 4 years ago, # |   +8 How to do E? I don't see how you can do it faster than O(n^2)
•  » » 4 years ago, # ^ |   +9 You may compare the difference of x[i] and y[i], say d[i] = y[i] - x[i] for every competitor For two competitors i and j, if d[i] <  = d[j] then i should solve the second one.Binary search on how many competitors have higher d[] then himself and the answer can be calculated using prefix sum.
•  » » » 4 years ago, # ^ |   0 don't forget to subtract scores of m pairs after that.
 » 4 years ago, # |   0 Does somebody know pretest 3 for C or pretest 7 for D?
•  » » 4 years ago, # ^ |   +13 Pretest 3 for C can be baaaa.
•  » » » 4 years ago, # ^ |   +224 That's what sheep said.
•  » » » » 4 years ago, # ^ |   0 Nice
 » 4 years ago, # |   +2 Why everyone solved D....So,how to solve it?
•  » » 4 years ago, # ^ |   0 Split the first permutation into largest substrings which appear in all other m - 1 permutations:1|2 3|42 3|4|14|1|2 31|2 3|4 If the length of the i'th substring is k[i], then the answer is: long long ans = 0; for (int i= 0; i < numberOfSubstrings; i++) ans += k[i] * (k[i] + 1) / 2; 
•  » » » 4 years ago, # ^ |   0 Thank you!
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Just finished my code 2 minutes after the contest. I used rolling hash and binary search. For each number i from 1 to n,find the longest subset obtainable starting with the value i. Complexity O(NMlogN). CMIIW.
•  » » » 4 years ago, # ^ |   0 I used rolling hash and binary search. That sounds too complicated :)We just need to test 2 consecutive digits in a permutation p[i] and p[i + 1] in order to test whether we can extend the current segment.
•  » » » » 4 years ago, # ^ |   0 won't this actually take O(N^2.M) tho ?
•  » » » » » 4 years ago, # ^ |   0 No. We are touching each element of array at most 2 times.
•  » » 4 years ago, # ^ | ← Rev. 4 →   +15 My personal ideas: The numbers from 1 to N can be seen as a directed graph, and I'll count the appearance of the pair (i, j), with i and j are the values of 2 consecutive elements on one permutation.If any pair appears exactly m times, then there will be an edge starting from u to v.With this given, it's certain that the graph will be a DAG, and there is no vertex having more than one edges pointing at it.So we can do a simple DFS from all sources to find the answer. With each source, if the total number of traversable vertices from it is x, add x * (x + 1) / 2 to the answer.UPD: I didn't take the TL seriously and my solution got TLE. Damn!Total complexity is O(NM * log(NM) + N).UPD2: Accepted solution (904ms): 45022094UPD3: Improved solution (171ms) from suggestion of mouse_wireless — complexity reduced to O(NM): 45031805
•  » » » 4 years ago, # ^ |   +8 Nice solution!Amazing!
•  » » » 4 years ago, # ^ |   +12 You can build the DAG from the first permutation. On each of the next ones, if you come across an edge that doesn't exist in the initial DAG, just delete it. This can be done in O(1), since each node can have at most one incoming and one outgoing edge.In the end, count the connected components in the resulting DAG and for each component add x * (x + 1) / 2 to the result (where x is the size of the component).By doing this, you eliminate the log factor.
•  » » » » 4 years ago, # ^ |   0 Right, I overkilled the solution. Good observation, man :D
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Oh well, I guess my solution was kinda different...Create the array ans[] where ans[x] is the amount of ways which start with number x in all permutations. Also, make the array pos[][] where pos[x][k] is the index where number k appears in permutation x. In particular, for num[m][n] (where num[x][y] is the yth number in permutation x), ans[num[m][n]] = 1. Now for any i with n-1 >= i >= 1 (a for loop where i decreases from n-1 to 1), take next = num[m][i+1]. Then, if for some j (1 <= j < m) num[j][pos[j][num[m][i]]+1] != next, we will have ans[num[m][i]] = 1. Otherwise, ans[num[m][i]] = ans[next]+1. Indeed, we know the value of ans[next], since we loop through i in decreasing order.Therefore, the answer for the problem is the sum of ans[x] for all x with 1 <= x <= n.
 » 4 years ago, # |   0 How to solve E? My idea was to do some sort of complementary counting but not sure how to get the sum for every team for person i in a fast way. Maybe there was some other observation?Also how did everyone solve D. I used hashing+binary search, and I thought it was weird so maybe someone has a better solution.
•  » » 4 years ago, # ^ |   +3 min(xi + yj, xj + yi) = xi + yj iff xi - yi ≤ xj - yj.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 For E, sort by x-y values since if x+b < y+a, then x-y < a-b. Then use prefix sums to calulate the sum.For D, I used hashing too, hope it doesn't give TLE in systests.
•  » » 4 years ago, # ^ |   +6 min(x[i] + y[j], x[j] + y[i]) = min(y[j] — x[j], y[i] — x[i]) + x[i] + x[j]a[i] = y[i] — x[i] a[j] = y[j] — x[j]min(x[i] + y[j], x[j] + y[i]) = min(a[i], a[j]) + x[i] + x[j]
 » 4 years ago, # | ← Rev. 2 →   +1 Can someone point out why my code for D is getting TLE for testcase 9 ? I guess it's O(mn) which shouldn't give TLE. I maybe wrong though. The main idea is simple: Consider a directed graph with n vertices, with an edge from i to j iff the numbers i, j are adjacent in all m permution. Note that for any vertex, ,and which vertex (if any) v is connected to can be checked in O(m), so for all vertex doing this takes O(mn). Now the answer is where ci ranges over the sum of connected components. Code for D#include #include #include using namespace std; typedef long long int ll; ll c2 (ll n){ ll ans = (ll)n*(n-1); ans = (ll)ans/2; return ans; } int main(){ int n, m; cin>>n>>m; int pos[n][m]; int arr[n][m]; for (int i = 0; i < m; i+=1){ for (int j = 0; j < n; j+=1){ int x; cin>>x; arr[j][i] = x-1; pos[x-1][i] = j; } } bool isroot[n]; int child[n]; for (int i = 0; i < n; i+=1){isroot[i] = true; child[i] = i;} for (int i = 0; i root; for (int i =0; i
•  » » 4 years ago, # ^ |   +15 I'm pretty sure it's just you're not using fast I/O. I TLE'd on 9 too and it passed once I fixed that
•  » » » 4 years ago, # ^ |   0 https://codeforces.com/contest/1043/submission/45019500 Any idea why this got a TLE? It's o(nmlogn) if I'm not mistaken.
•  » » » 4 years ago, # ^ |   0 same here. TLE on 7 using python3 then accepted using c++ scanf
 » 4 years ago, # |   +8 Is E solved using the fact that min(a+b) = (a+b-abs(a-b))/2?
•  » » 4 years ago, # ^ |   +23 min(x[i] + y[j], x[j] + y[i]) = min(y[j] — x[j], y[i] — x[i]) + x[i] + x[j]
•  » » 4 years ago, # ^ |   +5 I rather used the fact that xi + yj < xj + yi is equivalent to xi - yi < xj - yj -- and then you can just use variables zi = xi - yi.
 » 4 years ago, # |   -13 How to solve F??
 » 4 years ago, # |   +99 The problems were nice and interesting. But maybe the set together was easy.
 » 4 years ago, # | ← Rev. 3 →   0 What is the hack for B?
•  » » 4 years ago, # ^ |   +8 My solution was a brute-force check if constructing a valid x is possible for a given k. Got hacked because I initialised x to -1 each time, but x[i] can take value -1 sometimes...
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 Isn't a[i]-a[i-1]>=0?The second line of the output should contain l integers — possible lengths of the lost array in increasing order.
•  » » » » 4 years ago, # ^ |   0 That's the output. a[i] is the input array — that need not be in any particular order. Look even at the third sample (1 5 3)
•  » » » » » 4 years ago, # ^ |   0 oh my bad misread the question twice
 » 4 years ago, # |   0 It says pending systests, but systests have already started?
•  » » 4 years ago, # ^ |   0 Yep.
 » 4 years ago, # |   +205 As wise man said, please stop creating problems.
•  » » 4 years ago, # ^ |   0 This round was much easier than usual cf rounds, A, B, C, D were pure ad-hocs, and E too was easy. I didn't even read E because it was E :( .
•  » » » 4 years ago, # ^ |   +1 What did you gain from it not reading??
•  » » » » 4 years ago, # ^ |   -13 I prefered hacking other's solutions because I didn't thought E will be so easy, only to realise it later that it was simple ad-hoc,(binary search).
•  » » » 4 years ago, # ^ |   0 I directly jumped to E after solving C. This was good chance for me to solve 4 question first time if I wasn't that over-confident.
•  » » 4 years ago, # ^ |   +39 This time I can agree actuallyOr maybe just another notorious coincidence?problem F is from polish contest, author is polishhttps://szkopul.edu.pl/problemset/problem/4ftrK3Aqy2bpLk32N7wmjdZR/site/?key=statement
•  » » » 4 years ago, # ^ |   +69 My vote is on notorious coincidence (read: the author knew this problem). It's not the same problem though, N is higher and maxA is lower. Modifying a problem so it has a different solution is fine.
•  » » » 4 years ago, # ^ |   +37 Sorry, I didn't know this problem. I don't know all problems from POI.
•  » » 4 years ago, # ^ |   +41 +1
•  » » 4 years ago, # ^ | ← Rev. 2 →   +2 Thumbs up for the problem D.This is the first time it was interesting for me to read the story in a problem. I have never experienced that feeling while reading problem statement. The only artificial smell is that we're asked to find the number of different ways to eliminate ambiguities. At first I thought that the problem would ask us about deciphering who is trying to fool us (from the neighbours) and trying to lead the investigation astray :)
•  » » » 4 years ago, # ^ |   +2 Go to Timus for really cool stories. Or you also may be excited by a story in one of our contests: http://codeforces.com/gym/100812 (written by Shlakoblock)
•  » » » 4 years ago, # ^ |   0 Yeah but he must be a pretty bad detective to just ignore the evidence that doesn't work for him .-.
 » 4 years ago, # |   +27 I hope strong cases for F.Nice tasks :)
 » 4 years ago, # | ← Rev. 2 →   +11 Was the last problem created by the authors, by coordinators (KAN, cdkrot) or by 300iq? :)
•  » » 4 years ago, # ^ |   +40 By my friend isaf27 :)
 » 4 years ago, # |   +1 https://codeforces.com/contest/1043/submission/45019500 Any idea why this got a TLE? It's o(nmlogn) if I'm not mistaken. Could someone check it and let me know? Thanks!
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I think long long for every variable is causing TLE. Try to avoid putting long long everywhere.
•  » » 4 years ago, # ^ |   +1 Use vector instead of map. I also got TLE for that.
 » 4 years ago, # |   +18 How much cases do you have for model solution of G?
•  » » 4 years ago, # ^ |   0 Judging from the solution, it seems there are about 7 ~ 9 cases. Great!
•  » » » 4 years ago, # ^ |   +4 I found some recursion here :P
 » 4 years ago, # | ← Rev. 2 →   +35 That 700 lines for G from tourist...
•  » » 4 years ago, # ^ | ← Rev. 2 →   +11 tourist Got TLE :( for D
•  » » » 4 years ago, # ^ |   +16 His worst is even better than my best :D
•  » » » » 4 years ago, # ^ |   0 and his worst rate is still better than everyone!
 » 4 years ago, # |   0 why wrong answer in test case 2 is considered as a penalty in problem B. Link to the solution in which wrong answer in pretest 2 is considered penalty :Your text to link here...Please take a look into it
•  » » 4 years ago, # ^ |   +12 Because only a fail on test case 1 isn't considered a penalty, and 2 ≠ 1.
•  » » 4 years ago, # ^ |   +3 Wrong answer (or TLE, or MLE, or RTE, or...) on anything greater than test 1 counts as a penalty — even if that case is a provided sample. Only test 1 is excluded.
 » 4 years ago, # |   -8 Why this code for E gives runtime error? https://codeforces.com/contest/1043/submission/45014978
 » 4 years ago, # | ← Rev. 2 →   +33 When easy problems are attached with unnecessarily long question sentences, it is only an English reading comprehension contest for those who are not English speakers.
 » 4 years ago, # |   +8 Great contest , nice questions, nice tests, and I actually understood questions with reading only one time:)
 » 4 years ago, # |   -70 Contest featuring most advanced algorithms to date:(A) Binary Search (B) for loop (C) for loop (D) Binary Search (E) Binary Search"Balanced contest"I actually liked the adhoc nature of the contest though
•  » » 4 years ago, # ^ |   +79 It seems you use binary search where it is not necessary =) I have 0 BS's in solutions of this contest.
•  » » » 4 years ago, # ^ |   +41 Thank you for your insight. I have updated the topics.Updated list:(A) loop (B) loop (C) loop (D) loop (E) loop
•  » » » » 4 years ago, # ^ |   +24 According to your classification, 95% of the problems will have "for loops" topic :)
•  » » » » » 4 years ago, # ^ |   +10 Some REAL quotes:"95% of the problems ARE 'for loops' topic, it's just people came up with this pesky term 'algorithm' to describe basic operations" "I agree with Iightcode, he is genius"
•  » » » » 4 years ago, # ^ |   -32 It would be ok to see such comment from somebody, who solved all these problems in about a hour. From you it seems like one more comment of type .
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   -16 .What you think about anything I post is your own business. But why is it not ok to post what I want to say? I don't meet a rating threshold?And by the way, if you really are going to set such requirements for others at least meet them yourselves.
•  » » » » » » 4 years ago, # ^ |   -13 You can post anything that you want to say. As I also can. As we both do. And no, I try not to judge people by their rating, rather by their words (as in your case too).I set such requirements because you said (implicitly) that problems were easy and (explicitly) that contest was badly balanced. Maybe it was really easier than average CF round, but it should be said by somebody, who really feels that problems were easy (for 2 hours, of course). I didn't say it and you did. That's why you should meet such requirements and I shouldn't.
•  » » » » » » » 4 years ago, # ^ |   0 Sorry if I seemed like I was insulting the round. I actually like the round because it focused more on thinking than algorithm.I never meant to say round was easy, just that problems could be solved without advanced algorithms and more thinking.
 » 4 years ago, # |   0 man why was I soooo sloooooow solving C
 » 4 years ago, # |   +77 A notorious coincidence
•  » » 4 years ago, # ^ |   +25 Very mysterious...
•  » » 4 years ago, # ^ |   +154 Yes, they are the same person, have you ever spotted ksun48 and mnbvmar in the same location?
•  » » » 4 years ago, # ^ |   -17 I think I might've. But there was snoweverywhere so I could not tell for sure.
•  » » » 4 years ago, # ^ |   +49 My point wasn't that they are equal. The point is, that two nutellas got AC 2 ms under the TL.
•  » » » » 4 years ago, # ^ |   0 And CF top 1 didn't pass it at all.
•  » » » » » 4 years ago, # ^ |   0 that's the difference between C++11 anh C++14 :))
 » 4 years ago, # |   0 Can someone help what is wrong in this? http://codeforces.com/contest/1043/submission/44997704
•  » » 4 years ago, # ^ |   0 temp += max(0, i - a[i]); should be temp += max(0, i - a[j]);
•  » » » 4 years ago, # ^ |   0 I am so Noob :P Thanks for the help. Cannot find that simple mistake
•  » » » 4 years ago, # ^ |   +8 Tried running locally it was giving AC.
 » 4 years ago, # |   +12 how to get a random hoodie?
•  » » 4 years ago, # ^ |   +28 In the next contest become top-1 and make sure that nobody's gonna score more than you. Run the script locally with seeds (your score), (your score - 50), (your score - 100) etc until you find a seed where you win a random hoodie. Make a corresponding number of unsuccessful hacking attempts.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 problem B, round 412?
•  » » » 4 years ago, # ^ |   +10 How about giving up first place if second place person's score can get you hoodie?
•  » » » » 4 years ago, # ^ |   0 That person can betray you and make unsuccesful hack
 » 4 years ago, # |   +13 I misread problem C and did not know that there are just two letters. Does my code really solve it for general ? my code
•  » » 4 years ago, # ^ |   0 Uhh, same here, probably I will never realize it if I never see your post. Holy shit man, no wonder so many people already solved it the time I did. mine
 » 4 years ago, # |   +14 i think this contest rating changes can change top rated user in CF. i think mnbvmar will be top rated user after rating changes !!!!!
•  » » 4 years ago, # ^ |   +14 Revolution begins
•  » » » 4 years ago, # ^ |   +27 Last time it happened in the summer 2016 :D
•  » » » » 4 years ago, # ^ |   +18 It happened. Congrats to mnbvmar.
•  » » » » 4 years ago, # ^ |   +5 You are mistaken. Last time it happened in the spring of current year after CF #470 round.
•  » » » 4 years ago, # ^ |   +55 Or this was simply div2 contest + unsovlable task. Which for best guys in div1 means typing speed contest + every little mistake means -200 rating.
 » 4 years ago, # |   +55
•  » » 4 years ago, # ^ |   0 Will you explain,How u did it ? This is not the expected correct code.
•  » » 4 years ago, # ^ |   +2 Does it work on test 10 15 42 44 46 (all the even starting from 42)? The answer is 2 (15 and almost any other number (but not 10 and 42) so pairs of neighbours don't work.
•  » » » 4 years ago, # ^ |   0 Well, probability for that case is 1/n per random try (where n is less then 300000 becasue it's reduced and there's 50000 iterations so it's probably not hackable)
•  » » » 4 years ago, # ^ |   0 Just tried it and it prints 2. Thing is I also remove multiples of numbers that are among the given so this leaves me with only 13871 numbers.
•  » » 4 years ago, # ^ |   +17 So, 45023600 gives 4 while answer is 2 (gcd(15, 28) = 1)
 » 4 years ago, # | ← Rev. 2 →   0 Why is time limit for D so tight? Some NlogN solutions have passed and some didn't. I don't know if it wasn't the expected complexity. Update: My two solutions for D: TLE and Accepted. Both are O(NMlogN), just a one line difference (cin.tie(0);).
•  » » 4 years ago, # ^ | ← Rev. 3 →   +8 there's O(mn) solution (mine passed in 200ms)
•  » » » 4 years ago, # ^ |   0 Yes, I know. Maybe I ignored it thinking O(NMlogN) was enough to pass. These kind of testcases should be added in pretests because they are not even hackable.
 » 4 years ago, # |   +53 Who (outside of top 50) gets hoodies?
 » 4 years ago, # | ← Rev. 4 →   +34 My solution for F (45014411) failed in contest with tle 35:(. But it later passed all 4 times I submitted it in practice just after adding "srand(chrono::steady_clock::now().time_since_epoch().count());". 45021752. It is basically removing duplicates and then removing multiples of numbers and then kind of bruteforce with pruning. Can this solution be hacked and testcases are weak or can it be proved that it will work with high probability?
•  » » 4 years ago, # ^ |   0 It seems like you are not using Mersenne Twister in your first solution, relying only on default random function without setting seed (which makes it totally predictable). So, for any fixed n your shuffle is just a fixed permutation, which could be inverted. Then hacker could just take a test where bruteforce is working too slow and apply inverted permutation to it. In that case after random_shuffle you will get that bad test.
•  » » » 4 years ago, # ^ |   0 Thats ok. But even with true randomness should such solution work?
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +19 Well, seems like not.Suppose we have a number 299 999 and every number from 150 002 to 300 000 which is divisible by 2 — n = 75001. The answer is clearly 2 (gcd(299 999, 300 000) = 1), but you can get it only with 299 999. Note that no numbers would be deleted as duplicates or multiples.Let k be the position of 299 999 in shuffled array. You will need to do at least k*(k-1)/2 operations to get there (because your map stores every number you processed so far if ans >= 3, and until position k ans = 12), and if k is big enough, this number is too big.I runned your code on test above locally, and it took several minutes to finish (depending on position of 299 999 in shuffled array).
•  » » » » » 4 years ago, # ^ |   +14 Thank you! It makes me feel better that my solution didn't pass during the contest:D
•  » » » » » » 4 years ago, # ^ |   +8 There is another trick which allows you to reduce the number of candidates even more: You don't need to keep two numbers which have the same set of prime divisors. So if you have 2*2*3 and 2*3*3 keeping just one number is enough. This will reduce the number of candidates to 14548 in the provided test case.I used this during contest and my solution passed in 280ms. See 45018592 for details.
 » 4 years ago, # | ← Rev. 2 →   +3 I think I would have TLE on my own problem D solution with test:100000 101 2 ... 1000001 2 ... 100000...1 2 ... 100000100000 99999 ... 1
 » 4 years ago, # |   -14 This is not to blame the judges, but kind of disappointed that this submission 45015775 of mine for problem E failed the time limits. I did not think the I/O would be so slow for the problem. This would probably pass within 2.1s or less I guess. Please consider setting a little more kind time limit for problems where solutions with worse complexity has no chance of passing the test.
•  » » 4 years ago, # ^ |   +37 just add 2 lines in your template and forget about slow IO
•  » » 4 years ago, # ^ | ← Rev. 2 →   +21 No one to blame but yourself. You used fast IO in D because you were afraid of 10^6. You didn't use fast IO in E while it was almost the same input size, 12 * 10^5 but with larger numbers so input/output is even larger.
•  » » 4 years ago, # ^ |   -10 I also think problem E had too much I/O for the time limit. I usually like to use python to solve problems, and with some trickery it is mostly possible to solve any problem on cf with python (using pypy). However this problem had so much I/O that I was not able to do the I/O in under 2 s. Had to resort to C++ to get my solution to pass. I really think the constraints should be made such that not only C++ is able to pass. Currently this problem was mostly testing how quick I could get the I/O, which is not what makes these competitions fun.
•  » » » 4 years ago, # ^ |   -8 A sample solution I made in PyPy 2, 45036971, which might interest you.
 » 4 years ago, # |   -14 http://codeforces.com/contest/1043/submission/45014931why am I not getting AC when i clearly should??
 » 4 years ago, # |   0 Messi got injured in this round.
 » 4 years ago, # |   -18 I think problem setters need to re-consider limit for python. I have one implementation code of problem D, correct algorithm. However, I got different verdicts from different compilers: — http://codeforces.com/contest/1043/submission/45023038 — http://codeforces.com/contest/1043/submission/45021411
•  » » 4 years ago, # ^ |   +3 If you're using Python for anything past Div 2 B, you need to acknowledge the possibility that you can get TLE with the optimal solution. Python is too slow for most problems. Use C++ or Java.
 » 4 years ago, # |   +3 Sadly,this contest changed the world rankings !
 » 4 years ago, # |   -7 What's with test case 36 on D. I see tourist got TLE on it, and many of my friends also did. Why did this happen?
•  » » 4 years ago, # ^ |   -8 Because a lot of people solved it using directed graph. To construct it you need a map of pairs of integers, which is apparently slow. I managed to AC it, but with few pragmas (even then with 998ms) , my submission.
•  » » » 4 years ago, # ^ |   0 Consider using 100000 maps. I passed in 600ms.
•  » » » » 4 years ago, # ^ |   -8 just realised you dont need a graph at all...
•  » » » 4 years ago, # ^ |   -8 I just want to point put that you don't need maps to construct the graph. I'm actually surprised so many people went this path and submitted a sub-optimal solution (by a factor of logN). I guess it was more convenient and nobody thought it would TL.
•  » » 4 years ago, # ^ | ← Rev. 2 →   -18 45024667 vs 45024739,the only different is the space after * author: tourist and the c++ version
•  » » » 4 years ago, # ^ |   -8 Whitespace is ignored by compiler, so technically the only difference is c++ version, which is surprising that just because tourist used different C++ version he drops 100 places.
 » 4 years ago, # |   +16 I want to specially thank the problemsetter that came up with problem F. One of the most beautiful problems I've seen lately.
 » 4 years ago, # |   +13 tourist getting TL 45001078 on D during contest with C++11, but AC 45024674 post-contest with the same code submitted with C++14. feelsbadman
•  » » 4 years ago, # ^ |   +82 Still, inserting 1M elements into a map with TL=1s is never a good idea.
 » 4 years ago, # |   -34 Polish writers need to "polish" their problem setting skills!!
 » 4 years ago, # |   0 Good contest, it’s a pity that I didn’t have time to write (it coincided with conducting XXVI team championship of pupils of St. Petersburg in programming)
 » 4 years ago, # |   +68 when will random winners announce ??
 » 4 years ago, # |   +4 Those who got hoodies, share the picture of it. I really want to see how it looks.
 » 4 years ago, # |   -20 Are there any contests available this week?
 » 4 years ago, # |   -41 are there any contests available this week?NOIP is coming..
 » 4 years ago, # | ← Rev. 2 →   0 Where does randomness come into picture when solving F? I don't understand. I have seen plenty of people use random number generators when solving problems that involve calculating prime factorization but I never understood it. Can anyone please explain or point to some source. Thanks.
 » 4 years ago, # |   0 I am trying to solve E with the following solution (Python 3) — https://codeforces.com/contest/1043/submission/45127707. But, I am getting a TLE on test-5. Do I need to rewrite it in C++ or is there something that can be done in this solution? The solution is in O(N x logN)
 » 4 years ago, # |   +11 So who won the random hoodies?
 » 3 years ago, # |   +24 I understand you are not supposed to look a gift horse in the mouth. But does the hoodie really need a gigantic Che Guevara picture? What does it have to do with Botan Investments, Codeforces or programming in general?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I thought it is Grigory Perelman with π instead of a star on his cap
•  » » 3 years ago, # ^ |   +1 pic?
•  » » » 3 years ago, # ^ |   +22 pic
•  » » » » 3 years ago, # ^ |   +13 XDDDDDDDDThis is SO GOOD and SO BAD at the same time