### antontrygubO_o's blog

By antontrygubO_o, 5 months ago, ,

Hello Codeforces!

We are glad to invite you to the upcoming “Ozon Tech Challenge 2020”, which will start at Mar/03/2020 17:35 (Moscow time). The round will be open and rated for everybody!

This round is initiated and supported by Ozon.

Ozon — one of the leading players in e-commerce (provides its customers with over 2.5 million product names in 24 categories), a tech company that actively developing its IT department. They already have the largest Golang team in Russia, a proprietary WMS fulfillment management system completely written by the Ozon team, 250 million lines of logs per day, collected on the site and in the Ozon mobile application. Ozon experts perform at the leading profile conferences GoperCon, Heisenbug, GoWayFest, GolangConf, and also at the company site meetups are held for the IT community.

The company shows great interest in the support of the developer community — for schoolchildren there is Ozon Academy, for the older audience there is an internship program Ozon Tech Camp and training program Ozon Masters.

Participants will be asked to solve 8 problems in 2 hours 15 minutes. Scoring will be announced a bit later.

The problems were created by Akikaze, Ari, Kuroni, zscoder, xuanquang1999, and antontrygubO_o

We would like to thank:

Thanks to Ozon for the gifts to the participants:

• top 10 participants will receive stylish branded backpacks and branded T-shirts;
• 11-20th participants will receive compact portable chargers for 10000 mAh and branded T-shirts;
• 21-60th participants will get branded t-shirts;
• another 30 T-shirts will be played among the rest of the participants, who solved at least two problems, randomly.

We hope everyone will find an interesting problem for themselves. Wish everyone a successful round and high ratings! Good luck!

UPD1:

Score distribution:

500 — 1000 — 1250 — 1750 — 2000 — 2500 — 3250 — 4000

UPD2: Editorial

UPD3: Congratulation to the winners!

Information about prizes will appear soon.

• +754

 » 5 months ago, # |   +247 Is anybody going to talk about the "no subtasks" tag? :))
•  » » 5 months ago, # ^ |   -27 Is it rated?
•  » » » 5 months ago, # ^ |   +13 rated
 » 5 months ago, # |   +109 AC round #2
 » 5 months ago, # |   -54
•  » » 5 months ago, # ^ |   +3 Wise decision to be honest. ;)
•  » » 5 months ago, # ^ | ← Rev. 2 →   +37
 » 5 months ago, # |   +11 Finally prizes
 » 5 months ago, # |   -31 Small prizes though
•  » » 5 months ago, # ^ |   -10 Any prize is great!
 » 5 months ago, # |   +34 No subtasks
 » 5 months ago, # |   +243 ![ ]()
•  » » 5 months ago, # ^ |   0 It's soooo real!lol(#ﾟДﾟ)
 » 5 months ago, # |   +82
•  » » 5 months ago, # ^ |   -20 Hah,that's a serious problem. However,no matter whether you will get the T-shirts finally,wish you enjoy the competition!
•  » » 5 months ago, # ^ |   +169
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +43 On my way home I saw this meme and planned to change the text on the pink monster to "using question instead of problem", but thanks, that even better! :D
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -21 Nothing Here
•  » » » 5 months ago, # ^ |   0 i just realized your name means toucan, the bird in rainforests. or maybe i just had too much moonshine
 » 5 months ago, # |   -30 In my opinion, a person who has a better rating should have a better chance of winning a prize! (For 30 T-shirts) This is fairer!
 » 5 months ago, # |   -9 Will all sponsored rounds be combined? :(
•  » » 5 months ago, # ^ |   +109 How to make round with prizes not combined?
•  » » » 5 months ago, # ^ |   -106 Prizes only for div1, or for top30 of div1 and top2 of div2.And I didn't know what there will be prizes in all sponsored rounds.
•  » » » » 5 months ago, # ^ |   +169 Only for Div1 sounds unfair and the round becomes just the usual round for majority of participants.If you make prizes for Div2, Div1 people are likely to create fake accounts.Sponsored rounds usually have prizes or are elections to some onsite competition, in which case it's also reasonable to make round combined.
•  » » » » » 5 months ago, # ^ |   -70 Only for Div1 sounds unfair Why? Making qualification rounds before most important (third) online round of Google Code Jam is also unfair? the round becomes just the usual round for majority of participants that's a plus :) If you make prizes for Div2, Div1 people are likely to create fake accounts. top2 div2 isn't much easier than top30 div1
•  » » » » » » 5 months ago, # ^ |   +157 I don't know of this happens in reality, but when round is combined it makes sense for organising company to promote the competition on their own channels. If div2 is without prices it makes much less sense for them because newly registered users can't actually win
•  » » » » » » » 5 months ago, # ^ |   +76 Ok, this is a very good point.
 » 5 months ago, # |   +28 Official drink of the contest
 » 5 months ago, # |   +10 Solve two problems! That's so great for me, maybe I will get my first T-shirt in these rounds.
•  » » 5 months ago, # ^ |   +15 With <1% probability? You are the big optimist.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +22 Worst case: about 30/10000=0.3%. Best case: about 30/2000=1.5%But 0.3%>0% !
•  » » » » 5 months ago, # ^ |   +7 You should keep trying with 2+ solves as in future you will be able to solve more
•  » » » » 5 months ago, # ^ |   0 nah it is bigger than 0.3%. All of the competitors will not solve 2 problems.
•  » » » » 5 months ago, # ^ |   -11 Previous combined round have ~7000 participants and only ~4500 of them solved at least 2 problems, so your estimation of 10000 is very inaccurate. Anyway 0.3% < 1% so I don't understand the reason of this calculations.
•  » » » » » 5 months ago, # ^ |   0 That is the worst case :(Of course impossible XD
•  » » 5 months ago, # ^ |   0 Wish you good luck!Hah( ´▽ )ﾉ
•  » » 5 months ago, # ^ |   -14 No,you wont get a tishort becouse u would not solve 2 problems. Uoy won't solve anything.
 » 5 months ago, # | ← Rev. 2 →   -46 .
•  » » 5 months ago, # ^ |   +9 Good question. If only the name of the contest gives us that answer.
 » 5 months ago, # | ← Rev. 2 →   +3 Are there any previous Ozon Tech Challenge contests held on Codeforces?
•  » » 5 months ago, # ^ |   +15 No, it is the first one.
•  » » » 5 months ago, # ^ |   0 Believe it or not, I'll get the shirt
•  » » » » 5 months ago, # ^ |   0 1%
•  » » » » » 5 months ago, # ^ |   +5 1% is still too good, lets say there are 6000 participants that solve 2 problems. 30 out of 6000 XD, 0.005 chance.
•  » » » » » » 5 months ago, # ^ |   0 multiply 0.005 with 100 ,to get percentage.... i.e. 0.5 % still close :->
•  » » » » » » » 5 months ago, # ^ |   -11 multiply it with 200, to get percentage.....i.e. 100% we all win.
 » 5 months ago, # |   0 That feeling when you really need a new backpack knowing that you have no chance to win...
 » 5 months ago, # |   +3 what's the score distribution?
•  » » 5 months ago, # ^ |   +11 It is going to be announced closer to the beginning of the round.
 » 5 months ago, # |   +16 Can I participate in this contest? I don't know the full process. Anybody help me plzz.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +46 spoiler0) write "is it rated?" in the comments1) register for the contest in contests page 2) when contest starts, solve problems and submit them 3) after the contest your rating will be updated according to your performance
•  » » » 5 months ago, # ^ |   +3 Thank you so much ♥
•  » » 5 months ago, # ^ |   +1 Yes you can.
•  » » » 5 months ago, # ^ |   0 Thanks
•  » » 5 months ago, # ^ |   -12 No, an actress like পরীমনি shouldn’t participate in codeforces contest!
•  » » » 5 months ago, # ^ |   -10 A ball
 » 5 months ago, # |   -32 A lot of problem setter and tester including 300iq.I think this contest will be interesting.
 » 5 months ago, # | ← Rev. 2 →   -15 Sorry, but is any of authors or testers working in Ozon?
•  » » 5 months ago, # ^ |   +12 No
 » 5 months ago, # |   0
 » 5 months ago, # |   +33
•  » » 5 months ago, # ^ |   +4 :thinking:
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -14 Lol. I just reposted. Originally it was the reply to the meme which said "I'm out because Akikaze is setter" and that comment got removed. ¯\_(ツ)_/¯.
 » 5 months ago, # | ← Rev. 2 →   -10 .
 » 5 months ago, # |   +11 Ozon ≃ Ozone ≃ O 3 :)
 » 5 months ago, # |   +82 Why some users appear with it's real name, cities and in Black?
 » 5 months ago, # |   +1 I wish every round is combined
 » 5 months ago, # |   +55 TFW you can't submit a solution because "You have submitted exactly the same code before", list of submissions is empty, and mirrors are not working, nice// And it isn't a joke :(
•  » » 5 months ago, # ^ |   +18 Same here!
•  » » 5 months ago, # ^ |   0 What is more! We can not ask the questions in the contest interface because of request status code 500 error!
•  » » 5 months ago, # ^ |   0 Did you use late registration? I did, probably this is the source of bug
•  » » » 5 months ago, # ^ |   0 I didn't. It doesn't matter where the source, it just should not happen. And what surprises me most is the fact that this is a new bug. At least I never heard about this issue before
•  » » » » 5 months ago, # ^ |   0 agree
 » 5 months ago, # |   -23 I dislike this contest!
•  » » 5 months ago, # ^ |   -10 Same here! I cannot submit any task, but I want to participate in the lottery!
 » 5 months ago, # |   +59 Me after solving A, B and waiting for the contest end to see if I win a T-shirt or no :
 » 5 months ago, # |   +1 farewell, rating
•  » » 5 months ago, # ^ |   0 There is another contest tomorrow , you should be able to make it back.
•  » » 5 months ago, # ^ |   0 turns out, i disappointed the cf rating formula enough with my initial 4 rounds that I'm still getting rating even with poor performance:(
 » 5 months ago, # |   +10 Was randomized solution supposed in F?
•  » » 5 months ago, # ^ |   +8 Probably. I don't see any other way especially because it can be costly to even factor everything on the input.
•  » » » 5 months ago, # ^ |   +39 I have a deterministic solution for F — answer is always less then N + 1 (since we can always make everything even in at most N moves). Then it means we can only change smallest element d to (d — N, d + N). We can make a sieve upto 10^6 to find all primes in factorization of all numbers in this range, and then proceed with classic algorithm for each of those primes. I couldn't see what's the upper bound on number of primes like that, but I assume it's pretty small :P
•  » » » » 5 months ago, # ^ |   +3 What if every element in array is big prime number and also elements in array are pairwise different? Do you proceed n times?
•  » » » » » 5 months ago, # ^ |   +3 I factorize all elements in range (d — n, d+n) for one element of the array (in my case minimum), so this test should not be a problem
•  » » » » » » 5 months ago, # ^ |   +3 Yea, sorry. I misunderstood you
•  » » » » 5 months ago, # ^ |   +3 I just tried this solution, but n could be 2*10^5 and there're 17,986 prime numbers between 1~200,000. since we need O(n) time to obtain the sum of move counts for such prime number, it seems like 17,986 * 2*10^5(n) cause TLE. Do you have any idea about this?
•  » » » » » 5 months ago, # ^ |   0 Yeah, my best improvement is saving global answer and terminating gcd check as soon as my partial answer is bigger. I think I can unpack my solution, so take it with a grain of salt :P
•  » » » » » » 5 months ago, # ^ |   0 So it's something like $O(N^2/\log)$ with constant optimisations?
•  » » » » » » » 5 months ago, # ^ |   0 Probably yes, but I couldn't create a test where it would behave super badly. The "break when answer is bigger" check is pretty good in stopping almost all cases.
•  » » » » » » » » 5 months ago, # ^ |   0 Yeah, that complexity is already pretty good for many $O(N\log^2)$ problems if the constant factor is good. I'd rather not bet on it in-contest though.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -31 EDIT: This is wrong You can factor every number in O(nlogn) if you use a sieve like this:  /** * Return an array of primes up to and including N. Takes only O(N) time! * Also generates an array of the minimum factor for every number * from 1 to N, which can be used to find all factors of any number up to N. */ private static List primeSieve(int n) { List primes = new ArrayList<>(); // minFact[i] contains the minimum prime factor of i. int[] minFact = new int[n + 1]; for (int i = 2; i <= n; i++) { if (minFact[i] == 0) { primes.add(i); minFact[i] = i; } // Find multiples of i where primes[j] is the minimum prime factor. This loop will go exactly once for each // composite number. How it works: given a number i with prime factorization p1*...*pn, where p1<=...<=pn, // we say that, for each prime p <= p1, the number i*p is composite with minimum prime factor p. // Why this gets to every number exactly once: the number p1*...*pn will be generated only by p2*...*pn. // That's because all of it's prime factors need to be higher than it. for (int j = 0; j < primes.size() && primes.get(j) <= minFact[i] && i * primes.get(j) <= n; ++j) { minFact[i * primes.get(j)] = primes.get(j); } } return primes; } 
•  » » » » 5 months ago, # ^ |   +6 But $a_i$ is up to $10^{12}$, so it will work too long
•  » » 5 months ago, # ^ | ← Rev. 3 →   +8 Yes, choose any two element x, y, get all prime factor of gcd(x-1,y-1),gcd(x-1,y),..., gcd(x+1,y+1). Then try each factor. Each turn, you might get the correct answer with probability 1/4.Upd: choose any element x, get all prime factor of x-1,x,x+1. Then try each factor. Each turn, you might get the correct answer with probability 1/2.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +40 I don't know, but at least I solved with randomized solution. My Randomized Solution When $gcd = 2$, the number of operation must be less than or equal to $N$. Let $t_i$ be the number of operation that made for $i$-th element of array. It means: $t_i = |a_i - b_i|$ when $a_i$ is initial array and $b_i$ is final good array. You can prove easily, that in at least $\frac{N}{2}$ element, $t_i \leq 1$. Repeat 30 times as follows: Choose random index $i$ from $1 \leq i \leq N$. Let $t_{-1}$ be the set of prime factor of $a_i - 1$. Let $t_{0}$ be the set of prime factor of $a_i$. Let $t_{1}$ be the set of prime factor of $a_i + 1$. Let $T$ be the union of $t_{-1}, t_{0}, t_{1}$. For all value $v \in T$, check the minimum cost when $gcd = v$ with complexity $O(N)$. Total Complexity is $30 \times O(\sqrt{a_i} + N)$. It fails with at most $2^{-30} \approx 0.0000000931322$% probability.
•  » » » 5 months ago, # ^ |   0 How do you check the minimum cost in the whole set of primes T in O(N)?
 » 5 months ago, # |   +129 The gap from A to F is pretty good, but G and H are too hard..
•  » » 5 months ago, # ^ |   0 I am just curious how fo you generate these drawings they are really nice :)
•  » » » 5 months ago, # ^ |   +16 They are made using PowerPoint. :)
•  » » » » 5 months ago, # ^ |   +5 Ah you're the type that does Data Siens on Excel
 » 5 months ago, # |   +74 FaIr aNd BaLaNcEd cOnTeSt!
 » 5 months ago, # |   +1 It was a tough game, but it was great!
 » 5 months ago, # |   +6 How to solve D ?
•  » » 5 months ago, # ^ |   +44 Hint: Consider any $2$ leaves of the tree $u$ and $v$. Say $lca(u, v) = w$. Observe that $w \in${$u, v$} if and only if $w$ is the root. SolutionMaintain a tree $T$ which is initially the given tree. Now, keep doing the following:If $T$ has exactly vertex, then output that as the root. Otherwise, $T$ must have atleast $2$ leaves, so query any pair of leaves. If their lca is one of them then output that as the root otherwise delete both these vertices from $T$ and repeat this process.As each step either returns the answer or deletes exactly $2$ vertices, we use atmost $\lfloor \frac{n}{2} \rfloor$ queries.
 » 5 months ago, # |   0 How the heck is F solved? I passed pretests with what I presume is a nasty wrong solution, though I don't think I'm capable of generating tests that break it. Is there anything clean for that problem?
•  » » 5 months ago, # ^ | ← Rev. 3 →   +29 We can always make gcd=2 by using <= n operations, so let's use only < n operations. Let's say we applied operation on i c[i] times in optimal answer, then at least for n / 2 indices c[i] <= 1(otherwise (n/2) * 2 >= n). So just pick some index i and try to prime divisors of a[i] — 1, a[i] and a[i] + 1. Not sure if it's good enough to fit into TLE though.
•  » » » 5 months ago, # ^ |   +8 Fair enough, I guess that works. I feel dumb now.
 » 5 months ago, # |   0 How to Solve E?
•  » » 5 months ago, # ^ |   +12 I think you can construct the answer. Maximum possible number of triples is achieved in sequences like x, 2x, 3x, 4x, ..., kx, and you can calculate how many triples you can get for each k. If m > this number for n, the answer is -1. Otherwise you take the biggest number k less or equal to n, such that m is bigger than the maximum number of triples possible for this k. The first part of the answer would be 1, 2, 3, ..., k. Then you can add just one number: something like 2*k — 2*(how many more triples you need to get m in total), and you satisfy condition for m. If there are spare numbers left (n — k — 1), you can add a sequence of type (big number) * x — 1, which does not produce any more triples.
•  » » » 5 months ago, # ^ |   0 Thanks!
 » 5 months ago, # |   +6 Great problems! What's the logic behind E?
 » 5 months ago, # |   +3 how to solved D ??
•  » » 5 months ago, # ^ |   0 For every query, pick 2 from the current graph having degree 1. If the LCA is equal to any one of the 2 nodes you queried for, it is the root! Else remove these 2 nodes from the graph and repeat the same process.
 » 5 months ago, # | ← Rev. 3 →   0 Nice contest! I hope, i will get a T-Shirt ;)
 » 5 months ago, # |   +93 In case I win a random T-shirt.
•  » » 5 months ago, # ^ |   +39 More like
•  » » » 5 months ago, # ^ |   +12
•  » » 5 months ago, # ^ |   +15 now imagine not winning a shirt.
 » 5 months ago, # |   +1 I don't think it's allowed to send portable chargers? (lithium batteries)
•  » » 5 months ago, # ^ |   0 You can ship it on flights, given they satisfy the maximum mAh criteria. And I guess 10000 mAh is pretty much fine.
•  » » » 5 months ago, # ^ |   0 That's not true. Lithium batteries are only allowed to be hand carried in passenger planes or shipped in cargo planes. Since most mail services make use of passenger planes, they outright ban lithium batteries. Even if you use carriers like DHL you will need special approval.
•  » » 5 months ago, # ^ |   +1 Tell that to bootleg Chinese sellers on EBay.
 » 5 months ago, # |   0 How to solve C?
•  » » 5 months ago, # ^ |   +3 If a[i] % m = a[j] % m for some i < j, then answer is 0. Otherwise there are <= m numbers, so you can calculate answer in O(N^2).
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yeah the brute force will work, but I got a wrong answer in test case 15. Probably an OverFlow. I don't know what it is. I have used Long.
•  » » » 5 months ago, # ^ |   0 Got WA on Pretest 9 ;/ Codevoid solve() { int n,m; cin>>n>>m; ll ans=1L; ll num[n]; for(int i=0; i> num[i]; } for(int i=0; i(end — start).count(); / / cout << time_taken*1e-9 << setprecision(9) << endl; */}
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Not sure is it the case or not but...A possible cause is absence of "ans %= m" inside the loop after the "ans *= ..." part. I think that int64_t could be not enough to hold the value.
•  » » » » » 5 months ago, # ^ |   0 I even tried that, (a*b) mod m = (a mod m * b mod m) mod m but got WA on the 9th pretest itself. So then I changed it to this and no luck.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 You probably meant O(m^2) because O(N^2) should be TLE for N=10^5.I still do not get how to do that in O(m^2). Can you guys please explain?(The best I managed to try during the contest was O(N*m*log(N)), and I failed.)
•  » » » » 5 months ago, # ^ |   0 If ans!=0 for some i and j then it will be O(m^2) and unless m==N which is not the case(constraints).
•  » » » » 5 months ago, # ^ |   0 Got it (from this thread on this page).The pigeonhole principle. When N > m, existence of two numbers which are equal (mod m) zeroes the whole product.
 » 5 months ago, # |   +11 Is there a deterministic solution for F ?
 » 5 months ago, # |   0 Very fine and good statements. Thank you for these nice problems, but I had some problems with pretests on problems B and C -specially.
 » 5 months ago, # |   +66 If anyone's interested, the solution to F is described here.
•  » » 5 months ago, # ^ |   0 Wow the solution to today's problem had been written 2 years ago
•  » » 5 months ago, # ^ |   +17 Thanks, I was wondering why that felt so familiar.
 » 5 months ago, # | ← Rev. 2 →   +13 Another bloody lesson on CF Round: rand() only generate [0,65536) on codeforces......I got 6 wa and debugged for 20mins...Now I only hope that I can pass the system test...
•  » » 5 months ago, # ^ |   +67 The real lesson would've been to not have this covered by pretests.
•  » » » 5 months ago, # ^ |   0 Kinda tough to do that without keeping $N$ small in pretests.
•  » » » 5 months ago, # ^ |   +11 We decided to be nice, it's a bit less unfun to fail in pretests compared to failing on a hack :)
•  » » » » 5 months ago, # ^ |   +4 Bro, Thank you for being nice and preparing this excellent round~
•  » » » 5 months ago, # ^ |   0 Very good point! I am very grateful now.
•  » » » 5 months ago, # ^ |   +2 Just realized I haven't touched pretests of F. Completely forgot what I've done last year with hacking rand() lul, good thing someone else covered that.
 » 5 months ago, # |   +22 This round was one of the most interesting rounds I've participated!! Sooooo Amazing!!!!!
 » 5 months ago, # | ← Rev. 2 →   -43 I think it's better to give a warning in the blog if the contest contains any interactive problem(s).
•  » » 5 months ago, # ^ |   +14 I guess there is no rule as such.Usually the problem setters are kind enough to let us know before-hand so that anyone who is new to such problems, will take a look at it. :)
•  » » » 5 months ago, # ^ |   -10 Yeah. Actually that's why I am talking about this. Anyone who is not familiar with such problems may learn before participating and solve more problems.
•  » » » » 5 months ago, # ^ |   +22 Why only interactives? Just make the problemsetters announce all the problem topics so those who aren't familiar with them can learn them beforehand.
•  » » » » » 5 months ago, # ^ |   -9 Okay. It makes sense. I got the point :)
 » 5 months ago, # |   +6 "**The resulting string does not have to be empty**." due to this statement i got 2WA + late submission in B problem anyone faced same issue
•  » » 5 months ago, # ^ |   0 oh wow so i will get WA since i just deleted all the possible brackets...... (()) would fail for me :/
•  » » » 5 months ago, # ^ |   +3 actually i just realized i did solve it correctly since the number of deleted brackets dont matter , it is only the number of operations that matter.
•  » » 5 months ago, # ^ |   0 I did the same mistake. My answer should fail on cases like () but got an AC instead
•  » » 5 months ago, # ^ |   0 You should be grateful that the pretests covered it.I FSTed. :(
 » 5 months ago, # |   +9 Does D involves finding longest diameter of the tree, then query end points of that dia, if output of the interactor is one of the 2 ends, return that as that root. If not, then if interactor's output is a vertex not lying on the longest dia, return that vertex. Else (if lca returned is on the dia (but not the ends)), then check recursively the same process in the subtrees of that lca (by removing connection of lca and its neighbors that are not on the dia)?
•  » » 5 months ago, # ^ |   +10 It is more simple. Query two leaves, if response if one of those leaves, thats ans. Else remove those two leaves. Repeat.
•  » » 5 months ago, # ^ |   0 this approach will fail if all the nodes are connected to the same node
•  » » » 5 months ago, # ^ |   0 in that case you can output the last input we receive from interactor since that is the only vertex which will be left as we have removed all other vertex by removing 2 vertex n/2 times .
•  » » 5 months ago, # ^ |   +16 If the output of interactor, say w, is not one of the 2 ends(say n1 and n2) then you remove the edges connecting w to n1 and n2. You find the longest diameter again and repeat the process.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 implementing using this https://codeforces.com/contest/1305/submission/72494365 , but failing on 102th test case. Can you please help me with what am I missing?Upd: Nevermind. Got accepted, found the bug.
•  » » 5 months ago, # ^ |   +3 I did something related to diameter of the tree.You may notice you want to remove a lot of nodes, which are not candidates to be the root in each query, until you are left with one, which is done (fitting exactly in queries) by the approach in the editorial, too.I, instead, went on querying the ends of the diameter, and removing all nodes (and of course all other nodes in "subtrees" of the diameter nodes, except the LCA returned in the query, because all of them except the "w" returned in the query, are no longer candidates to be the root as all of them have atleast one vertex "above" them), and continued to do so until I have one node remaining.
 » 5 months ago, # |   +8 Systest when, fellow Stalker?
 » 5 months ago, # | ← Rev. 2 →   +10 How to solve G?
 » 5 months ago, # |   -9 Tests are strong (at least not shitty) this time, yes?
•  » » 5 months ago, # ^ |   0 Pretty sure making strong tests for F is a difficult problem in and of itself. My shitty solution passed pretests, we'll see about tests.
•  » » » 5 months ago, # ^ |   0 I also have something what I'm not sure about in E.Also was close in G, we'll see in upsolving.
•  » » » 5 months ago, # ^ |   +10 Well, your solution definitely can't get WA because the last part of your code checks all large divisors of (some number)$\pm n$ and every number will be modified at most $n$ times. The only thing I'm not 100% sure of is whether it's fast enough.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yes, in worst case scenarios it can check ridiculous amounts of primes (millions) and it checks each linearly. However, lots of optimizations and early stops make it very fast on most data.P.S.Accepted in 561ms. I am not capable of generating tests against it even if I strongly believe it's slow. Can't prove any good complexity either, but oh well, it passed.
•  » » » » » 5 months ago, # ^ |   +11 There are at most (78498 (number of primes <= 1e6) + 2 * n) primes in the factorization of numbers in [x-n, x+n] and that's a kinda loose upper bound anyway so it's not millions.
 » 5 months ago, # | ← Rev. 4 →   +34 Hacks for C: Hack Test Case2 2 1 2You can prove that when $M < N$ the answer is $0$. But, even if your source code assumes that when $M \leq N$ the answer is $0$, you will get pretest passed. (There is some hack cases like above)For me, first, my source code assumed that when $M \leq N$ the answer is $0$, and then I resubmitted. So I was able to notice hack case earlier, but there is no such source code in my room :(
•  » » 5 months ago, # ^ |   0 I checked that for all N < M the answer is 0 but how to formally prove it ?
•  » » » 5 months ago, # ^ |   0 There exist i,j i!=j such that a[i]%m==a[j]%m, hence (a[i]-a[j])==0 (mod m).
•  » » » 5 months ago, # ^ |   +1 If a and b have the same result after modulo m, |a — b| mod m = 0. Then it's pigeonhole principle.
•  » » » 5 months ago, # ^ |   +1 I guess you meant M < N. According to the pigeonhole principle, among >M numbers there will be at least two (call them a_i and a_j) with the same remainder upon division on M. Since there will be |a_i — a_j| or |a_j — a_i| in the product, the entire product will be divisible by M.
•  » » » » 5 months ago, # ^ |   0 Does that mean we assume all numbers given will be distinct?
•  » » » » » 5 months ago, # ^ |   0 Well, if some two are not distinct, that still have the same remainder. Moreover, then the product will be 0 automatically.
•  » » » » » » 5 months ago, # ^ |   0 Ok now I get it that for n > m even if we all are distinct there will be 2 that have same modulo by m. Thanks for your help
•  » » 5 months ago, # ^ |   +12 After staring at C for a good 20 mins, I had an epiphany. Pigeonhole principle! I smirked like the ninja in https://www.youtube.com/watch?v=pKO9UjSeLewAnd then wrote m>=n in my pigeonhole condition instead of m>nFML
 » 5 months ago, # |   +10 Nice problems with clear statements.
 » 5 months ago, # |   +77 TFW B is harder than F >:/
 » 5 months ago, # |   +3 Weak.Pretests on C
 » 5 months ago, # |   +18 Prepare for Polish Mafia in uphacking ;_;mnbvmar, show them what you think about them.
•  » » 5 months ago, # ^ |   -8 Hiiii Can you check this submission. Is this agreed in contest? https://codeforces.com/contest/1305/submission/72343610
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 As idea looks just like a solution from editorial. Of course, it looks like full of bugs, but it's typical obfuscation, which can be found in many places in CF (and is against rules!). Ofc I'm talking about #define int long long.
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 Please hack 72364530 72364506 72364194 72364859 . They all are same with a change in constant.72364859 and 72364466 are exact same but one got WA on tc93. P̶r̶o̶b̶a̶b̶l̶y̶ ̶a̶ ̶h̶a̶c̶k̶.̶ Dori added them ~20 mins before start of round.These are my ugly brute forces which survived system tests during testing. Idea was to run sieve and check all primes up to a constant (5e7 in the present case.) and then randomly pick a no and try to factorise it up to primes 1e4 then assume leftover prime and gcd and check it.The intent was to break solutions which doesn't check factors $a_i+1$ or $a_i-1$ .pajenegod has some similar solns which sieve up to 4e8 (using some superfast sieve.) and runs under 2s.One plan to break them was to increase $a_i$ up to $10^{14}$ but we didn't want to force factorisation in O(primes up to $10^7$) instead of O($\sqrt a_i$)
•  » » » 5 months ago, # ^ |   -13 You know that there is no rating limit for uphacking, yes? You can also try.
•  » » » » 5 months ago, # ^ |   +14 We tried hacking them during testing of the round. Btw only div1 users can up hack.
 » 5 months ago, # | ← Rev. 2 →   0 shouldnt n^2 solution for C fail?
•  » » 5 months ago, # ^ |   0 yes it would, however a (n <= 1000)^2 solution wouldn't, all answers for n > 1000 are always 0's. this is why you only calculate the answer for (n <= m).
 » 5 months ago, # |   0 For anyone interested in detailed analysis of problem C -- Here you go!
 » 5 months ago, # | ← Rev. 2 →   -47 Can any one plsss check this submission . How on earth this random submission got accepted. Its cheating https://codeforces.com/contest/1305/submission/72343610
 » 5 months ago, # |   +17 I had the proper idea for F, but my deterministic solution of course got TLE, but didn't realize I can do a randomized solution. I have never solved a contest problem with randomization till date. Can someone help me how to get started with such randomized solutions, so that it gets intuitive when I see a question in future to use a randomized solution with high probability. :)
 » 5 months ago, # |   +1 Does anything faster than $O(N^2)$ exist for C if the modulus was large?
•  » » 5 months ago, # ^ |   -18 from what i've seen the absolute difference instead of a normal difference ruins most possibilities of coming up with mathematic solution. ++ for an answer.
•  » » » 5 months ago, # ^ |   +30 If you sort the numbers in decreasing order then you can remove the absolute.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +29 I can only present a polylog solution, which should run way slower than the $O(n^2)$ solution in practice. After sorting the array we can get rid of the absolute value part. Then use divide and conquer, split into two subproblems of size $n$, then we need to multiply something which can be done using multipoint evaluation of a polynomial, which is a typical problem that can be solved using D&C and FFT in $O(n\log^2{n})$, therefore the overall complexity is $O(n\log^3{n})$.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +72 By understanding how multipoint evaluation works, you can make it in $O(n \log^2 n)$. Assume for simplicity that $n$ is a power of two. In fact, for each $i$, we want to find the remainder of the division of $(x - a_{i+1})(x - a_{i+2})\dots(x - a_n)$ by $(x - a_i)$.For each interval $[L, R]$ of the form $[2^i \cdot j, 2^{i} \cdot (j+1) - 1]$, compute $(x - a_L) \dots (x - a_R)$. Call it $P_{[L, R]}$. (This is in fact needed in multipoint evaluation as well.)Now, a recursive function $f(L, R)$ will compute all the results for $i \in [L, R]$. This function will receive $(x - a_{R+1})(x - a_{R+2})\dots(x - a_n) \mod{P_{[L, R]}} =: Q$. If $L=R$, we're done. Otherwise, let $m := \left\lceil \frac{L+R}{2} \right\rceil$ and notice we can call $f(L, m-1)$ with $(Q \cdot P_{[m, R]} \mod{P_{[L, m-1]}})$, and $f(m, R)$ with $(Q \mod{P_{[m, R]}})$. Each multiplication and modulo operation can be done in $(R - L) \log (R - L)$ time, hence $O(n \log^2 n)$ total runtime. Edit: notice that the "normal" multipoint evaluation does almost exactly the same stuff, only that $f(m, R)$ is called with $(Q \cdot P_{[L, m-1]} \mod{P_{[m, R]}})$; so that in each step, $f(L, R)$ will receive $\prod_{i \not\in [L, R]} (x - a_i) \mod{P_{[L, R]}}$.
•  » » » 6 weeks ago, # ^ |   0 Can you provide links to some similar questions?
 » 5 months ago, # | ← Rev. 2 →   -15 Problem C was : Pigeonhole principle
 » 5 months ago, # |   0 I don't understand why my sub idlenessPlz help me
•  » » 5 months ago, # ^ |   0 I think that you need to send a new line when you print the answer. cout << '!' << " " << ans; cout.flush(); vs cout << '!' << " " << ans << "\n"; cout.flush(); 
•  » » » 5 months ago, # ^ |   0 I have found out why it was idleness, when i used cout << flush;its no longer idleness. Btw tks bro.
 » 5 months ago, # |   -17 Comment on problem C: Next time, when $O(nm)$ solutions didn't suppose to pass the TL and $n=200000$, choose your $m$ like $3000$ or something!
•  » » 5 months ago, # ^ | ← Rev. 2 →   +6 Your solution is correct!The TLE was caused by an overflow You can see my submission of your code Here..
•  » » » 5 months ago, # ^ |   +3 Ohhh, Thank youuuu! Now I feel much better!
 » 5 months ago, # |   0 Hello, my solution for "B" got an Runtime Error on Test 24, where the String was all "(" (length;1000). The code gives correct answer on this case ("0", that is) on my editor, as well as some online editors too, when checked upon.Can someone please, check out and tell where it could have got a Runtime Error, because I don't think it (the code) can give Runtime Error.Thanking you with anticipation! Solution Link: https://codeforces.com/contest/1305/submission/72323474
•  » » 5 months ago, # ^ |   +1 ll i=0, j=close.size()-1; This will init j to huge value if close is empty.
•  » » » 5 months ago, # ^ |   0 Got your point, But actually j's value is saved "-1" through this statement, in most of the editors, as I told, above.Then, why does it assign a large value of "j" on the Editor and Compiler of CodeForces? Please explain the reason, if you know! Thanks!
•  » » » » 5 months ago, # ^ |   0 The vector.size() returns size_t, which is unsigned.However, if it is -1 the code still is undefined, since j is used as an index, and -1 is not allowed there, too.
•  » » » » » 5 months ago, # ^ |   -6 The "while" loop condition is there for not allowing the neg. value of "j". j>=0 This condition will stop that, anyways.
•  » » » » » 5 months ago, # ^ | ← Rev. 3 →   -16 Now, the code works, when I write the equations as follows:ll j=close.size();j--;Then, it works! Why is it happening like that? MikeMirzayanov
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   -6 Also, when I write "int", instead of "ll", it works!int i=0, j=close.size()-1;Can someone explain, why?
•  » » » » » » 5 months ago, # ^ | ← Rev. 3 →   +19 The type of .size() is size_t which is an unsigned integer type, so if the size is 0 and you subtract it by one, it will overflow (it may become a large integer). Therefore, you should not subtract the size without type casting.If you use ll j = close.size();j--; or int j = close.size();j--;, close.size() will be cast to ll or int, which is a signed integer, before you subtract it, so it works.If you use ll j = close.size() - 1, close.size() will be subtracted before it is cast, so it is wrong. But if you use int instead of ll, it "may" (since overflowing is an undefined behavior) be correct. size_t is a 4-bytes integer type and so is int. The binary result of subtracting an unsigned integer is as same as a signed integer type with the same size commonly, so the binary value of (size_t)0 - 1 is as same as (int)-1. (The value is the maximum value of a 4-bytes unsigned integer which is $2^{32}-1$, but the maximum value of a signed 4-bytes integer is $2^{31}-1$, so it will overflow to -1 when you cast it to int.)ll is not like that. Although the value of (size_t)0 - 1 is -1 when we regard it as an int, it cannot be cast correctly to ll.
•  » » » » » » » 5 months ago, # ^ |   0 Got the point.Thank you so much, for such a nice explanation!
 » 5 months ago, # |   +25 when we get the result of random t-shirt winner
•  » » 5 months ago, # ^ |   +47 I guess they first have to eliminate those hundreds of smart people who, after solving A and B, started modifying their codes to send from other accounts, instead of solving C.
 » 5 months ago, # |   +181 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters and update them again!
•  » » 5 months ago, # ^ |   0 Excuse me, I don't know how to report the cheating behavior, but it seems like the User Qingyu98821, who got the second place in Contest Codeforces Round #624 (Div. 3), is suspected of making his code obfuscated.
•  » » 5 months ago, # ^ |   -31 In problem B of todays contest it is clearly mention ed in the question that after applying the operations the string does not have the empty size. So naturally for test cases in which string is Simple string any answer is not possible.Kindly check the question..
•  » » » 5 months ago, # ^ |   +36 The resulting string does not have to be empty. "Does not have to be empty" meant it could be empty, or non-empty, will not affect the verdict.Mind your English, please. And if you were unsure about the statement, what prevented you from asking?
•  » » » » 5 months ago, # ^ |   -24 ok.from next time i will ask during the contest itself..
•  » » » » 5 months ago, # ^ |   -52 the resulting string does not have to be empty means that after the operations the remaining string must be of non-zero size.
•  » » » » » 5 months ago, # ^ |   0 Actually not. That'd be "the string cannot be empty" or "the string must not be empty".
 » 5 months ago, # |   -8 How to get test cases for D?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +14 How is it possible?Time: 15 ms, memory: 148 KBVerdict: OKInput6 41 44 25 36 32 3Participant's output3Jury's answer1Checker commentok Passed.
•  » » » 5 months ago, # ^ |   +3 when the prize is T-shirt Its possible
•  » » » 5 months ago, # ^ |   +3 Interactive test data is quite different from normal problems.In this problem specifically, the "input" showed in the submission details is equivalent to the hack format described in the statement, and the "output" here is number of queries used (actually this part is quite a placeholder, since I implemented the process of judging the answer to be in the interactor, not the checker).
•  » » » » 5 months ago, # ^ |   +3 Thanks
 » 5 months ago, # |   -30 I solved 2 problems in the whole contest. I was relieved by this . My submission was accepted so I started thinking about next problem. Now I only got 1 correct submission . What is this ???? Who should I report to for this incident? :(
•  » » 5 months ago, # ^ |   +25 Looks like your solution on B failed on system test.To make it clear, ịn a contest your solution will be judged by a smaller set of tests (called "pretests"). After contest time, it'd be judged again.We tried our best to make the pretests strong, but it's certain that not every case can be covered. :(
•  » » 5 months ago, # ^ | ← Rev. 3 →   +27 Btw your error was on this line while(open[o]
•  » » » 5 months ago, # ^ |   0 Thanks I got it :)
 » 5 months ago, # |   -18 Give me T-shirt
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 You'll get a T-shirt if you're lucky, Because there are only 30 T-shirts, good luck everyone.
 » 5 months ago, # |   +63 I am just wondering what tourist does with all those T-shirts and iPads that keep piling up...
•  » » 5 months ago, # ^ |   +97 Obviously he puts on all t-shirts at once and pretends to be an onion while simultaneously watching 20 cooking shows on his ipads
•  » » » 5 months ago, # ^ |   +47 Actually when I read it I picture Um_nik doing that. I don't know why.
•  » » » » 5 months ago, # ^ |   +294 I guess because in 1 T-shirt I look like a human in 20 T-shirts?
•  » » » » » 5 months ago, # ^ |   0 You made my day with your joke ... I am laughing now :)
•  » » 5 months ago, # ^ |   0 tourist be like:
 » 5 months ago, # |   +1 Im so sad because i miss the last one second to submit my D answer.And after the contest ,i checked it's right...
 » 5 months ago, # | ← Rev. 2 →   -36 .
 » 5 months ago, # |   -6 Great round, really nice non-standard problems.
 » 5 months ago, # |   +33 When t-shirt winner will be announced?
 » 5 months ago, # |   -9 this contest broke my record: the previous greatest rating change(with the maximum absolute value) is +131 and now it's -145. QWQ
•  » » 5 months ago, # ^ |   +7 -157, hold my beer
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +27 Seems you were overrated before the contest :)
•  » » » » 5 months ago, # ^ |   +7 In fact my real rating is around 1400
 » 5 months ago, # |   0 if my submission gets partially acceptd or it passes 3-4 testcases, will that be counted or not?? I am not getting rating mechanism, kindly help??
•  » » 5 months ago, # ^ |   -9 No
 » 5 months ago, # |   0 My rank go up about 200 after the system tests...
 » 5 months ago, # |   +30 When the t-shirt winners will be announced?
•  » » 5 months ago, # ^ |   +15 I think they have finished removing fake accounts.
 » 5 months ago, # |   0 Why Rollback, any valid reason please?
•  » » 5 months ago, # ^ |   -9
 » 5 months ago, # | ← Rev. 2 →   +15 I guess removal of fake account done by team codeforces. Waiting for tshirt winner announcement
»
5 months ago, # |
+167

And the winners of t-shirts are (congratulations!):

List place Contest Rank Name
1 1305 1 tourist
2 1305 2 maroonrk
3 1305 3 peehs_moorhsum
4 1305 4 ksun48
5 1305 5 Endagorion
6 1305 6 Benq
7 1305 7 gisp_zjz
8 1305 8 neal
9 1305 9 Um_nik
10 1305 10 yasugongshang
11 1305 11 izban
12 1305 12 boboniu
13 1305 13 mnbvmar
14 1305 14 yhx-12243
15 1305 15 NoLongerRed
16 1305 16 I_love_Tanya_Romanova
17 1305 17 yosupo
19 1305 19 Marcin_smu
20 1305 20 E869120
21 1305 21 vepifanov
22 1305 22 BigBag
23 1305 23 icecuber
24 1305 24 ohweonfire
25 1305 25 cuizhuyefei
26 1305 26 Martin53
27 1305 27 Golovanov399
28 1305 28 qazswedx2
29 1305 29 receed
30 1305 30 ashmelev
31 1305 31 Kostroma
32 1305 32 ainta
33 1305 33 Petr
34 1305 34 SkyDec
35 1305 35 Hazyknight
36 1305 36 DCXDCX
37 1305 37 KAN
38 1305 38 cwise
39 1305 39 chemthan
40 1305 40 Quang
41 1305 41 Reyna
42 1305 42 isaf27
43 1305 43 molamola.
44 1305 44 8-_-8
45 1305 45 wrinx
46 1305 46 Elegia
47 1305 47 jijiang
48 1305 48 orz
49 1305 49 poisonous
50 1305 50 cerberus97
51 1305 51 marX
52 1305 52 AndreySergunin
53 1305 53 Maksim1744
54 1305 54 nickIuo
55 1305 55 wucstdio
56 1305 56 voidmax
57 1305 57 Noam527
58 1305 58 Alex_2oo8
59 1305 59 yashChandnani
60 1305 60 darnley
114 1305 114 Marckess
215 1305 215 olphe
386 1305 386 idxcalcal
475 1305 475 HCPS42
579 1305 579 _dsstar
765 1305 764 nicoing
866 1305 866 WildWesam
921 1305 921 smurf
1488 1305 1488 Hitesh_0301
1920 1305 1920 killer_lsy
2025 1305 2025 crazy__1234
2026 1305 2026 Srk1C
2325 1305 2324 mutinner2
2427 1305 2427 zmy123456
2467 1305 2467 ssvirk
2570 1305 2569 volkov179
2690 1305 2689 vaibhavsarda
2711 1305 2711 sachitb
2932 1305 2932 Chintan_295
2961 1305 2962 wangjingting
3933 1305 3930 pln.
4188 1305 4186 AmineWeslati
4306 1305 4306 uddeshya.singh
4340 1305 4344 usertab34
4500 1305 4495 Anuj_0911
4652 1305 4657 Icewill
•  » » 5 months ago, # ^ |   0 Hey MikeMirzayanov! I can see my name in this list, might I ask how do I redeem this Tshirt? Like where can I fill in my delivery addresses and everything? (newbie at this section of forces)
•  » » » 5 months ago, # ^ |   0 You can fill it at your home page where you can see an address page and select your T-shirt size.(also a newbie at this section,figured it out just now)
•  » » » » 5 months ago, # ^ |   0 Thank you!
•  » » 5 months ago, # ^ |   0 Excuse me,if I see my name on the list,but didn't filled the address beforehand,if I filled it now can I still receive it?(didn't even thought I'd be able to use the address page)
•  » » » 5 months ago, # ^ |   0 Similar query here , MikeMirzayanov.
 » 5 months ago, # |   +41 Congrats to Pajaraja for his 11th consecutive rating increase, all the way from Specialist!
•  » » 5 months ago, # ^ |   +40 Thanks! Hopefully I won't end up taking a trip back to Specialist now.
•  » » 6 weeks ago, # ^ |   0 orz!!
 » 5 months ago, # |   +3 When will the T-Shirt winners be announced ?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Here\ntrqwertg..