By deltixlab, 5 months ago, translation,

Hi Codeforces!

We are DELTIX. Founded in 2005, DELTIX is one of the market leaders in software development for financial research and products for systematic and algorithmic trading. In 2020 DELTIX joined the EPAM family. Our mission is to turn promising ideas into breakthrough products fast.

We are experts in:

• aggregation, storage, and processing large volumes of time-series data
• data modeling
• testing and deployment of quantitative models

In our team we value skills like:

• knowledge of algorithms
• high-performance coding
• low latency data streams processing

Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces. Today, we are excited to welcome you to the first installment of our rounds (joined Div1 и Div2) — Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2), that will start on May/30/2021 17:35 (Moscow time).

It is an open and rated round for both divisions.

We have prepared the following trophies for you:

• 1st place = the most desired console of 2021 — PlayStation 5!
• 2nd place = Nintendo Switch
• 3rd place = Nintendo Switch Lite
• 1-100: branded t-shirts

Another 100 t-shirts will be distributed randomly between 100 participants outside of top-100 and who have solved at least one problem and participated in rated Codeforces rounds before.

Problems have been prepared by our employees: Vladik, netman, AleXman111 and sdryapko.

We would like to say a word of appreciation:

We will offer participants 8 problems and 135 minutes to solve them. We wish everybody good luck and high ratings!

Fill out a short contact form if you are interested in internship and/or employment opportunities or would like to speak with recruiters or members of our team.

Contact Form →

UPD: The scoring distribution is 500 — 1000 — 1500 — 2250 — 2250 — 3000 — 3250 — 3250.

Thank you all for participating! (editorial)

Congratulations to the winners:
1. tourist
3. Um_nik
4. maroonrk
5. ecnerwala
6. jiangly
7. SSRS_
8. Petr
9. scott_wu
10. Maksim1744

We would like to express our special congratulations to the top three leaders! We will try to send you your well-deserved prizes as soon as possible :) Unfortunately, we can not list the people who received 100 random T-shirts due to the fact that the search for cheaters is not completed.

• +198

 » 5 months ago, # |   +174 So Which game are you going to play tourist on your brand new Play Station 5?
•  » » 5 months ago, # ^ |   +86 he already has 50 of them from code jam and hackercup
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 I came up with same comment to post in my mind but then I also knew that this praising will be surely down there already!
•  » » » 5 months ago, # ^ |   +2 I think you should reconsider your statement after the contest is over!And see the standing once :)
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 DELTIX AC Quest :)
 » 5 months ago, # |   +171 Crossing my fingers that "we value skills like high-performance coding" doesn't mean "Anyone who uses java is going to have a concussion from banging their head against their desk because of how tight we made these time limits"
•  » » 5 months ago, # ^ |   +41 If you think about it, screencasts are high-performance coding.
•  » » 5 months ago, # ^ |   -30 Will it be better if time limits are according to the languages?
•  » » » 5 months ago, # ^ |   -13 It will be better if we have websites according to languages! maymay
•  » » » 5 months ago, # ^ |   +3 you are a classic example of minority being bashed by majority... xD
•  » » 5 months ago, # ^ |   +30 Well, it's a finance/trading company. Taking the phrase "make really good decisions really fast" to a completely new level is the only chance they have to be profitable. Their limits are imposed by competitors, not arbitrarily chosen. (That also gives you all the more opportunity to fail in this industry.)
•  » » 5 months ago, # ^ |   -20 Still not as tight as ur mom
•  » » » 5 months ago, # ^ |   0 Lmao, didn't see this coming at all
 » 5 months ago, # |   +35 The more different rounds, the better! I also really hope that the tasks will be good.
 » 5 months ago, # |   +31 Nice T-shirt :)
•  » » 5 months ago, # ^ |   0 Look please at the comment above yours! I think that guy tells the truth
•  » » » 5 months ago, # ^ |   0 BOT_SaNyA orz
 » 5 months ago, # |   +40 "Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces." Wait, so we're gonna have one of these every 3ish months? :O
•  » » 5 months ago, # ^ |   +113 Yes, that's the plan! :) I hope we will delight you with our tasks
 » 5 months ago, # |   +5 I would love to have that PS5.But I won't be able to achieve that this time.Maybe 5-6 years later in some div1 + div2 I will get PS6!!!
•  » » 5 months ago, # ^ |   0 Buying with your money is better in than, 5-6 years :)
•  » » » 5 months ago, # ^ |   +7 I am poor.Besides,winning something has a different sort of satisfaction.
 » 5 months ago, # |   +2 Best of luck to all the participants :)
 » 5 months ago, # |   +25 Warning: This round will be slightly harder, because I will be on a plane instead of donating my rating.
 » 5 months ago, # |   +25 Please make the pretests strong! That's all I ask.
•  » » 5 months ago, # ^ |   +55 May the pretests be strong and time limits long.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +87 Just like your D
 » 5 months ago, # |   0 Woah 8 problems? This one is big.
•  » » 5 months ago, # ^ |   +200 okay sorry I'm done
•  » » » 5 months ago, # ^ |   +18 I like it when SecondThread gets involved in the comments!!
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   0 Specially when they have double meaning ; ), reaching "69+" upvotes on his sense of humour.
•  » » » » » 5 months ago, # ^ |   0 wait I didn't get the joke.. Can u explain it?
•  » » » » » » 5 months ago, # ^ |   -12 Never ask someone to explain their Code and by that extension their jokes, cause guess what?? all code is a joke!
•  » » » » » » » 5 months ago, # ^ |   0 I just really hope your codes are better than your jokes.
 » 5 months ago, # |   +9 Nowadays codeforces is giving a lot of gap between two contests
 » 5 months ago, # | ← Rev. 2 →   0 nvm, it changed
•  » » 5 months ago, # ^ |   0 Bro see it again cf contest page also shows 2:15
 » 5 months ago, # |   0 Nice prizes !! Hope to win one of them in the future :))
 » 5 months ago, # |   0 8 problems in 2 hour and 15 minutes... are we going to face some easy questions!
•  » » 5 months ago, # ^ |   -11 :)
•  » » 5 months ago, # ^ |   0 maybe it's a trap
•  » » » 5 months ago, # ^ |   +3 yes its_Atrap
•  » » » » 5 months ago, # ^ |   -7 Poor trap sir, Everytime someone(me) ends up using his handle for replying to his comments ends with hoooge upvotes. But when he is using his own handle to reply he ends up getting downvotes. Please give him deserved upvotes
•  » » » » » 5 months ago, # ^ |   +8 The world is so cruel :(
•  » » » » » » 5 months ago, # ^ |   0 well what can we say, all I know is its_Atrap
 » 5 months ago, # |   0 the prizes are really good
 » 5 months ago, # |   +15 Me being a 'specialist' calculating my probability of winning a PS5 in a combined round. But I forgot I'm bad at probabilities and even CP (-_-)
 » 5 months ago, # |   -37 With all due respect
•  » » 5 months ago, # ^ |   0 r/antimeme
•  » » 5 months ago, # ^ |   0 You're the second one.
 » 5 months ago, # |   +2 Can I have a T-shirts from the random generator :)))
 » 5 months ago, # |   +91
•  » » 5 months ago, # ^ |   +100 I actually disagree with my meme I don't want to enjoy my new color
 » 5 months ago, # |   +1 Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces. I'm excited to see that! Woahh, more div.1 + div.2 means more participating for me
 » 5 months ago, # |   +9 Time for SpeedForces.
 » 5 months ago, # | ← Rev. 2 →   0 when you know there are playstation 5! you must be ready for the contest
 » 5 months ago, # |   +24 I feel a little envious about the top three.
•  » » 5 months ago, # ^ |   0 what is the name of the anime?
•  » » » 5 months ago, # ^ |   0
•  » » 5 months ago, # ^ |   +5 Gif works here ??!!! Wuuuut how
•  » » 5 months ago, # ^ |   +45 People good enough for top 3 probably already won 8 PS5s, 20 Nintendo switches, and 69 T-shirts. The only polite thing to do is ask the winners to give you their prizes.
•  » » » 5 months ago, # ^ |   +8 1-gon can you give me your prizes that you have won ?!!
•  » » » 5 months ago, # ^ |   0 I am poor guy :) I have a dream to have ps5 from last 20 years :)
 » 5 months ago, # |   +3 I'm very excited for this one, since it's happening after a long time. All the best everyone.
 » 5 months ago, # | ← Rev. 2 →   0 I already knew that the PS5 is going to be one of LGM's. :)
 » 5 months ago, # | ← Rev. 7 →   0 Deletdd
 » 5 months ago, # |   -6 Hope Bugaboos will be good. May random be on my favor (that doesn't mean i want t-shirts :p)
 » 5 months ago, # |   +7 how many bugaboos?
•  » » 5 months ago, # ^ |   +21 8 bugaboos, bro
 » 5 months ago, # |   0 As a tester, I can assure the problem set is fun, well atleast the first half surely is. Good luck!
•  » » 5 months ago, # ^ |   +24 Thanks for confirming you weren't able to solve any of the last half problems
•  » » » 5 months ago, # ^ |   +16 yay trap is purple, orz
•  » » » 5 months ago, # ^ |   +1 If I could, I wouldn't be stuck at low expert right :)
•  » » 5 months ago, # ^ |   +16 As an author, I want to assure that the second half is also worthy of attention :)
•  » » » 5 months ago, # ^ |   +4 Are the problem statements long?
•  » » 5 months ago, # ^ |   +32 I didn't think it was much fun at all. The first 3 problems were pretty trivial and the rest were way too hard for me.
 » 5 months ago, # | ← Rev. 2 →   -57 tourist can you don't give your PS5 to me?
 » 5 months ago, # |   0 Good Luck everyone for this round!!!
 » 5 months ago, # |   +23 We have four purple questionsetters!
•  » » 5 months ago, # ^ |   +33 no :)
•  » » » 5 months ago, # ^ |   +4 Why the downvotes and no? Is the usage of question not allowed?
•  » » » » 5 months ago, # ^ |   -6 Sorry, I didn't really understand your question. If you think that I put a minus on your comment, then this is not true)
•  » » » » » 5 months ago, # ^ |   0 My mistake ：）
•  » » » » 5 months ago, # ^ |   0 It is no because he was purple when the blog was written but now he is a master.
 » 5 months ago, # |   0 8 problems! Can you please increase the contest duration a little bit more?
 » 5 months ago, # |   0 Excited!!
 » 5 months ago, # |   0 Where is Anton when you need him?
•  » » 5 months ago, # ^ |   +117 Killed by 313 people yesterday :'(
•  » » » 5 months ago, # ^ |   +8 That's kind of like what I meant. Wonder why I got downvotes...
 » 5 months ago, # |   0 Amazing prizes and I hope it's amazing contest Thanks :))
 » 5 months ago, # |   -7 I think the contest's description should say here's a new ps5 to tourist and the rest of the things for the top 500
 » 5 months ago, # |   +40 The winner of the contest will be probably have no time to play PS5 otherwise he wouldn't be the winner in first place :D
•  » » 5 months ago, # ^ |   +55 Umnik disagrees.
•  » » » 5 months ago, # ^ |   +5 EnEm also disagrees.
 » 5 months ago, # |   +18 what about scoring distribution? Also as a contributor i want some testing.
 » 5 months ago, # | ← Rev. 3 →   +10 :)
•  » » 5 months ago, # ^ |   0 yes
 » 5 months ago, # |   +5 everyone talking about prizes, I'm thinking to become candidate master asap.
•  » » 5 months ago, # ^ |   +6 bro, you improved a lot after the 17th or 18th contest that you gave. Can you tell what specifically did you do or how did you practice in that period
•  » » » 5 months ago, # ^ |   +2 hard, I gave a lot of time to it.
•  » » » » 5 months ago, # ^ |   +3 thx bro, i will also try harder...
 » 5 months ago, # |   +3 is it impossible to improve in codeforces without watching anime ?
•  » » 5 months ago, # ^ |   +3 no.
•  » » 5 months ago, # ^ |   +6 Yes. Anime is essential
•  » » 5 months ago, # ^ |   0 Yes, you have to be a man of culture to solve CP questions :)
 » 5 months ago, # |   +2 hoping this will not be a div 1.5 round !
 » 5 months ago, # |   +9 Score distribution looks sus
•  » » 5 months ago, # ^ |   +21 Seems like it'll be a contest of who can get D and E for me...
 » 5 months ago, # | ← Rev. 2 →   0 Can someone clarify that will it be rated for Div. 2 participants or not?
•  » » 5 months ago, # ^ |   0 Yes, it will!
 » 5 months ago, # |   0 is it going to be a difficult or moderate one looking at the scoring distributions
•  » » 5 months ago, # ^ |   +1 It will clear in contest..
 » 5 months ago, # |   0 Codeforces is broken on my PC but it's working fine on mobile. Is it only happening to me?
•  » » 5 months ago, # ^ |   0 Yes sometimes it happens on PC.
•  » » 5 months ago, # ^ |   0 It is fine for me
 » 5 months ago, # |   0 It will be my first contest as a specialist. Hoping for the best.
•  » » 5 months ago, # ^ |   +1 +1
•  » » 5 months ago, # ^ |   0 Congrats :)
•  » » 5 months ago, # ^ |   0 my first round as pupil. hoping for the best
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 Good luck!
 » 5 months ago, # |   +1
 » 5 months ago, # |   -32 deltix round == bad round
•  » » 5 months ago, # ^ |   +30 deltix round = Div1 round :(
•  » » 5 months ago, # ^ |   0 true
 » 5 months ago, # |   +26
 » 5 months ago, # |   +7 Looking at the standings, it seems Tourist is in urgent need of another PS5 ! Oh by the way, is there going to be Bugatorial for this round?
 » 5 months ago, # |   +4 What's wrong with B??
•  » » 5 months ago, # ^ | ← Rev. 2 →   +4 Observation.. For any two pair you need to perform 1 1 2 1 1 2 or 2 1 1 2 1 1 or 1 2 1 2 1 2 or any valid formation ;)
•  » » » 5 months ago, # ^ |   +1 1 2 1 1 2 1 works also...Indeed a good observation problem
•  » » » 5 months ago, # ^ |   +1 Yeah... I got the hint just after I expressed my frustation here. It was my problem I read the question hastly. I think the basic step is how to swap two numbers without third variable logic.
•  » » 5 months ago, # ^ |   0 Just upvoting you because your name is Luffy\m/_(>_<)_\m/
 » 5 months ago, # |   +7 And i thought the contest will be easy since it has 8 questions.LOL!!!!!!!!!
 » 5 months ago, # |   +18 I really wish an easier problem was in place of D. Instead of writing this comment, I would have been solving a problem that was actually in my league. Contest would have been more enjoyable :(
 » 5 months ago, # |   +1 Out of > 18 000 registered participants only 8 700 submitted anything after 90 minutes.
 » 5 months ago, # |   +20 speedforces
 » 5 months ago, # |   +1 D is too tough to even try
•  » » 5 months ago, # ^ |   0 The fact that you were able to solve A, B, C in this contest indicates that you already punched way above your weight.
•  » » » 5 months ago, # ^ |   -36 I am expert lol, I am fucking up some recent contest hence I am giving from this fake id
 » 5 months ago, # |   -20
 » 5 months ago, # | ← Rev. 2 →   +166 statement of C is shit
•  » » 5 months ago, # ^ |   0 I agree, I've given many rounds and i don't say they are bad just because I performed poorly but today's C problem statement was totally shit ;( they could've explained it in a better way.
 » 5 months ago, # | ← Rev. 3 →   0 Please, help understand problem Ethis bruteforce solution gives wa on 2-nd and 3-rd samples Spoilerfull code: 117916698 void go(string s, const int m, const int k, ll &sum , ll &cnt) { const int n = size(s); int cur = 0; for(int l=0,r=0; l 1) { cnt+=1; sum+=m; return ; } cur-= s[l] == '1'; } for(int i=0;i
•  » » 5 months ago, # ^ |   0 Different sequences of operations have may have different probabilities, so you can't just calculate sum and divide by their number.
•  » » » 5 months ago, # ^ |   0 ok, got it
 » 5 months ago, # |   +9 Problem statements should have been more clearer.(also no need of that image in each ques) :(
 » 5 months ago, # |   +22 Oh wow! Not only bugaboos were great, but also these beautiful pictures in every bugaboo! Awesome contest.
 » 5 months ago, # |   +30 how to solve the problem D ?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +5 You would only need to test up to 2**p = 32768 bitmasks, and I think which can be optimised.I have yet to pass systests however.Edit: Failed systests, my solution is actually O(N * 2**(2*p))
•  » » » 5 months ago, # ^ |   +3 I came up with a solution, with complexity O(const * n * 2 ^ p) but it's TLE. how fast did you check is the mask good or no ?
•  » » » » 5 months ago, # ^ |   +5 You don't need n, you can maintain a map with the number of each state. As for iterating subset it is 3^p. So total complexity is O(n + 3^p)
 » 5 months ago, # |   +11 Thanks for the interesting problems!
 » 5 months ago, # | ← Rev. 2 →   +140 Ok C is the worst problem I have ever seen. I spent about 40 minutes staring at it and I didn't understand the statement till now. How could this problem even got accepted by coordinators?Apart from that the problems were great but this really ruined the contest for me.
•  » » 5 months ago, # ^ |   +45 I would never have understood it if not for the samples, but reading the sample explains it pretty well, I think.
•  » » » 5 months ago, # ^ |   +24 I'm not sure. At the end I just implemented some greedy shit that got accepted :D
•  » » 5 months ago, # ^ |   +16 look at the image
 » 5 months ago, # |   +94 Such a lousy statement on Problem C, it's a shame. Incomprehensible what this is about. The setters work hard to develop and work out great problems, and then ruin the result with an incomprehensible statement text. Why? I do not get it.
•  » » 5 months ago, # ^ |   +4 Still don't know what we are supposed to do exactly, lol.
•  » » 5 months ago, # ^ |   +12 I have assumed the problem only by looking at the picture.
 » 5 months ago, # |   +8 wasn't able to understand what the task C meant till end of the contest ;(
 » 5 months ago, # |   +6 Pun Intended, tourist give me your old play station. :)
 » 5 months ago, # |   +4 Am I the only stupid one who write about 100 lines for C and get 6 was??? It feels terrible (especially I notice other people in the same room pass this bugaboo neat and quickly :(
 » 5 months ago, # |   +2 My strategy after struggling for hours with C.. Just relax in the forthcoming Deltix Rounds. Peace.
 » 5 months ago, # | ← Rev. 2 →   0 could someone provide counter case for this submission of problem c. Got 6 WA on this problem.
 » 5 months ago, # |   +97 I hate combined rounds! I was sure that I would be able to hack a few people in D because my solution was randomized and usually, there are people who still don't seed their random number generators. However, because the round was combined and the room was mostly greens or cyans, there were only two solutions in my room, one of which had good random and the other didn't seem to have random at all.
•  » » 5 months ago, # ^ |   +13 Wow, how do you do it without randomisation?
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +13 I tried all possible subsets of (sensible) currencies (there is at most 2*p = ~30 of those) XD I implemented custom bitset and pruned execution if some subset yielded less than n/2 interested peoples. I doubt it will pass max tests, it passed pretest within 700ms though. For reference: Submission 117911694Edit: Systests passed in 750ms :D Hooray
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   0 I did almost the same thing. Maybe you can continue the loop when this state's number of $1$ is less than or equal to the current answer. And it got TLE :(Then I tried to break at 2.8s, it passed again :((And my solution got hacked(WA) yet...Now I wonder whether there's a solution without random
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 The main difference between our solutions is the presence / absence of prunning. What do I mean by that?Consider that you use some subset of currencies (for example currencies 100110) and you've concluded that it's impossible to satisfy at least $\frac{n}{2}$ people. This means that you don't have to evaluate all "super-masks" (supersets of currencies), for example 110110, 101110, 100111 and any other. And I see that you evaluate the satisfacion for those masks anyway. In my case, the reccurence does not "enter" any states corresponding to superset (which is hard to do with loop).The other difference is the computation of guests satisfaction. From what I see your logic is somewhat convoluted because of your data structure — you have bitset mapping which person likes what currency, and I have it the oposite way — which currency is liked by whom. It gives fast computation to check if enough guest will be satisfied (it allows for computing bitwise and in O(n/32)).
•  » » » » » » 5 months ago, # ^ |   +8 You are right. I totally don't consider supersets of failed masks. But I remember bitset's time factor is divide by 32 or 64 too...
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +24 I did similar thing and got TLE on test 112!!!Edit : It can be saved if I get a T-shirt!
•  » » » » 5 months ago, # ^ |   0 I tried to implement similar idea, but in python. Guess I had no chance
•  » » » » 5 months ago, # ^ |   0 Can you explain your approach?
•  » » » » » 5 months ago, # ^ |   +4 Yes.First, you start by selecting only currencies that interest at least n/2 friends. It can be shown, that there are at most $2p \leq 30$ such currencies. In my code I store their indices in vector relev (it contains only RELEVant currencies).Secondly, you create bitsets for your relevant currencies. In other words, you create around $2p$ bitsets of size $n$. We need those to be betsets because we need them to quickly compute bitwise and and number of ones (ie. popcount).Now we proceed to the reccurence. If you have some subset of first $idx$ currencies, you can either add the next one to the set or skip it and proceed with the same subset. If you added your currency, check if it satisfies at least $\frac{n}{2}$ people. If it doesn't — don't evaluate reccursive call (bitset zadowoleni, which means "satisfied" in Polish, stores the bitset of people satisfied with current currency subset; sklej method computes bitwise and). Now simply return the best of the two reccursive calls. In short, recurrence structure is as follows: solve(currencies subset S, int idx): if idx == all currencies count: return S S' = S.union(currency number idx) if S' is liked by at least n/2 poeple: solve(S', idx + 1) solve(S, idx + 1) return best of recurrence calls Finally you simply reconstruct the answer with all currencies based on relev vector.
•  » » » » » » 5 months ago, # ^ |   0 What would be the time complexity, O(2**(2p)) for the bitset, and O(N) for the comparison, leading to O(2**(2p)N)? Or am I missing something?
•  » » » » » » » 5 months ago, # ^ |   +1 Roughly speaking, yes. But note, that any solution can have at most $p$ currencies so we are quaranteed not to check all $2^{2p}$ sets even in the worst case, but only sets with size up to $p$. In the average case I believe it will compute much less currency subsets.Additionaly, comparison has a very low constant factor due to bitset ($O(N/32)$).
•  » » » » » » » » 5 months ago, # ^ |   +8 Thanks, this is a nice solution, especially how it utilizes the powers of 2 to suppress the time complexity :D.
•  » » » » 5 months ago, # ^ |   0 Hey Wielomian, I tried running your submission — https://codeforces.com/contest/1523/submission/117911694 but it is now TLE'ing in TEST-131. Any workaround how to proceed with this?My submission with the same code — https://codeforces.com/contest/1523/submission/118490042
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +1 I hacked it back in the day (You can see the hack at Submission 117911694). It seems that the system tests were simply weak and that there was no max test with $2p$ relevant currencies (which is weird). And thus allowed for such a solution to pass. Possibly this testcase was added after the hack for upsolvers.To me it seems that one must incorporate the $dp$ as described in the editorial rather then bitsets to have fast update of people counts for subsets, which I don't understand, honestly.
•  » » 5 months ago, # ^ | ← Rev. 2 →   -150 You motherfucker , go suck radewoosh dick and eat shit. You don't like cOmBiNeD round then why participated asshole ? SpoilerDeltix employeeRadewoosh and you polish shit don't trigger me!
•  » » 5 months ago, # ^ |   0 How to solve D with randomisation (
•  » » » 5 months ago, # ^ |   +37 Select a random person. With probability $\frac{1}{2}$ they are in the $\frac{n}{2}$ chosen in the optimal solution.Then you can do bitmask DP over only the bits that they like.Repeat 30 times for $2^{-30}$ chance to fail.
•  » » » » 5 months ago, # ^ |   0 Hi, Suppose I select a person and I do all the bitmask, there are 2^p masks but in order to know how many members are there in that mask, I need to iterate all of n right ? Even with iterating only among the persons where the mask exists, I will still be needing 2^p instead of n, so the complexity becomes O(iters * (2^2p)) or (O(iters * n * 2^p) which is worse than the brute force O(n * 2^p) ). How to eliminate 'n' or another 2^p ?
•  » » » » » 5 months ago, # ^ |   0 You count how many times each of the possible $2^p$ bitmasks appears in $\mathcal{O}(n)$ time. Then you do SOS dp in $p \cdot 2^p$ time to count for every bitmask how many times a bitmask containing all of its bits appears.
•  » » » » » » 5 months ago, # ^ | ← Rev. 5 →   0 Actually how to count each of the possible 2^p masks appear in O(n) time ? Wont it be O(n * 2^p) ? could you pls elaborate ?Also could you pls elaborate on what you are doing here ? for (int x = 0; x < k; ++x) {  for (int y = 0; y < (1 << k); ++y) {  if (y & (1 << x)) cou[y ^ (1 << x)] += cou[y];  }  }... 
 » 5 months ago, # |   +1 I reduced problem D into a bipartite graph problem where friends would be in one side and currencies would be in another side. Now, if we select x from friends and y from currencies, we need all x's to be connected with all y's and we gonna take maximum y such that x meets sufficient conditions.Couldn't proceed further.
 » 5 months ago, # | ← Rev. 2 →   +5 how will you know who will be included in the list of 100 random people who will receive t-shirts?
•  » » 5 months ago, # ^ |   0 +1
•  » » » 5 months ago, # ^ |   +4 they wrote to me "after checking the cheaters, we will publish the script and the list" :)
 » 5 months ago, # |   +3 I'm so nervous that my D will get TLE. I just use something like bruteforce....
•  » » 5 months ago, # ^ |   +4 FML, TLE on 112
 » 5 months ago, # |   -33 why no bugaboo :(
 » 5 months ago, # |   +220 Fine, finally a reading comprehension round. Spoilerread E as "exist a continuous segment of length k with all lights turned on", and the sample explanation doesn't contain anything about this.
•  » » 5 months ago, # ^ |   +10 Same...
•  » » 5 months ago, # ^ |   +15 SAME
•  » » 5 months ago, # ^ |   0 +1
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Same, until the end of the contest (until reading this comment) :/
•  » » 5 months ago, # ^ |   +17 same (I spent at least 20min reading C)
•  » » 5 months ago, # ^ |   +3 I didn't realize it until I read this comment...
•  » » 5 months ago, # ^ |   +10 Same >:(
•  » » 5 months ago, # ^ |   0 Same.
•  » » 5 months ago, # ^ |   0 Same...
 » 5 months ago, # |   +7 I made an assertion statement in C to check if the first character is 1 or not, I got a runtime error! I can't believe it has more than 3k AC.
•  » » 5 months ago, # ^ |   +3 Submission with assert. Guess you have RTE somewhere else.
 » 5 months ago, # |   +40 how did testers approve C , the language was pathetic , wasn't able to get what the task meant till end...
 » 5 months ago, # |   0 Lol A was harder for me than B, For A i took 2 attempts and 1 hr and B only 30 mins in 1 attempt, didn't have enough time to solve C.anyways it was a good round xD...
•  » » 5 months ago, # ^ |   0 I passed pretests on B and C but couldn't get A fml:/
•  » » 5 months ago, # ^ |   0 opposite for me...did A in some time (17 mins) and submitted B literally at the last minute
 » 5 months ago, # |   +1 Wait when you changed n upper bound to 1000 for B? I always think it should be 2000 and the requirement is 5000... i spent like 1 hour thinking about how to get better than a 3n solution but the question description :(
 » 5 months ago, # |   0 what is wrong in my submission of C link
 » 5 months ago, # |   0 OOf just lacked a tiny bit of time for D lul
•  » » 5 months ago, # ^ |   0 Tried Bruteforcing got TLE Tried Bitmasking + Bruteforcing got TLE Tried Further bitmasking + Bruteforcing contest finishedOH NO
 » 5 months ago, # |   0 Why the next contest is after 2 weeks (⋟﹏⋞)
•  » » 5 months ago, # ^ |   0 +1. Frequency of codeforces contest has decreased compared to month back.
•  » » 5 months ago, # ^ |   0 They will probably put an educational round in between. It happened earlier that I thought the next contest is after 2 weeks and didnt check codeforces for 2 weeks. After 2 weeks, I saw an educatioal round was announced 5 days before happening 1 week later.My point is keep checking the contest schedule each day. Something might get added.
 » 5 months ago, # | ← Rev. 3 →   +2 Randomised solution for D:Randomly take a friend and assume it to be the part of the final subset now compare all other friends with this subset and use submask dp in the end to find maximum size subset. I took 25 random friends.
 » 5 months ago, # |   +20 why so bad...
 » 5 months ago, # | ← Rev. 3 →   +341 Does problem C's initial statement form a proper problem? Before the sentence 'then the sequence of items should always remain increasing in lexicographical order' was added, I couldn't found the operations like121.1are invalid from the initial statement.The announcement of the addition of previous sentence was so late that it's hard to say that the impact of this problem was little.(actually, I've use so long time to debug my code which was doing something like the previous operation)Hope for the appropriate response.
•  » » 5 months ago, # ^ |   +274 It's not only "hard to read" or "hard to understand" but it's broken as a problem. I can't say it's enough to be unrated but should take into account whether making this round unrated or not. MikeMirzayanov Vladik
•  » » » 5 months ago, # ^ |   +262 I think this mistake is enough to be unrated.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +147 I agree. Making such a significant change to the problem statement 40 minutes into the contest is unacceptable. This contest should be unrated.
•  » » » » » 5 months ago, # ^ |   +8 Agree "take into account whether making this round unrated or not".For me , I wasted at least one hour in C . And have no time to read E.
•  » » » » » » 5 months ago, # ^ |   0 I totally agree with you !
•  » » » » » » » 5 months ago, # ^ |   +45 Did you forget to log out your clone to comment? This is just hilarious.
•  » » 5 months ago, # ^ |   +74 I agree, the problem basically changed halfway through. I don't think this should happen.
•  » » » 5 months ago, # ^ |   +99 yes, the addition was not just the description. it fundamentally changed the problem.
•  » » 5 months ago, # ^ |   +63 We are sorry for this issue in the statement. None of the testers and authors noticed that the formal definition of a multi-level list was not exactly correct. The statement was corrected and an announcement was made as soon as the issue was noticed. Fortunately, most of the participants followed the common sense about what a multi-level list is and authors meant exactly that.By the way, I think when a high-rated participant finds something strange in a problem, like statement does not match usual definitions, or some other mistake, they should report that to the authors (in any contest, not only here). It is much more probable that there is a mistake or that you misunderstood something rather than authors deliberately made a trap without mentioning it explicitly. Reporting that will help authors and save your time.
•  » » » 5 months ago, # ^ |   0 Will the round still be rated?
•  » » » » 5 months ago, # ^ |   +65 Yes.
•  » » » » » 5 months ago, # ^ |   0 Nikolay, Is that somehow possible to retest all solutions for problem A in this contest? What I've noticed is that there are 5 lists of participants who got TL on this problem, whereas only 1 list of people passed system tests, and all of them had linear algorithm, but according to the editorial quadratic solution should pass. Thanks in advance
•  » » » » » 5 months ago, # ^ |   +18 Lost t-shirt by this shit problem, also lots of rating.
•  » » » 5 months ago, # ^ |   +49 so, you mean that the problems are still remain correctly even if it is mathematicaly wrong but can perdict it from some kind of fuzzy "common sense"?I don't so much care about whethere it is unrated or not, but the dealing with this issue to say "if youre high rated and found it strange, report it" is a question mark(as statement makes a sense without the order constraint, I have no idea but somewhere of my code is wrong.)Problems should have been established only by the problem itself. not depening on something lile "common sense".I hope the future rounds wont repeat and I can help it by reporting.I have one nice idea for preventing: let's totally get rid of STORIES :)
•  » » » 5 months ago, # ^ |   +17 I don't understand — there are so many problems — Anton coordinated ones especially, where the "definition" is the trick to the problem. By putting the pressure on these high rated participants, you are effectively scapegoating them to do the work that authors should have done — listen to tester feedback.Oh, and, "none of the testers noticed..." is just shifty phrasing. Testers complained about the statement of C saying it was confusing. You know that.I did not take this contest, but I am equally outraged about the way this matter was handled.
•  » » 5 months ago, # ^ |   0 I made the same mistake ,and I wasted at least one hour in it and get four WA :<
•  » » 5 months ago, # ^ |   +30 Does problem C's initial statement form a proper problem? Before I got AC using the decimal numeral system, I couldn't found the operations like123456789AB are invalid from the initial statement.It was so late that it's hard to say that the impact of this problem was little.(actually, I've use so long time to debug my code which was doing something like the previous operation)Hope for the appropriate response.
•  » » » 5 months ago, # ^ |   0 This is different. Using base 10 is an underlying assumption in all problems. The list being lexicographically sorted, however, isn't so clear. Also, the statement was editted 40 minutes into the contest to correct the mistake.
 » 5 months ago, # | ← Rev. 3 →   0 I take my words back.
 » 5 months ago, # |   0 who else got TLE in A? :d I think for big number of m and "1111...110111....1" this kind of solution was the main reason right?
 » 5 months ago, # |   +19 Can anyone explain how to solve E?
 » 5 months ago, # | ← Rev. 2 →   0 Can someone please point out my mistake in today's C?https://codeforces.com/contest/1523/problem/CMy own testcases passed.. and I feel pretty sure I have done right. Please help.
 » 5 months ago, # |   +81 The problem statement of C is unreadable.
 » 5 months ago, # | ← Rev. 4 →   -32 [. .
•  » » 5 months ago, # ^ |   +1 omg, that must feel bad ;)
•  » » 5 months ago, # ^ |   0 omg!rating predictor is showing -213 OMFG
•  » » » 5 months ago, # ^ |   +2 Yeah , My bad luck :(
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 So basically you participated but decided not to submit because didn't want to ruin you rating and as a result you did exactly thatWhat irony
•  » » » 5 months ago, # ^ |   0 I didn't even wanted to participate ( the biggest reason being I was busy in upsolving today's ABC's E) I started contest after a good amount of time , But that happened . leave it , I think nothing could be done .
 » 5 months ago, # |   0 I see a lot of specialists there, including me, failing sys tests in A lol guys.
 » 5 months ago, # | ← Rev. 3 →   0
 » 5 months ago, # |   +3 I resolved the bug in my solution to problem C, but only 12 seconds were left. I couldn't submit it. I wish I had 1 more minute.....This is so saddening.
 » 5 months ago, # |   +95 Didn't unterstand E correctly, FSTed in both C and D, bad day for me :(
•  » » 5 months ago, # ^ |   +81 Not your fault, this round is shit.
•  » » 5 months ago, # ^ |   +57 If you wonder how is it possible to FST in C, here's the answer:I stored the input in an array $a$.The array $a$ is an array of integers in my default source, but when I solve problem A, I changed it to char. And when doing problem C, I forgot to change it back:(And it passed pretests:(
•  » » » 5 months ago, # ^ |   +34 Imagine writing all problems in the same file, lol.
 » 5 months ago, # |   +25 can anyone of the testers , problem setters tell what was going through their mind when they approved the language of problem C , complete nuisance it was
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 You don't know the dance and says floor is tilted (naach na jane aangan tedha)
 » 5 months ago, # |   +22 Weak pretests on D!
 » 5 months ago, # |   +1 Asking for hack: my submission for DMy solution is totally wrong but I can't hack it.
•  » » 5 months ago, # ^ |   +6 It was interesting!
•  » » » 5 months ago, # ^ |   +8 Your hack is amazing!By the way, I've written another wrong solution which passed all the test cases.You may hack it here :)
 » 5 months ago, # |   -33 In problem A, I think it is immoral to write the constraints as such t <= 1E3 n <= 1E3 . . . The sum of n in all testcase does not exceed 1E4 When I read the top 2 lines I would think the intended solution to be O(n), while an O(n^2) solution would also pass.
•  » » 5 months ago, # ^ |   -8 I dont't get it, why this comment is getting downvotes
 » 5 months ago, # |   +306 I think problem C is different problem before and after the problem statement is changed.before changing the problem statement,1 1 2 2 1 3 3is valid sequence(because you can make a list like below: 1 1.1 1.2 2 2.1 3 1.3 ),but after changing the problem statement,this is invalid sequence.I was very sad about this change.
•  » » 5 months ago, # ^ |   +113 I've chosen the solution same as yours and get "Wrong answer on test 2."As allowing the "non lexicographical order" operations just extend the valid operations and the fact that "all testcases has solution", our solution have give a answer.but the verdict was "Wrong Answer" so I guess the output checker was checking is it lexicographical order or not.If the output checker was taking into consideration but forgotten to write in the statement, it's a so so FATAL MISS!!!!
•  » » 5 months ago, # ^ |   +21 not gonna lie, I saw the first version of the problem. Didn't understand it at all. I only understood it from the image. I guess the image actually has better explanation that the statement its self Lol. But yeah, that is really sad :c
•  » » 5 months ago, # ^ |   0 You can provide solution with test case : 10 1 1 1 2 2 1 2 3 3 3 is it a correct test case ?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +18 with my (before the changing problem statement) solution (117891713 ), 1 1.1 1.1.1 2 1.2 1.1.1.1 1.1.2 3 1.3 1.1.3 is provided.(after changing, this sequence is invalid.)You can solve (before the changing) this problem by listing all items that can appear next.
•  » » 5 months ago, # ^ |   +19 I solved problems F and G after contest, and both were interesting. I also like problems D and E. Thanks for preparing this round.
 » 5 months ago, # |   +12 In problem B, I realized that I needed to do 6 operations for a pair, but I multiplied 6 by 1000, although there are only 500 pairs( So I came to a more complex solution after an hour.Maybe someone will be interested https://codeforces.com/contest/1523/submission/117914942In this solution I am doing 14 operations for every four of numbers. If the number of numbers is not divisible by 4, then I do 6 operations for the remaining pair.
•  » » 5 months ago, # ^ |   +8 I'M SO STUPID! 14 for four numbers in my solution is bigger, than 12 for two pairs!!!Well, at least I could immediately understand it. Here is the normal solution https://codeforces.com/contest/1523/submission/117920818
 » 5 months ago, # |   0 Hey, anyone else did not pass Problem A because they used Python??
•  » » 5 months ago, # ^ |   0 Yo bro me too, python is crap
•  » » » 5 months ago, # ^ |   0 I think I will just have to stop using it. This is the second time this happened to me. I am sad cuz its just so comfortable to work with strings in python...
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 I used pypy3 and passed A (although I was scared that it wouldn't!)
•  » » » 5 months ago, # ^ |   0 If anything, with very few exceptions, Python's performance is more than enough for div2 participants
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 I used Python 3 for problem A, B, and C with no issues. Maybe you just had a bad implementation.
•  » » » 5 months ago, # ^ |   0 My implementation is crap, but it should have the same complexity as described in editorial. I looked at your impl. and it seems more effective than the editorial solution
 » 5 months ago, # |   +14 What was the point on the weak pretests for A?
•  » » 5 months ago, # ^ |   +1 What is the point of having 37 pretests for D and still I fsted ?
 » 5 months ago, # |   +7 As a contestant, I want a t-shirt :v .. That T-shirt is so beautiful.. <3
 » 5 months ago, # |   0 Operation can only be applied if the list does not contain two identical items afterwards Can someone explain what this statement means with respect to problem C ?
•  » » 5 months ago, # ^ |   +1 It means you can't have duplicate items in the list, for example [1, 1.1, 1.1, 1.2] is not a valid nested list.
•  » » 5 months ago, # ^ |   +3 This statement on tallying it with the sample explanation left me puzzled and blank!
•  » » » 5 months ago, # ^ |   0 Yes! Me too. This statement completely threw me off guard. I wish they had not kept such ambiguous statements and included more samples in the problem statement.
 » 5 months ago, # | ← Rev. 2 →   +3 The last second I found I just use rand()%n+1` to select a person randomly on problem D. That's why I got wrong answer 5 times on pretest 36. I will never forget this trap. :(
•  » » 5 months ago, # ^ |   +13 RAND_MAX is 32767 on OJ.But it is 2147483647 on my laptop.QAQ
•  » » » 5 months ago, # ^ |   +3 go read this: https://codeforces.com/blog/entry/61587
•  » » » » 5 months ago, # ^ |   +1 Thanks
 » 5 months ago, # |   +9 such a very good contest, many thanks for deltix !!!
•  » » 5 months ago, # ^ |   0 how exactly :0
 » 5 months ago, # | ← Rev. 2 →   +3 This round was as good as the problem statement of C:)
•  » » 5 months ago, # ^ |   +1 C was more like a headache T_T.
 » 5 months ago, # |   0 chert
 » 5 months ago, # |   +116 I misread E that he continues turning lights on until K consecutive lights are on.Explanation of the example matches it :(I think it is way harder than the original problem. Is there an easy way to the problem that I understood?
•  » » 5 months ago, # ^ |   +10 I'm not sure if you wanted a subquadratic solution, but I think you can do it in $O(n^2)$ with the following lemma.Lemma: Let $X$ be a random variable that takes non-negative integer values. Then $\displaystyle E[X] = \sum_{i = 1}^{\infty} Pr[X \ge i]$.From the lemma, it is sufficient to find $\displaystyle \sum_{i=0}^{\infty} Pr[\text{There aren't k lights in a row after i steps}]$. This can be done with DP in $O(n^2)$ by finding the number of ways to pick $i$ lights from the first $j$ such that no $k$ of them are consecutive, for all $i,j$. Maybe there is some way to optimize this, idk.
 » 5 months ago, # | ← Rev. 2 →   +7 Finally a good round after back to back bad rounds for me.I do admit even I didn't like the problem statement of C. But that table at the bottom helped me a lot. :)
 » 5 months ago, # |   +63 abc were the most rubish problems I had ever seen
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 A and C was supposed to be non existent due to their bad quality. But I find B not that bad for a Div 2 A or an easy Div 2 B.
•  » » » 5 months ago, # ^ |   +10 Idk but I felt C statement was not clear enough ,add that midway change,I solved a whole of different version of it until I reread statement .Maybe I had to work upon my English:(
 » 5 months ago, # |   0
 » 5 months ago, # |   +16 who else understood the statement for C because of the image?
 » 5 months ago, # |   +9 Well, I was about to get purple, until my D FSTed. Do you guys know how it feels when you are about to purple for the first time and you end up losing rating instead cuz of FST ! :sob: :sob: :sob:
 » 5 months ago, # |   +102
 » 5 months ago, # | ← Rev. 2 →   0 after triggering it all items in the list were replaced by a single number: the last number originally written in the item number. f***, after looking at the test data I realized that I solved a completely different problem for C, I thought that the list was replaced by the last number i.e the digit written on the list. Also the sample test data contained all a[i]<=9. The problem statement just ruined it man. The writer should provide a concrete example of what he wants to convey.
 » 5 months ago, # | ← Rev. 2 →   +8 The problem C itself was not badBut the statement was crappy and if none of the testers noticed it, they did crappy job as testers.I don't know what exactly is tested during preparation, but clarity of the problems statements should certainly be one of such things
 » 5 months ago, # |   -7 About problem C. I read the problem sentences before the announcement and thought the answer is not always increasing in lexicographical order. So I was confused when I got the announcement. But I trust that the writers will not change the sentence in such a way that what the problem means will change and therefore I searched for what was wrong with my thought. Eventually, there prove to be nothing wrong with my thought (as there are mentions in other comments). Would I have been better not trusting the writer? I'm worried whether I can trust the writers in future contests :(
 » 5 months ago, # |   +17 What a shame, there are 15 testers while none of them notice the problem in C
 » 5 months ago, # |   +61 To not keep you waiting, the ratings updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
•  » » 5 months ago, # ^ |   +10 I just hope, i get a +1 after that :}
•  » » » 5 months ago, # ^ |   +24 Come true!!!)
•  » » » » 5 months ago, # ^ |   +8 yes ;)
•  » » » 5 months ago, # ^ |   +13 Congrats! :)
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +13 Thanks :}, congrats to you too on becoming master
•  » » 5 months ago, # ^ |   +76 This round should be unrated. The statement of problem C changed during the contest and many contestants were affected.
•  » » » 5 months ago, # ^ |   +81 I highly appreciate your Honesty , Even after becoming LGM for first time , you are saying that the round should be unrated . BTW congrats for becoming LGM.
•  » » » 5 months ago, # ^ |   -11 yeah it should be, I think by the time I reached C, the problem statements were already changed, so I didn't notice that.
•  » » » 5 months ago, # ^ |   -28 Not only for the statement of problem C , but also the weak pretests on A and D.
•  » » » 5 months ago, # ^ |   -7 i waste my 1 hours to solve C problems..
•  » » 5 months ago, # ^ |   +28 want to take a glance at the issues on C.https://codeforces.com/blog/entry/90915?#comment-797718
 » 5 months ago, #