By TLE, 10 months ago, ,

Hi!

I'm glad to invite you to participate in Avito Cool Challenge 2018 which starts on Dec/16/2018 17:35 (Moscow time). The round will be rated to participants of both divisons.

The problem setters are fjzzq2002, yjq_naive, fateice, yanQval and quailty.

We would like to thank:

This round is conducted on the initiative and support of Avito. Avito.ru is a Russian classified advertisements website with sections devoted to general good for sale, jobs, real estate, personals, cars for sale, and services. Avito.ru is the most popular classifieds site in Russia and is the third biggest classifieds site in the world after Craigslist and the Chinese website 58.com.

Avito presents nice gifts for participants. Top 30 participants and also 10 random participants with places 31-130 will be awarded with a special T-shirt.

You will be given 8 problems and 2.5 hours to solve them. As usual, the score distribution will be revealed shortly before the contest.

This is the first contest on Codeforces for most of us. Hope to see you participating! Good luck!

There will be an interactive problem in the round. If you have never solved interactive problems before, please read this.

UPD: The scoring distribution is standard 500-1000-1500-2000-2500-3000-3500-4000.

UPD: Congratulations to winners!

Also, you can find the list of T-shirt receivers here.

UPD: Editorial

Announcement of Avito Cool Challenge 2018
Announcement of Avito Cool Challenge 2018

• +557

 » 10 months ago, # |   +79 a round setted by 3 legends!it is gonna be a legendary contest
•  » » 10 months ago, # ^ | ← Rev. 2 →   -10 Many Chinese legends!
•  » » 10 months ago, # ^ |   +36 Is it the first round set by so many high schoolers? Excited for this round :) tons to learn
•  » » 10 months ago, # ^ |   0 "setted" is not a word.
 » 10 months ago, # |   0 Can't wait for this cool contest :D
 » 10 months ago, # |   +19 Reminds me of "Aviato" from Silicon Valley Series XD
 » 10 months ago, # |   +51 Chinese Round!
•  » » 10 months ago, # ^ |   +60 Chinese legends' round, but Chinese night owls' round as well.
•  » » » 10 months ago, # ^ |   0 I can't help sleeping at about 00:40 …
•  » » 10 months ago, # ^ |   +47 I smell geometry and a lot of meth!
•  » » » 10 months ago, # ^ |   -25 :( why?
 » 10 months ago, # |   -50 choutii for playing a crucial role in the contest. (you'll see.)Both of you choutii and fjzzq2002 studying in Fuzhou No.3 High School. And I am not blind
•  » » 10 months ago, # ^ |   +2 I think he will appear in problems just like Alice and Bob. :-)
•  » » » 10 months ago, # ^ |   +31 guess again
•  » » » » 10 months ago, # ^ |   0 Well, That was true :P
•  » » » » » 10 months ago, # ^ |   +10 Not,I got no Alice
 » 10 months ago, # |   0 I need a lot of math in this contest.
 » 10 months ago, # |   +99 There will be an i̶n̶t̶e̶r̶a̶c̶t̶i̶v̶e̶ binary search problem in the round.
•  » » 10 months ago, # ^ |   -28 Not all of them: 1088D - Ехаб и еще одна очередная задача на xor
•  » » » 10 months ago, # ^ |   +74 actually it is binsearch, every two iterations we discard a half of candidates for both numbers
•  » » 10 months ago, # ^ |   +7 Not all of them (2): 1075D — Intersecting Subtrees
 » 10 months ago, # |   +70 Traditionally, we publish algorithm of selecting random winners before the round. 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 = [1081] def is_eligible(contest, party_name, rank, points, problems, last_submission_time): return (31 <= rank <= 130) 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)) The seed will be the total number of points of three best participants of this contest, length is 100 (130 — 30) and nwinners is 10.
 » 10 months ago, # |   +77 tourist I think this contest will be the best revenge Radewoosh
 » 10 months ago, # |   +30 rua！
 » 10 months ago, # |   -8 I am looking forward to participating this legendary contest created by fjzzq2002!Three Legends! %%%Fjzzq2002!!
 » 10 months ago, # |   +14 I like Chinese rounds.
 » 10 months ago, # |   +68 Chinese Round but a little bad time for Chinese high school students...
•  » » 10 months ago, # ^ |   +78 Sorry about that, but an opencup will end half an hour before the contest, so we can do nothing :(
 » 10 months ago, # |   +32 when reading the Avito
 » 10 months ago, # |   +207 Will problem setters get T-shirts too? :D
 » 10 months ago, # |   -10 previous Avito code challenge is a good one for me(+100) hope this contest will also give a lot of increase in rating and for other also.
 » 10 months ago, # |   -49 Will we get rating from this contest?
•  » » 10 months ago, # ^ |   +8 Read careful the round announcement, the second sentence specifies that it is rated for both divisions.
•  » » » 10 months ago, # ^ |   -8 thanks you very much
 » 10 months ago, # |   -34 IS it ICPC rules ? and are the 8 questions too much?
 » 10 months ago, # |   -15 I am wondering watching gritukan profile . Won't you ?
 » 10 months ago, # |   0 Good Luck! :D
»
10 months ago, # |
-63

# Is It Semi-Rated?

 » 10 months ago, # |   -60 That silly registration process is annoying, fuck hacking, fuck rooms
 » 10 months ago, # |   +1 zzq and fateice!the proud of fzsz!
•  » » 10 months ago, # ^ |   0 %%%
 » 10 months ago, # |   0 In CP, You get T-shirts in winter XD
•  » » 10 months ago, # ^ |   +39 You can go to Australia to make the T-shirt useful.
•  » » » 10 months ago, # ^ |   -10 tourist is now buying a ticket
 » 10 months ago, # |   +1 How to solve D?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +13 Think in terms of mst. Consider all the edges which directly or indirectly connects any 2 special nodes. Among all such edges find the one with maximum wight. This passed system test for me.
•  » » » 10 months ago, # ^ |   +1 I did but what to do after that? How to find maximum distance for each special node after constructing the tree?
•  » » » » 10 months ago, # ^ |   -12 I have updated my comment. Try proving the solution yourself. It is interesting.
•  » » 10 months ago, # ^ |   0 Find the MST, and then choose the relevant subtree that contains all the special nodes. The answer is going to be the maximum edge weight in this subtree repeated k times. The MST has the property that it minimizes the maximum edge between in a path between nodes a to b.
•  » » » 10 months ago, # ^ |   0 I think it will not be maximum edge weight for ex: 4 3 2 3 4 1 2 10 2 3 1 2 4 1 Here the answer will be : 1 1 Correct me if am wrong.
•  » » » » 10 months ago, # ^ |   0 We have to choose a SUBTREE of the MST that contains all the special nodes.The 1-----2 edge will not be part of this MST subtree
•  » » » » » 10 months ago, # ^ |   0 Yes you are right, I did not read your comment properly, my bad.
•  » » 10 months ago, # ^ |   +11 I did using a binary search to find the maximun edge that is necessary to contains all special nodes. The answer will be this maximun edge for all nodes.
 » 10 months ago, # |   +25 I wasted too much time on A-E and couldn't find time to code problem H :(My approach would be something like this:We may calculate number of distinct palindromes and . First estimate would be , but there will be some pairs which we counted twice. What are those strings which may be obtained in several ways? They always may be viewed as where , , and are palindromes. This immediately implies that is the period of both and and this is one-to-one correspondence. Good news is that we may find all possible minimum periods of all palindromes in both strings and . Now we should calculate number of strings which may be glued with where is one of minimum periods we found, seems like an easy task to do with eertree and some hashes, given that you have enough time to code it.
•  » » 10 months ago, # ^ |   -49
•  » » 10 months ago, # ^ | ← Rev. 2 →   -11 I tried something similar.I made the pallindromic tree for both strings, now, to find the number of such y's, I calculated, for each reversed suffix links in A, the number of suffix links in B, so I made hashes of all these suffix links and inserted them in a multiset. But I had a bug in the code. Also, I cannot prove the suffix link idea is correct, so most probably it's wrong since it has 0 solves :p.
 » 10 months ago, # |   +62 G is awesome. Could anyone share his/her solution?As for the others. I found the contest quite nice overall. I failed on D and saw that only after locking. I'd say the biggest issue that I could see with the contest was the very weak pretests in D. Basically you'd pass them if you compute the maximum distance between any 2 points, not necessarily special. Then, regarding the same issue, this left plenty of space for hacks. And apparently rooms are very badly calibrated. In my entire room, there were only 5 (4 until 10 mins ago) people that even tried D (me included). So not only have I locked D and couldn't get a later AC, but my gain from hacks was only 100 points, whereas others had 4-5 hacks on D. I was close to having a good performance, but trying not to be biased, I think I'm not lying when saying that nobody likes having weak pretests. Basically you might misunderstand the problem, solve a wholly different problem and still pass the pretests.
•  » » 10 months ago, # ^ |   +8 Basically you'd pass them if you compute the maximum distance between any 2 points, not necessarily special Really? Why would you even do that? I saw people getting hacks on D but nothing happened in my room...
•  » » » 10 months ago, # ^ |   +53 That's what I submitted too...It's the answer if you read it as "for each special vertex, find the farthest (not necessarily special) vertex from it".
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   +26 High five!
•  » » 10 months ago, # ^ |   -38 If there is a person to blame, i think it should be you. You should blame yourself for not reading statement carefully. Many people solved it, so you shouldn't blame the pretest.
•  » » » 10 months ago, # ^ |   +68 Was I blaming anyone? I just said that it's shitty when this happens and nobody particularly enjoys it. I thought the purpose of the pretests is to help you get rid of silly/obviously unintended mistakes. If this is not true, then why do we have pretests at all? When there are some poor pretests, there are 2 categories of people: those that fail, definitely didn't enjoy failing on some easy problem because of a corner case, and those that don't, that still shit their pants when seeing so many hacks and WAs and double-triple check their sources, wasting time, instead of focusing on the beauty of the contest: thinking about the other problems. So I was just claiming that it's not a nice thing to do, and that nobody actually enjoys the fact that the pretests are weak (to be noted, that in this problem, the most random tests would've shown the bug, so the pretests were especially designed to hide this sort of wrong interpretation)
•  » » » » 10 months ago, # ^ |   -72 I don't care about the pretest. You just use the reason to satisfy yourself that you may still better than someone who solved the problem you failed, when the fact that you ruined your work yourself, while they were not. If i were you, i would accept the fact that i read the wrong statement and try hard next time, instead of leaving a complain.
•  » » » » » 10 months ago, # ^ | ← Rev. 2 →   +11 Hmm so now I wasn't blaming anyone anymore, was I? Now I was complaining. Next, I'll be whining and so on. My point was: good contest, liked the problems, would've liked the overall experience more if the pretests were better and I'm sure I'm not the only one. This is not complaining, but stating a fact to remind the setters that nobody enjoys it.If you're so much willing to support an opposite point of view, then better try to add some arguments. If you don't care about pretests, then obviously something's wrong with you. I wonder why IOI and ICPC are full feedback. Ahh maybe, because they want to emphasize the idea, and not the code? Neah, can't be that
•  » » » » » » 10 months ago, # ^ |   -14 Okay, i think that blaming is similar to complaining. Anyway, i'd like to think that when we fail and other people aren't, then the failure should because of our mistakes. Pointing out the weak pretests is necessary for Codeforces community, as it helps improving the contest quality. i just don't like when you said that the weak pretests affected your perfomance. This is the fact, but there is also another fact that you ruined it before the pretests by reading wrong statement. What you said is like prefer the first fact than the second one, which is what i wouldn't like. So i tried to tell you this, but it became a bad argument.
•  » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 Dude you blamed all your FIFA opponents for rekting you and you are here being hypocritical about what lmao???
•  » » 10 months ago, # ^ | ← Rev. 3 →   +11 Not only pretests were weak, but system tests too, which makes it more fair.Here is O(m*k) accepted solution, which I did not manage to hack within contest.
•  » » » 10 months ago, # ^ |   0 Isn't that solution O(M * logM)? It looks like he baited you with bad indentation.
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   -18 I guess that because of your comment I got downvotes, for bullshit and blaming strong tests :) Well this is O(m*k) as I wrote and here is the test exposing this:  printf("100000 100000 50000\n"); REP(i, 49999) printf("%d ", i + 1); printf("50000\n"); printf("1 2 1\n"); REP(i, 49997) printf("%d %d 1\n", i + 2, i + 3); FOR(i, 49999, 99999) printf("%d %d 1\n", i + 1, i + 2); printf("1 50000 2\n"); printf("1 50000 2\n"); 
•  » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 You're calling bs but I copied the test and the solution and it runs in under 2 seconds in my (slow) computer... ? Did you care to try the test?Edit: In fact, I ran that test on custom invocation with the input hardcoded and it got 30ms
•  » » » » » » 10 months ago, # ^ | ← Rev. 5 →   +18 You must have a very fast computer or use a different test. Here is the result on a fast computer:It took me 3398 clicks (3.398000 seconds).Edit. I also run it on cf and it runs in 15 ms. I don't understand that. I even added counter inside inner for loop for (j = 2; j <= k; j++) The value of that counter is 2,5*1e9, which proves that it runs in O(m*k). I don't understand how is it possible on cf to run so fast...Edit. I even multipled constraints by 10 and on my machine it runs as expected — extremely long. On CF it runs in 93 ms and outputs very small number of total iterations. I completely do not understand this weird custom invocation behavior:Expected number of iterations during local testing: 249999999999CF custom invocation: 1666656
•  » » » » » » 10 months ago, # ^ | ← Rev. 3 →   +26 I found the issue. Please replace sort with stable_sort to get huge TLE or use different weights on edges. In case the values are the same the order can be arbitrary and it happened that first edge with 50000 appeared in the end instead of being in the middle.Edit. I think that KNB. might be interested, as he also noticed that and tried to hack that solution.
•  » » » » » » » 10 months ago, # ^ |   +13 I see, that's true. Nice catch.
•  » » » 10 months ago, # ^ |   +16 Tests on E were also weak. Solutions which can set x_i = 0 like: 47142808 or 47119126 by mnbvmar were accepted. This fails for example on: 4 600 600 
•  » » » » 10 months ago, # ^ |   +35 Added test for the upsolving
•  » » » » » 10 months ago, # ^ |   0 Have you added perf test to D too?
•  » » » » » » 10 months ago, # ^ |   0 There was some discussion going about it, give me the last version and I will surely do :)
 » 10 months ago, # | ← Rev. 2 →   +34 That was really interesting and close.if V--o_o--V got just one successful hacking attempt, he would have become the first.Edit: nvm :(
 » 10 months ago, # |   0 How to solve E?
•  » » 10 months ago, # ^ | ← Rev. 4 →   0 for each number you have the sqrt of the sum of numbers before it bf, and number next to it nxt. now you need to find an x such that ll(sqrt(a * a + nxt)) == sqrt(a * a + nxt) and a = bf + x . I don't think binary search would work, so I iterated while ((a + 1) * (a + 1) - a * a <= nxt) which means that the difference between the next perfect square is already bigger than nxt and we have no answer if that happened, and nxt <= 1e5 so that will fit in the time limit. Tho I don't have any proof whether the first number that fits will be the only one that does.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +40 We can prove that we want to always greedily take lowest possible square for any prefix. Lets consider 4 numbers, first and third of them we can choose. Consider the case when multiple prefix sums can fit the prefixes of sizes 1-2, but only one value fits prefixes of size 3-4. In this case we can take any of lower values for 1-2 and adjust 3-4 up to needed numbers by adjusting value of number 3.Formally: a1 = A a1 + a2 = B a1 + a2 + a3 = C a1 + a2 + a3 + a4 = D And we have two different values for A and B: (A1, B1) and (A2, B2). So we can satisfy them with proper values a1 and a2. And then choose a3 = C - a1 - a2.The only limitation is that a3 > 0. So choosing minimum B is not only valid, but also optimal.Consider this geometrical interpretation. From up-left to right-bottom: green area is a1, yellow is a2, blue is a3 and pink is a4. On both pictures areas of yellow and pink are the same (up to my drawing skills quality), but we can freely choose green and blue areas to preserve total area of C and D unchanged. And this idea can be easily generalized for higher number of prefixes.
•  » » » 10 months ago, # ^ |   0 wewark I think you meant a*a = bf + x and not a = bf + x .
•  » » » » 10 months ago, # ^ |   +3 sorry, bf is the sqrt of the sum of the numbers before, not the number itself. Fixed.
•  » » 10 months ago, # ^ |   0 I did it with a greedy algorithm. For every odd i find such an a[i], so sum (a[1..i-1]) + a[i] + a[i+1] is a correct square, using the fact, that we can make any correct square from sum (a[1..i]), that is less than sum (a[1..i-1]). So every time i seek for the minimal square. We can stop seeking, when a[i+1] is less than 2 * sqrt (sum (a[1..i])) + 1.
•  » » 10 months ago, # ^ |   0 I did it with a greedy algorithm. For every odd i find such an a[i], so sum (a[1..i-1]) + a[i] + a[i+1] is a correct square, using the fact, that we can make any correct square from sum (a[1..i]), that is less than sum (a[1..i-1]). So every time I seek for the minimal one. We can stop seeking, when a[i+1] is less than 2 * sqrt (sum (a[1..i])) + 1.
 » 10 months ago, # | ← Rev. 2 →   +8 Can we do F deterministically? If yes then what is the approach?
•  » » 10 months ago, # ^ |   0 In general, we can't. For example, see array with size 2. 01 and 10 are indistinguishable.
 » 10 months ago, # |   0 Is pC C(m,n/(n-k))
•  » » 10 months ago, # ^ | ← Rev. 2 →   +49 It is
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +3 I managed to find the formula during contest and submitted exactly the same. But it gave WA on pretest 5. I guess I messed up ordering of modular arithmetic. :(
•  » » » 10 months ago, # ^ |   +3 Can you please explain?
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   +16 So there are k + 1 blocks. Choosing the sizes of the blocks and the colours are independent of each other, and the answer is the product of the two. colour arrangements: For the first block, we have m options, but for the other k blocks, it must have a different colour than the previous one, so there are m - 1 options for those. This gives m(m - 1)k. Block sizes: Every block must be of size  ≥ 1, so let s1, ..., sk denote the starting positions of the second, third, etc. block. Then we have 1 < s1 < ... < sk ≤ n, so . Thus we are picking k 'balls' out of n - 1 'items'. This is .
•  » » » 10 months ago, # ^ | ← Rev. 3 →   +1 Is it the correct one ? I submitted the same but got WA on pretest 4 !! and then applied DP seeing the constraints :( Edit — I made a modular arithmetic mistake :3
•  » » » 10 months ago, # ^ |   0 Completely misunderstood the problem. I thought there are k different bricks in total with color different from each brick except the last one.
 » 10 months ago, # |   0 What are the hacks in D? I see a lot of hacks.
•  » » 10 months ago, # ^ |   +25 Basically, anything
 » 10 months ago, # |   -13 i couldnt solve b. Can anyone please telll the solution?
•  » » 10 months ago, # ^ |   0 please?
•  » » » 10 months ago, # ^ |   0 Here is my solution, but I feel like there's a simpler one out there. I recommend waiting for the editorial.
•  » » » » 10 months ago, # ^ |   0 cant see your solution . can you explain your approach?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +1 I'll tell you how I approached it. First, Observe that all people who are wearing the same type of hat will have the same value of a[i] i.e. people differing will be the same. Although vice versa is not true.Maintain a hat ID variable starting from 1.FOR ith person who is not assigned any hat number:count the number of people having the same values in a as a[i]. let's call them SAME and count the people having different values in a, other than a[i].let's call them DIFF.if DIFF is greater than a[i] that means sequence b is not possible. if DIFF is equal to a[i] then all the people counted in SAME will get the same hat number. Assign the same hat ID to all people counted in SAME. if DIFF is less than a[i] then (a[i]-DIFF) people counted in SAME will not get the same hat number. Hence assign same hat ID to ( SAME-(a[i]-DIFF) ) people counted in SAME. Don't assign any Hat ID to the rest. increment hat ID variable. END FOR loop.Here's my code.
•  » » 10 months ago, # ^ |   +1 For each people we can say the number of hats of his kind — it's n - a[i]. Then we can count the number of people, the number of hat's of whose if n - a[i]. X people for Z hats. If for each number from 1 to n X % Z == 0 — we can answer. Otherwise, it's impossible. We can choose the types from 1 to n in this order: int ttype = 0; for (int i = 0; i < n; i++) { cin >> a[i]; if (numb[n - a[i]] % (n - a[i]) == 0) { ttype++; type[i] = ttype; numbtype[n - a[i]] = ttype; } else type[i] = numbtype[n - a[i]]; numb[n - a[i]]++; } 
 » 10 months ago, # | ← Rev. 2 →   +182 Please stop using l (lowercase L) as a variable name in problem statements.On problem 1081F - Коварный интерактор, I thought "the interactor will either flip [1, r] or [l, n]" was "[l, r] or [l, n]" and spent over half an hour solving the wrong problem.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +27 I think l is similar to 1, but l is not similar to 1.
•  » » » 10 months ago, # ^ |   +3 Looking similar doesn't justify the use of wrong characters. Don't you think?
 » 10 months ago, # |   +10 holy terrible implementation on F
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 +1, I spent like 40 minutes trying to figure out when to invert the value of s[i]...PS: I still think the problem was awesome
 » 10 months ago, # |   0 what was test 15 in E?
 » 10 months ago, # | ← Rev. 2 →   +3 It was great being purple for a day. :(Will probably fall about 30 rating points. EDIT: WTF Got hacked and failed two problems. RIP pretests.
 » 10 months ago, # |   0 really nice problems !! it was fun to think about :D even so C made me confused with probabilities and couldn't solve it See problem setters we don't get mad because we didn't make good result it's because the problems aren't fun to think about
 » 10 months ago, # |   0 My solution of C failed on pretest 4. But i didn't find the right case. Can somebody, who failed at pretest 4 first, please, explain, where is mistake?
•  » » 10 months ago, # ^ |   -7 I had ifs: if (k==0)return cout<m)return cout<<0,0;I removed them and got ac, formula is: d[i][j]=d[i-1][j-1]*(m-1)+d[i-1][j];Before processing this formula i put every d[i][0] to m (1<=i<=n)
•  » » » 10 months ago, # ^ |   0 Thank you! I did't think about dp. But I haven't got the problems with this cases...
 » 10 months ago, # |   0 Tourist is going to take back the first spot!
 » 10 months ago, # |   0 How to solve B?
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 I'll tell you how I approached it. First, Observe that all people who are wearing the same type of hat will have the same value of a[i] i.e. people differing will be the same. Although vice versa is not true.Maintain a hat ID variable starting from 1.FOR ith person who is not assigned any hat number:count the number of people having the same values in a as a[i]. let's call them SAME and count the people having different values in a, other than a[i].let's call them DIFF.if DIFF is greater than a[i] that means sequence b is not possible.if DIFF is equal to a[i] then all the people counted in SAME will get the same hat number. Assign the same hat ID to all people counted in SAME.if DIFF is less than a[i] then (a[i]-DIFF) people counted in SAME will not get the same hat number. Hence assign same hat ID to ( SAME-(a[i]-DIFF) ) people counted in SAME. Don't assign any Hat ID to the rest.increment hat ID variable.END FOR loop.Here's my code.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Here a[i] is the number of persons who wear different hat from him. Hence, n-a[i] is the number of persons who wear similar hat to him.Now, group the indices whose n-a[i] is equal. Insert i in the group[n-a[i]]. If for any group[i], size of the group is not divisible by i, then print Impossible Otherwise, maintain a id starting from 1. For each group[i], iterate through all the indices in it and for every i indices, set their value of b[] to the counter value and increment the counter by 1. Then print Possible and the array b[]. Update: Here is my code: https://pastebin.com/QWf0gbsB Sorry for my poor English. Feel free to comment, if you don't understand the solution.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 one this i don't understand. please explain...Depending on what condition , counter value will be increment by 1. And one more this,Why divisible is require for Possible or Impossible. please explain conceptually.
 » 10 months ago, # |   0 why are other's submission still not public ? :(
•  » » 10 months ago, # ^ |   0 Probably to do the system testing fast.
 » 10 months ago, # |   0 If we say in C that k is not just for left bricks, but to all bricks (every brick can be painted with m colors, but all bricks in the end need to have k different colors), what is formula for dp[n][k] then?
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 DP[0][0] = 1;DP[i][j] = m*DP[0][j] + Sigma(x from 0 -> i-1) (m-1) *DP[x][j-1] (if j > 0)
 » 10 months ago, # |   +23 Best chineese contest i've ever seen
•  » » 10 months ago, # ^ | ← Rev. 2 →   +1 As a general rule, no one solved H. But I still think the problems are perfect.
 » 10 months ago, # |   +55 How can pretests be so weak that for problem D a solution which outputs the biggest distance between the furthest vertex, not the furthest special vertex pass pretests?
•  » » 10 months ago, # ^ | ← Rev. 6 →   -19 I was hacked by khokho with this same idea. Luckily for me, he gave me the opportunity to correct my code. EDIT: my corrected code didn't pass system tests. Damn it, I spent twice the time for less than worse results.EDIT: Why the downvotes?
 » 10 months ago, # |   +3 nice 9th test on B just kills me.
•  » » 10 months ago, # ^ |   0 i think it's will be something like 2 1 1 or 4 2 2 2 2 or 7 5 5 5 5 5 5 6
 » 10 months ago, # |   +46 How come tourist was able to hack on A...Btw, I see only one FST among all 63 submissions in our room. What a smart room!
•  » » 10 months ago, # ^ |   0 You should try to be bad-at-luck like me, constantly jumping into rooms that nobody makes mistakes even other rooms are full of such people :DAlso, nicely done hacking one D :D
•  » » 10 months ago, # ^ |   +9 What is FST?
•  » » » 10 months ago, # ^ |   +13 Failed System Test
•  » » 10 months ago, # ^ |   0 aactually I have seen the code of problem A which tourist hacked . that fellow's code gives output 2 for input 6. here's the code https://codeforces.com/contest/1081/submission/47132351 and hacking that code is too easy for someone like Tourist!
 » 10 months ago, # |   +22 Why I'm unable to see other's solutions?
 » 10 months ago, # |   +43 Why can't I submit problems though systest is over? Submit button still redirects to same page with notification 'contest is over' .
 » 10 months ago, # |   +11 How can I upsolve the problems of this contest?
•  » » 10 months ago, # ^ |   +3 The problems should be able to submit by now. However, they're not at the top of the problemset, so be careful to find them.
 » 10 months ago, # |   +20 Why am I not able to submit solutions even though the systests are over?
•  » » 10 months ago, # ^ |   0 coz they havent put the problems for practice!!
•  » » » 10 months ago, # ^ |   +1 I hope they add it soon. My frustration level is rising exponentially.
 » 10 months ago, # | ← Rev. 2 →   +61
 » 10 months ago, # |   0 why I faced problem while submitting ans of problem after contest ?
 » 10 months ago, # |   0 Anyone got an idea what was pretests 6 in E? Can't wait anymore
 » 10 months ago, # |   0 back to div2 it is
 » 10 months ago, # |   +10 When the Editorial will be published ?
 » 10 months ago, # |   0 In problem C, can anyone explain meaning of this line "he found there are k bricks with a color different from the color of the brick on its left (the first brick is not counted, for sure)".
•  » » 10 months ago, # ^ |   +13 If color[i] is the color of the i-th brick, then it's talking about the number of bricks such thatcolor[i] != color[i-1].I agree that it could have been worded better.
 » 10 months ago, # | ← Rev. 5 →   +5 https://codeforces.com/contest/1081/submission/47141835My submission is O(n) but you can easily achive O(1) with factorial preprocessing for calculating nCr.O(1) sol for C. 1). How many ways to divide n into k+1 segements. (x)2). How mnay ways we can color k+1 segements such that no adjacent color is same. (y)ans = x*y
•  » » 10 months ago, # ^ |   +8 But thats O(n) solution.
•  » » » 10 months ago, # ^ |   -8 Mine is O(n) but with factorial preprocessing you can do nCr part in O(1).
 » 10 months ago, # |   0 many have crached task D on test 18, does anyone understand why?
•  » » 10 months ago, # ^ |   +7 Taken such test for example: 3 2 2 1 2 1 2 3 2 3 4 The answer should be 3, but since many solutions output the maximum weight of the MST of the entire graph (not just the subgraph including all special vertices), they outputted 4 and failed system tests.
 » 10 months ago, # |   -10 I just want a T-shirt~QAQ
 » 10 months ago, # |   -6 Problem D is so close to this one: The Child and Zoo
 » 10 months ago, # |   0 int s1=(b-a)/2;For E, why do we need to divide the difference by2. Can someone provide a intuitive explanation for E? Thank u v m!
 » 10 months ago, # |   +5 Guys ! for problem D you also can use simple Dijkstra algorithm starting from any special vertex. The answer is the maximum of cost of all special vertex. check my solution. Using wrong comparator function was the reason i had to try submitting so often.