By PikMike, history, 4 weeks ago, translation, ,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Attention Codeforces!

Calling on all tech disruptors, data specialists and computer science pioneers.
We are offering fully-funded international scholarships for exceptional tech specialists from around the world. Accelerate your career by becoming an industry expert capable of making key data-driven decisions that add value and drive innovation within tech industries.

Harbour.Space University has partnered with SCG, a leading business conglomerate in the ASEAN region, to offer exceptional tech specialists the opportunity to work and study in two of the most dynamic and vibrant cities in the world. Join our progressive two-year program based in Bangkok, with 6 of the 24 months in Barcelona, to develop the international mindset needed to accelerate your career and redefine how data drives the businesses of the future.

Tuition fee:

2 years | €45,800

Education:

3 hours of study per day | 15h per week

Work Experience:

4 hours of internship per day at SCG | 20h per week

Living Allowance:

€16,800 euros | €700 per month living allowance

APPLY HERE→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 7 182
2 kmjp 7 216
3 socketnaut 7 218
4 KrK 7 225
5 ivan100sic 7 244
5 pwild 7 244

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Aaman007 39:-10
2 liouzhou_101 59:-58
3 dzhiblavi 15
4 Rian_5900 31:-40
5 Fyodor 10:-2
278 successful hacks and 501 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A rahulDugar 0:00
B Siberian 0:02
C ZwariowanyMarcin 0:03
D LJC00118 0:16
E jjang36524 0:23
F TripleM5da 0:19
G black_horse2014 0:19

UPD: Editorial is out

• +204

 » 4 weeks ago, # | ← Rev. 2 →   +26 Hope to become expert in this contest......
•  » » 4 weeks ago, # ^ |   +4 If you'll do so you will make another record on codeforces .Best Of Luck .
•  » » » 4 weeks ago, # ^ |   +8 seems he is going to do so
 » 4 weeks ago, # |   +36 Strange that there's only one comment in 14 hours. Anyway, it's a PikMike contest so I'm excited. Hope I can finally get candidate master lmao.
 » 4 weeks ago, # |   -37 hope to become specialist in this contest.
•  » » 4 weeks ago, # ^ |   -16 hope to become unranked in this contest)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +39 hope to become headquarters after the round.
•  » » » » 4 weeks ago, # ^ |   +57 Hope to become Batman... after this round...
•  » » » 4 weeks ago, # ^ |   +189 Hope to find Girlfriend after the round.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +24 Make your handle GF_in_Three_Months
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Me too, I made a bet with my friend and I should find a girlfriend in the next 40 days. ;)
•  » » » » » 4 weeks ago, # ^ |   +62 It's fair easy for you. Just pass her some solutions :P
•  » » » » » » 4 weeks ago, # ^ |   +16 And marry her if she could hack them.
•  » » 4 weeks ago, # ^ |   +5 Dammit I'm only expert.
 » 4 weeks ago, # |   0 Hope to become 1500+ this contest.
 » 4 weeks ago, # |   +21 Good Contest.
 » 4 weeks ago, # |   0 Were Segment Trees necessary in D? I had to do some maximum queries on the monster array, was too scared to try my solution without the tree.
•  » » 4 weeks ago, # ^ |   +7 Well, i did a sparse table
•  » » » 4 weeks ago, # ^ |   +5 Oh yeah, right! Well thought!
•  » » 4 weeks ago, # ^ |   +30 we can take the suffix max after sort the hero on the basis of its power and then take lower_bound.
•  » » » 4 weeks ago, # ^ |   +13 I've done that. I said maximum queries on the monster array
•  » » 4 weeks ago, # ^ |   +3 Not necessary, Although I thought about Segment Trees first
•  » » 4 weeks ago, # ^ |   +1 Overkill segment trees was not needed at all.
•  » » 4 weeks ago, # ^ |   +3 no
•  » » 4 weeks ago, # ^ |   0 I think if you sort heroes' by power, you can calculate the maximum endurance for each suffix in O(m)
•  » » » 4 weeks ago, # ^ |   0 [D][IS][Greedy] [IS] [RIGHT]
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 I did it without Segment tree. Solution. Just sort, binary search and array for suffix maximum endurance
•  » » 4 weeks ago, # ^ |   +3 Not at all. Just sort the heroes by endurance O(MlogM), than in O(N+M) build an array that stored at element i what is the maximum power between heroes with at least i endurance. Then simply loop the monsters array O(N) and with a single lookup it can be found if the current monster could be beaten up during the same day or it is needed a new day
•  » » 4 weeks ago, # ^ |   +3 I did not use a segment tree or sparse table for this problem. You can check my solution: http://codeforces.com/contest/1257/submission/64838220
 » 4 weeks ago, # |   +6 How to solve C?_
•  » » 4 weeks ago, # ^ |   +26 The answer is the minimal distance between two equal elements.
•  » » » 4 weeks ago, # ^ |   +6 why
•  » » » » 4 weeks ago, # ^ |   +3 If you check the subarray that is the answer to the task, you will see that it's first and last elements are equal (because it is the most optimal). And all the elements between them are all different.Sorry for my poor (maybe) English.
•  » » » » 4 weeks ago, # ^ |   +9 If you look at two equal elements in an array then the only case where it is not dominant is if there is at least another pair of two inside. The equal elements that have the minimum difference between them cannot contain another pair because that would contradict that the elements we found have the minimal difference.
•  » » » » 4 weeks ago, # ^ |   0 because when you take two elements with minimum distance then between these two other element appear at most one.1231 if there is repeated value between two 1 then distance between 1 can't be minimum.
•  » » » » 4 weeks ago, # ^ |   0 Consider you have two suquences1 4 3 2 4 1Now here, we can choose the first 2nd and last 2nd element in a segment. That will form the minimum.and other,1 4 3 3 4 1Now here, if we choose the same indexes as an upper example, it would be wrong. Because we can still minimize the segment to {3,3}. So we can conclude that all we needed to do is minimizing the difference between equal elements. Hope you understood.
•  » » » » » 4 weeks ago, # ^ |   0 why result is 4, 5, 4 for 4 1 2 4 5 4 3 2 1 and not 4 4 for example
•  » » » » » » 4 weeks ago, # ^ |   0 Because choosing a subarray should be contiguous.
•  » » » » » » » 4 weeks ago, # ^ |   0 I see now :) thanks
•  » » » » » » 4 weeks ago, # ^ |   0 ****The subarray of a is a contiguous part of the array a, i. e. the array ai,ai+1,…,aj for some 1≤i≤j≤n.****you missed this line.
•  » » » 4 weeks ago, # ^ |   0 Wow, I feel dumb now jury-rigging a two-way multimap keeping track of element counts and number of elements with the maximum count
•  » » 4 weeks ago, # ^ |   +5 you have to find minimum difference between two repeated value. save the last position you get for each value and when you get it again take difference and update position of last appearence. then take minimum of all diference.
•  » » 4 weeks ago, # ^ |   +5 We note that, there is a answer if and only if some number is repeated otherwise ans is -1.The shortest such subarray will be |start of that number(x) — another instance of that number(x)| so just count how many repeated numbers are there and print the minimum distance b/w them
•  » » 4 weeks ago, # ^ |   0 Implementation works: link
•  » » 4 weeks ago, # ^ |   0 I used two pointers which I later realized to be difficult to solve that problem.
 » 4 weeks ago, # |   +3 In question D, codeforces giving different output than other platforms like hackerrank, onlinegdb for the same code. Output on codeforces is coming as 0 and -1 for the 1st test case but it is correct on other platforms. Does someone know why is it so
•  » » 4 weeks ago, # ^ |   +3 It's an undefined behavior. For example if you donn't fill a local array explicitly, it doesn't have to be filled with zeros, it may be filled with anything depending of compiler.
•  » » 4 weeks ago, # ^ |   +5 See diagnostics in your submission: "Error: attempt to dereference a past-the-end iterator." I had a similar solution with the same bug. That lower_bound returns the end of the map when there's no heroes with energy day or more left.
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot bro. code worked after handling this case
 » 4 weeks ago, # |   -10 Seems not sorted by difficulty...RIP my rating.
•  » » 4 weeks ago, # ^ |   +12 It seemed very sorted to me. I won't say they were easy though, I might get hacked when I least expect it
 » 4 weeks ago, # | ← Rev. 4 →   +23 F is just btuteforce, LOL. 100e9 in 2 seconds))UPD 1: Hacked.UPD 2: Added set, Accepted.UPD 3: Passed final tests in 2.5 seconds.UPD 4: More stable program with a run time 1.9 seconds: Link.
•  » » 4 weeks ago, # ^ |   0 Can you elaborate a little more please?
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   -19 Just implement the dumb checking described in the statement with some optimizations (pragmas, shuffle, set and popcount is enough). Code.
•  » » » » 4 weeks ago, # ^ |   +19 Not enough anymore xd
•  » » » » » 4 weeks ago, # ^ |   0 Now enough)
•  » » » » » » 4 weeks ago, # ^ |   0 how does adding set help?
•  » » » » » » 4 weeks ago, # ^ |   +1 Still not enough xD
•  » » » » 4 weeks ago, # ^ |   0 Kindly please tell how does adding set help in increasing speed?
•  » » 4 weeks ago, # ^ |   +8 Bruteforce way can be Hacked, test cases are weak.
•  » » » 4 weeks ago, # ^ |   0 Try to hack my solution)
 » 4 weeks ago, # |   0 Good test cases on F, I tried my best to make random solutions pass and failed.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -68 You are an idiot.
 » 4 weeks ago, # |   +19 How to solve D???
•  » » 4 weeks ago, # ^ |   +6 Greedy.Every day,choose a hero who can beat most monsters.
•  » » » 4 weeks ago, # ^ |   0 Can anyone please elaborate on this? How to choose the hero who can beat most monsters? I did something in my solution but I find that to be too messy.
•  » » » » 4 weeks ago, # ^ |   0 Binary search on the hero. Solution
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 I saw people's submissions where they were obtaining the suffix maximums over the max. powers needed for a fixed endurance value. I find that idea to be much less on code. I'd like to know about that idea as I am still not able to think about it.UPD: I have mentioned the idea in one of my comments below.
•  » » » » 4 weeks ago, # ^ |   +4 Just sort the {power, endurance} array. Then start with the first monster and check maximum power needed to defeat the dragon(Binary search), also I have maintained a suffix array that will store maximum endurance. If we can defeat the dragon then try to take one more dragon on the same day otherwise start with a new day. Link to my Solution
•  » » 4 weeks ago, # ^ |   0 I implemented O(m*n), and though in worst case scenario there is no way it passes TL, it somehow got accepted. I sorted heroes in descending of their stamina, and for each hero in this order I tried to find maximum of monsters he can beat if he enters now (i.e. iterate mosters one by one and increase counter if monster is weaker and hero's stamina is not exceeded). I break cycles if I find a hero with lower stamina than my current maximum.
•  » » » 4 weeks ago, # ^ |   0 We still are in the hacking phase, someone might try to break your code so it gives TLE, hopefully not!
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 My approach is, at first I sort all the heroes in basis on their power and then endurance in decreasing order. Then I try to find out maximum power for every endurance. It always proves that endurance[i]>=endurance[i+1]. Finally, at every step, I just try to pick the longest endurance(using binary search) which can able to kill all the monsters on that range.(I use segment to find out the maximum monster value on that range). If there is any monster whose value is greater than the maximum hero's power then the answer is -1.My solution -> https://codeforces.com/contest/1257/submission/64846739
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +27 I finally managed to understand the easy way to solve the problem by going through people's submissions. I'll try to explain. First, if we are currently at the $i$th monster, we have to choose a hero that can kill the largest no. of monsters. The only tricky thing is choosing that hero. Let $cnt$ denote the current no. of monsters that we can kill from the $i$th position. Initially, $cnt = 0$. Now, $cnt$ can be extended to $1$ iff there exists some hero whose endurance $\ge 1$ and the power is more than the power of the $i$th monster. Using this logic, we'll be extending $cnt$ as much as we can. To extend $cnt$ by $1$, we have to check to see whether there exists a hero whose endurance is $\ge cnt + 1$ and whose power is $\ge$ power of all monsters within the range $[i, i+cnt]$. If there does exist one, we can extend $cnt$ to $cnt + 1$.To check this thing, we can have an array we store the maximum power of a hero whose endurance is $\ge i$. This can be computed by taking suffix maximums on an array where the $i$th element is the maximum power of a hero whose endurance is $i$. Also, since we are always extending $cnt$ by $1$, we can instead keep a running maximum of monster's powers instead of using a data structure to obtain the maximum within that range.Code
•  » » » 4 weeks ago, # ^ |   0 Hey roll_no_1, I did a similar thing as well, but in the other direction, so just putting my strategy here as wellInvariant: If there is a hero with more power and more endurance, he is always better than anyone with both of these lower.Steps: Create an array that has the best weapon for each endurance -> update bestHero[endurance] = max(bestHero[endurance], power) and then place the suffix maxThis step would mean that at every value of endurance, the best value of power that is greater than or equal to the power for the range having more endurance is taken. (Greedy choice)Move from the back and kill the current monster, if you can't kill the current monster, along with the suffix, add 1, else, keep expanding the array backwards updating the maximum.Overall an order of O(n+m)
•  » » » 4 weeks ago, # ^ |   0 I did solve with the same concept but with binary searching. keeping a max suffix array is much more cleaner. Thanks for sharing, I learnt something cool.
•  » » 4 weeks ago, # ^ |   0 You can solve the problem without using segment tree or binary search. http://codeforces.com/contest/1257/submission/64838220 Just a map and lower_bound is required
•  » » 4 weeks ago, # ^ |   0 I did a greedy solution. 64832445Explanation — sort heros according to endurance and allocate each monster a hero starting from max endurance, than start making maximum group possible.
 » 4 weeks ago, # | ← Rev. 3 →   0 Given the huge TL, I imagine my solution for G is off, but is it something like finding number of solutions to $\sum_{i=1}^d x_i = k$, where $d$ is the number of distinct prime divisors and $k$ is the minimum power of one of the prime divisors?
•  » » 4 weeks ago, # ^ |   0 k is actually floor(n/2).
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Upon further thought, it makes sense that it shouldn't be the minimum power of the prime divisors, but it's not at all clear to me why floor(n/2) encodes the proper information. Can you elaborate?EDIT: Just tried to verify this on the samples. Unless I'm misunderstanding what you mean by n/2, this doesn't seem to work.EDIT2: My implementation was wrong, tried to use stars and bars where I couldn't. My bad.
•  » » » » 4 weeks ago, # ^ |   +33 It's theorem 1 in this link: https://pure.tue.nl/ws/files/4373475/597494.pdf
•  » » » » 4 weeks ago, # ^ |   +22 n is number of prime divisors given in the input.Lets say (p1,p2,..,pd) are the distinct prime factors and (a1,a2,...,ad) are the powers of prime factor. Now you can represent these tuple of powers (a1,a2,..,ad) for each divisor as a partially ordered set (poset).The goal is to find the longest antichain which is the width of the poset.You can notice that sum(ai) represents a distinct level.Lets say the number is 2^4*3^2.(4,2) represents level 6. (sum=6)(4,1), (3,2) represents level 5. (sum=5)(3,1), (4,0), (3,1), (2,2) represent level 4. (sum=4) and so on.Its kind of intuitive that the poset is symmetric about mid level (level=n/2) and that should have the maximum cardinality. I dont know a proof.Thus the answer to the problem is the number of solutions such that sum(ai) = floor(n/2).This can be solved by fft.My submission
•  » » » » » 4 weeks ago, # ^ |   0 I see; thanks, that explanation makes a lot of sense!
 » 4 weeks ago, # |   +2 Can E be solved using this idea: 1) Iterate from i=0 to n. i is the last problem of first-person.2) Then do a ternary search for getting the answer among 2nd and 3rd person.Is this idea correct?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 isnt binary search enough? I did not code it, I am a binary search code noob
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I don't think this solution is correct. As the cost of distribution between 2nd and 3rd is not necessarily unimodal. ExampleLet, the initial owners of problems are: 2 3 2 3 2 3. And you have fixed that coder no 1 will take no problem (as you are iterating on number of problems taken by 1). Then coder no 3 will definitely take some suffix (maybe empty). Say suf[i] = cost that coder 3 takes problem no i...n. Then suf[] = 3 2 3 2 3 2 3. suf[1] = 3 as coder 2 will give all his problems to coder 3. suf[3] = 3 as coder 2 will give problem no 3 and 5 to coder 3, coder 3 will give problem no 2 to coder 2.But it can be done using segment tree.
 » 4 weeks ago, # |   +152 I'm not sure if it was intentional, but E could be solved by ordering the three lists, concatenating them, and then running a very well known LIS (Longest Increasing Subsequence) algorithm.
•  » » 4 weeks ago, # ^ |   +34 The answer was simply (K1+K2+K3) — N, where N is the length of the longest increasing subsequence.
•  » » 4 weeks ago, # ^ |   0 Can u help me prove it why is it LIS? The idea intuitively seems correct.
•  » » » 4 weeks ago, # ^ |   +15 LIS size is the most objects you can remain unchange
•  » » 4 weeks ago, # ^ |   0 But why it's working?
•  » » » 4 weeks ago, # ^ |   +1 Sort each array independently. Given this LIS size, you know maximum amount that are in place. The goal is to get whole array sorted, and each operation increases that number by 1 (place the element out of order to its position), so we will need that amount of operations. This is not a formal proof but an intuition of how I see it
•  » » » 4 weeks ago, # ^ |   +3 It's actually exactly COCI lista
•  » » 4 weeks ago, # ^ |   +17 This is beyond my knowledge. Never knew LIS would be this powerful. This not only works for 3 arrays. The intuition is you want to maximize the amount of element to stay in its segment. What an elegant solution. to restore the steps of the answer, youll simply make the LIS related elements stay and move the rest greedily.
•  » » » 4 weeks ago, # ^ |   0 It seems so obvious and easy once we understand the idea.
•  » » 4 weeks ago, # ^ |   +59 It wasn't intended (model solution uses some math and prefix sums), but the solution is really cool nevertheless!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Amazing solution!!this is a good source for people who dont know LIS to learn how it works.
 » 4 weeks ago, # |   +9 How to solve G?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +17 Hint: It turns out 'finding' the subset is easy but 'counting' it is hard. Can you prove a certain subset must be maximal?Decompose \forall x \in S as \prod_{i} x_i ^ e_i. Observe that x could be partitioned into equivalent classes according to \sum(e_i), and by simple combinatronics the reader may prove that \sum(e_i) = n/2 is one of the class with the largest size. Hint: OK, can you count it?Rewrite all primes as generating functions: When there is only 1 prime (with e_i copies of it), represent it as a generating function of [1]^e_i, i.e. the size of the equivalent classes.When there are more than one primes, simply divide the workload into half and solve recursively (DnK DP), and convolute the final results with NTT.
 » 4 weeks ago, # |   +33 Why has CF started giving T test cases for every problem like codechef does?
•  » » 4 weeks ago, # ^ |   0 Now it's easy for us to run all the sample cases at once
•  » » » 4 weeks ago, # ^ |   +37 Yeah, but then i need to care about resetting global variables and arrays when problem has T test cases and it increases my chances of making a mistake.
•  » » » » 4 weeks ago, # ^ |   -14 Wouldn't that be caught on the sample cases?
•  » » » » » 4 weeks ago, # ^ |   +19 Well most of the times it doesn't.
•  » » » » 4 weeks ago, # ^ |   +50 You don't have to use global variables. They are evil.
•  » » 4 weeks ago, # ^ |   +71 It's a common solution for ERs (and, it seems, div3) because it's too much burden for the system to check 20-30 tests (and 30 tests are not enough sometimes) per each submit especially on tasks like A, B, C.
•  » » » 4 weeks ago, # ^ |   0 If this is the case I highly agree with you.
•  » » 4 weeks ago, # ^ |   +29 I highly prefer it this way. You get to have much better test coverage without insane queues.
 » 4 weeks ago, # |   +80 Good Contest.
 » 4 weeks ago, # |   0 How to solve problem C?
•  » » 4 weeks ago, # ^ |   0 You just need to find the minimum difference of i and j, of same element. If no such i and j exist ans=-1;
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 What will be the time complexity? Will it be O(n^2)
•  » » » » 4 weeks ago, # ^ |   +2 Depends how you implement, I did it using pair and map in O(n).
 » 4 weeks ago, # | ← Rev. 3 →   +2 English lesson: волшебная палочка — magic wand. :)(Don't try to look it up on Google — you'l get the wrong idea. :)))
 » 4 weeks ago, # |   0 Finally gained some confidence, Thank you so much for the contest.
•  » » 4 weeks ago, # ^ |   +2 What will you say when all your solutions are hacked? lol
 » 4 weeks ago, # |   0 only single line error in solution of problem D drop my dream of Expert.
•  » » 4 weeks ago, # ^ |   +21 Don't worry. We hope you will expert very soon.
 » 4 weeks ago, # |   +19 how to solve F?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +81 Use meet-in-the-middle, split x into first 15 bits and last 15 bits, and use map to check if there is second half.
•  » » » 4 weeks ago, # ^ |   0 Does this fit in time limits?
•  » » » » 4 weeks ago, # ^ |   +3 There will be like 2^15*100*30 operations if you use hashmap.
•  » » » » » 4 weeks ago, # ^ |   0 Done!! thanks
•  » » » » » 4 weeks ago, # ^ |   0 I wonder if it's possible to do a hash collision attack to force lots of deep equality checks if your hash function is deterministic
•  » » 4 weeks ago, # ^ |   0 Simplex!
•  » » » 4 weeks ago, # ^ |   +11 I also tried to solve the problem by constructing equations and inequations but didn't know how to solve the system. Can you please provide some useful resource to learn the simplex method and also to understand how to code it? Thanks.
 » 4 weeks ago, # |   0 Can anyone point out what the mistake could be for test-case 2 on problem D ?
•  » » 4 weeks ago, # ^ |   +1 Try something like this: 2 6 1 2 3 3 3 3 3 3 3 6 1 1 6 (ans = 2) 6 6 1 2 3 4 5 3 3 3 6 1 1 6 (ans = 4). These tests helped me to find out my mistakes
 » 4 weeks ago, # | ← Rev. 2 →   +13 i just have solved problem 1257C - Dominated Subarray — in Greedy solution in just O(n) ; why you did'nt include Greedy tag ! this is my submission : 64830934
•  » » 4 weeks ago, # ^ |   +9 std::map works in O(log), not in O(1). So, your solution is O(nlogn)
•  » » » 4 weeks ago, # ^ | ← Rev. 4 →   0 Didn't you notice that those 2 std::map's were never used? ;)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 IWMG my friend did you read my solution !!!?i never used std: map in it but just called it . i have used just one loop to read Input and an array to store last position for an element ! why it is O(n log n ) !
•  » » » » 4 weeks ago, # ^ |   +1 Yeah, im sorry for it, i thought you use only maps. Then you're right, your solution works in O(n)
 » 4 weeks ago, # |   -16 In problem D, we have to take input from the users which is O(n). So total TC would be minimum O(t*n) which is the order of 10^12. How is it passing?
•  » » 4 weeks ago, # ^ |   0 *Order of 10^10.
•  » » 4 weeks ago, # ^ |   +36 It is guaranteed that the sum of n+m over all test cases does not exceed 2⋅10^5
 » 4 weeks ago, # | ← Rev. 2 →   +6 I can only solved 2 problems... kinda have feeling my rating will be decreased again XD. I hope I can get better next time T_T. Gotta learn more frequent.
 » 4 weeks ago, # | ← Rev. 2 →   +5 Any clue about the 18th sub-test of test case 2 in problem D ?Edit: I was writing min in place of max in Sparse Table. XD
 » 4 weeks ago, # |   +5 Who else, first, thought of Binary Search for C? xD
•  » » 4 weeks ago, # ^ |   +12 :-/
•  » » 4 weeks ago, # ^ |   +6 I thought and did it that way only.
•  » » » 4 weeks ago, # ^ |   +6 Yeah, but you applied binary search to get the index where a[i] occurs next. I was applying it to find the optimal length.
•  » » » » 4 weeks ago, # ^ |   +8 Yes. Maybe.Submission
•  » » » » » 4 weeks ago, # ^ |   +9 Nice solution. I was checking if there exists a subarray of length exactly mid such that it is dominated, if no, I assumed that there will not be any dominated subarray with length less than or equal to mid, which clearly is wrong.
 » 4 weeks ago, # |   0 Whats the DP solution for E?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 dp[i][j]: I'm looking at element i, at group j.I can either start the next group -> dp[i][j]=dp[i][j+1]or add element i to existing group -> dp[i][j]=(i is not in group j) + dp[i+1][j]
 » 4 weeks ago, # |   +2 For all of you that want something to uphack but can't: 64856439. This shit really shouldn't pass, it should get WA or TLE or both.
 » 4 weeks ago, # | ← Rev. 2 →   +15 Try to hack my $O(n*2^{30})$ solution to F: Link
•  » » 4 weeks ago, # ^ |   +3 How does this runs in less than 2 seconds?
•  » » » 4 weeks ago, # ^ |   0 It does, my approach takes approx. 3 seconds on the judging server of CF(I used vectors and cins and stuff), yet it took forever to run on my own computer.However, I am getting WA 92 for some strange reasons, and since my logic is very similar to his, maybe he will get WA on the same tese(just my guess).I went through his judgement protocol and saw that he has only been tested with tests 1 to 83.
•  » » » » 4 weeks ago, # ^ |   +5 Oh, somebody already put into the effort to tinker the constant and break it lol.
•  » » » 4 weeks ago, # ^ |   0 The reasonThink from the setter's POV: First, to break brute force solutions, I should design test cases with only 1 solution, such that the coder has to search through the entire solution space.Then, to break code with only pruning implemented, the integers that are close to each other should share quite a lot of bits so that there are a lot of potential X that results in similar b[i] = a[0]^X. However, as you have very few solutions in the solution space (or else naive brute force goes through), integers that are far from each other should share very few bits. With randomization you bring integers that are far from each other together and makes pruning work efficiently.Vaguely speaking, if there are 2x more solutions, naive runs 2x faster; if there are 2x less solutions, pruning converges 1 iteration earlier.
 » 4 weeks ago, # |   0 What on earth is test $92$ of problem F? I kept getting WA for it using the most naive brute-force algorithm.
•  » » 4 weeks ago, # ^ |   0 You remove duplicates from the vector a but still loop up to n, not to the size of a, accessing elements past its size. It doesn't necessarily segfault since the vector had size n+1 before, but It seems something problematic happens in that test.
•  » » » 4 weeks ago, # ^ |   +1 I don't think that causes WA though? Although he/she is reading elements out of bounds, no writes were performed so the data should not be corrupted, and more reads (albeit corrupted) could only cause more "bad" cases to show up, hence this issue should not lead to false positive.
•  » » » » 4 weeks ago, # ^ |   0 I also think so. I mean, well, I am not doing anything to the out-of-bound indexes, and changing it to a.size() causes TLE3
 » 4 weeks ago, # |   0 I will hack you!
 » 4 weeks ago, # |   0 Can D be solved using binary search ? If yes can anyone share their approach?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +7 Try greedily defeat more monsters, so we need to binary search how far we can reach.Suppose we need to defeat K monsters and the highest power among them is P, we need to have at least one hero with p>=P and s>=K, which could be precalculated, in such a form: maxp_i = the largest power among heros which has s>=i. Thus we could easily check whether maxp_K>=P.Binary search such K and get the answer, to find P, is a problem of RMQ，use ST.
•  » » 4 weeks ago, # ^ |   0 Yes, there is a way. First sort all the heroes by power. Then create an array of suffix endurances for the sorted array of heroes. Suppose you have to kill k monsters on a particular day. Then find the maximum of those monsters and do a binary search on sorted heroes to find the suffix which includes all the heroes that have sufficient power to defeat the k monsters. Now, look at the maximum endurance of that suffix which we already calculated. If this endurance is at least k then we can kill k monsters. So you can check for each k whether we can kill k monsters or not in log(N) time.
 » 4 weeks ago, # |   +1 no systest?
 » 4 weeks ago, # |   0 How to sol D?? I need help..
 » 4 weeks ago, # | ← Rev. 8 →   0 Help needed in Problem EMy approach is getting WA on test case 6 and I don't know why. Please can someone tell me why it is coming wrong.My Approach :I will try to make all possible prefixes for A(first person) i.e. (from 0 to N) where N = k1+k2+k3. I have maintained a set of elements for all three of them. Now suppose prefix of A is "i", so I will remove all the elements less than equal "i" in the set of first, second and third person and for it, I am maintaining the count in a variable name "taken". Now the problem is to solve for B(second person) and C(third person), and this will be equal to the minimum of the count of (elements in C which smaller than the largest element in B) and (elements in B which bigger than the smallest element in C) this can be done using BIT(In which I delete the elements according to the prefix). Note that I don't have to give the remaining elements of A to B and C first and do the computation as we can assume that A was given to them in the correct order.So the final answer for the prefix "i" = taken + "remaining element in A(as he has to give it to other)" + min(element B give to C, element C give to B). And the minimum of all the prefixes will be our answer.My SubmissionThanks in advance!!!
•  » » 4 weeks ago, # ^ |   +3 Hi, check this case: 10 10 10 10 29 14 28 18 9 20 7 23 22 30 19 2 25 12 17 8 15 11 21 6 13 5 1 4 16 3 24 26 27 The answer should be 18. Hope it helps.
•  » » » 4 weeks ago, # ^ |   +3 Yep Got it!Thanks
 » 4 weeks ago, # |   +7 E can be solved using dp.But some people solved it using binarysearch,how to solve it using binarysearch?
•  » » 4 weeks ago, # ^ |   +6 And also How to solve using segment tree because I have seen some has done by segmeent tree
•  » » 4 weeks ago, # ^ |   +6 using dp mean using LIS or something else?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +6 dp[i][1] means the smallest cost which all [1,i] number return to its correct position and the i-th number(which is exactly i) belongs to the first Programmer.dp[i][2] means ... belongs to the second Programmer. dp[i][3] means ... belongs to the third Programmer.the ans is the smallest number among dp[n][1], dp[n][2] and dp[n][3].if id[i]==1 and you want to let it still belong to the first Programmer, it cost none. Otherwise you will cost 1 unit. int id[200005], dp[200005][4]; int main() { int A, B, C; scanf("%d%d%d", &A, &B, &C); for(int i = 1, ai; i <= A; ++i) { scanf("%d", &ai); id[ai] = 1; } for(int i = 1, bi; i <= B; ++i) { scanf("%d", &bi); id[bi] = 2; } for(int i = 1, ci; i <= C; ++i) { scanf("%d", &ci); id[ci] = 3; } int n = A + B + C; for(int i = 1; i <= n; ++i) { if(id[i] == 1) { dp[i][1] = dp[i - 1][1]; dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1; dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1; } else if(id[i] == 2) { dp[i][1] = dp[i - 1][1] + 1; dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]); dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1; } else { dp[i][1] = dp[i - 1][1] + 1; dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1; dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])); } } printf("%d\n", min(dp[n][1], min(dp[n][2], dp[n][3]))); return 0; } 
•  » » » » 4 weeks ago, # ^ |   0 Can you plz explain the transitions?
•  » » » » » 4 weeks ago, # ^ |   0 dp[i][1]=dp[i-1][1]+cost(i,1); dp[i][2]=min(dp[i-1][1],dp[i-1][2])+cost(i,2); dp[i][3]=min(dp[i-1][1],dp[i-1][2],dp[i-1][3])+cost(i,3);cost(i,j) means the cost if let the i-th problem be solved by the j-th programmer. Easily to know that cost(i,j)=1-(id[i]==j). dp[i][1] from dp[i-1][1] means let [1,i] problems all be solved by programmer 1.dp[i][2] from dp[i-1][1] means let [1,i-1] problems all be solved by programmer 1, but the i-th problem start to become be solved by programmer 2.It means when you start to assign i-th problem to programmer 2, you cannot assign all j-th problem (j>i) to programmer 1.
 » 4 weeks ago, # |   0 Can anyone confirm whether my approach for D is correct. Sort the soldiers with inc power. For every ith monster, do B.S and find the soldier whose power >= power of monster, let be at index idx, then I will choose the soldier with maximum strength from index idx to n (as all soldiers after idx have greater power than idx). Let's call this soldier as 'X'. I will kill as much monsters with this soldier as I can. Now two case arise- 1. Number of monster killed by x becomes equal to its strength, i.e., x.killed == x.strength 2. It's power is less than current monster.For the first case I will increase the count of day and again iterate as done in first step. For the second case, I will B.S and find the soldier whose power >= power of monster, and has the most strength(among those having power greater than the monster), let's denote it by 'Y'. Now 2 conditions arise, 1. x.killed < y.strength For this case I can safely say that instead of chosing X in the first place I could have chosen Y and killed more monsters than X, so I update my current soldier from X to Y (as X.power=Y.power, X.strength=Y.strength). 2. x.killed>=y.strength. For this case I increase count of day , udate my X and iterate forward(X.power=Y.power , X.strength=Y.strength, X.killed=1). I am getting WA for 2nd test case. Here is my solution : 64836864
 » 4 weeks ago, # |   +41 The color of the name seems to be wrong
•  » » 4 weeks ago, # ^ |   +7 Yeah, I have the same problem, I hope it's gonna be fixed soon
•  » » 4 weeks ago, # ^ |   +12 Yeah,I have rating above 1600.I am still specialist!!!
•  » » 4 weeks ago, # ^ |   0 ++
 » 4 weeks ago, # |   0 Does anybody have a $O(n)$ approach to solve D?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 I don't think an O(n) solution is possible for this problem. O(nlogn) is needed at least. UPD: oh there is a clever O(n) solution. watch roll_no_1 's comment.
•  » » 4 weeks ago, # ^ |   +1 You are also Chinese, so you can see this.https://www.cnblogs.com/KisekiPurin2019/p/11854682.htmlYou can use dp to get the highest power of heroes which has at least i endurance.  scanf("%d", &m); for(int i = 1, pi, si; i <= m; ++i) { scanf("%d%d", &pi, &si); p[si] = max(p[si], pi); } for(int i = n - 1; i >= 1; --i) p[i] = max(p[i], p[i + 1]); p[i] is the highest power which can beat i monsters in just one day.and then you can use greedy, each day try to move as more as possible.  int i = 0, j = 0, rmq = -1, ans = 1; while(j < n) { ++j; rmq = max(rmq, a[j]); if(p[j - i] < rmq) { if(rmq > p[1]) { ans = -1; break; } else { i = j - 1; ++ans; rmq = a[j]; } } } It means you have already beaten i-th monster, and you want to beat the j-th monster, today you move j-i blocks so the highest power is p[j-i], if p[j-1] < a[j], you need to wait until tomorrow and use your highest power hero p[1] to try to beat it.
•  » » 4 weeks ago, # ^ |   0 Right, Me too.
•  » » 4 weeks ago, # ^ |   0 me too
 » 4 weeks ago, # |   0 When will be an editorial?
 » 4 weeks ago, # |   0 What was the approach for D apart from Segment Trees/Sparse Table ?
•  » » 4 weeks ago, # ^ |   0 Sort by endurance and find for every endurance suffix maximum instead of using segment tree, and just compare maximum of monsters with this suffix maximum
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 you sort array of pairs . Then you try to kill in one day as much as possible so you iterate through $a_i$, count the number of monsters you want to kill this day as $cnt$ and memorise the most powerful monster this day as $max\text{_}pow$. You go further and further until there is a hero with $s_j \ge cnt$ (it can be checked by $lower\text{_}bound$) and a hero with $p_j \ge max\text{_}pow$. To check the last condition you can look at max hero power on suffix $[j..m - 1]$ and you can do it in $O(1)$ by precalcing an array $max\text{_}suf$ where $max\text{_}suf_i$ is the maximum power of hero in suffix $[i..m - 1]$ in sorted array
•  » » 4 weeks ago, # ^ |   +2 Why don't you read above there have been atleast 10 comments about D solution !!!
 » 4 weeks ago, # |   0 My Screencast for this round. https://www.youtube.com/watch?v=g5n6eW7uwVY
 » 4 weeks ago, # |   0 Jesus! Where is the solution(ok. i just want to know how to solve problem G
•  » » 4 weeks ago, # ^ |   0 I just made a brief writeup above.
 » 4 weeks ago, # | ← Rev. 2 →   0 UMMMMMM!!! OK XDD
 » 4 weeks ago, # | ← Rev. 2 →   +1 I have a question about the problem D. In this question,a special exampleInput:151 2 3 4 531 102 105 1for this example,the right answer should be 4,not 5`.And I found that a lot of the output through the AC code was 5.Why?
•  » » 4 weeks ago, # ^ |   0
•  » » 4 weeks ago, # ^ |   0 I found that some code can't even pass the simple data below： 1 2 1 2 1 2 2 Some of them AC code output -1,I think the background test data is too weak.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 s_i should be less than or equal to n, so {1, 10} and {2, 10} are invalid inputs
 » 4 weeks ago, # |   0 Can anyone explain solution of F briefly? TIA
•  » » 4 weeks ago, # ^ |   0
 » 4 weeks ago, # |   0 When will the editorials be available ?PS:Hints on div 2 C,D,E,F,G please ... I am new:)
 » 4 weeks ago, # |   0 How to solve E?? I think in E many coders used different techniques to solve it..Here are some in the comments.. more are welcome. https://codeforces.com/blog/entry/71362?#comment-557767https://codeforces.com/blog/entry/71362?#comment-557863
 » 4 weeks ago, # |   +3 Editorial?
 » 4 weeks ago, # |   0 When will the editorial of the problems be posted?
 » 4 weeks ago, # |   0 How about editorials???
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 4 weeks ago, # |   +3 Color display still not fixed ?
 » 4 weeks ago, # |   0 I can't see my friends standing of this contest. (It's not for sign in problem)Let me know if I only facing this problem...
 » 3 weeks ago, # |   0 Why Difficulty of this round in Problemset is None
 » 3 weeks ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 3 weeks ago, # |   0 Please also include pwild as the 5th place winner, we had the same penalty.
•  » » 3 weeks ago, # ^ |   +10 Whoops, sure. Funny enough my script got pwild into the rus version of the table and you in the eng one :D
•  » » » 3 weeks ago, # ^ |   0 I was wondering why I got a message saying I was mentioned in some topic, but then not actually finding my name in the text.