By awoo, history, 5 months 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 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon 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:

NEW APPRENTICESHIP OPPORTUNITIES IN BARCELONA
VODAFONE x HARBOUR.SPACE*
&
ONERAGTIME x HARBOUR.SPACE

Harbour.Space University has partnered with Vodafone Business, a company rich in tradition that specializes in telecommunications and with Oneragtime, a fund-as-a-platform specialized in sourcing, financing and scaling early-stage tech startups from across Europe, to offer motivated tech talents Master’s degree scholarships in Data Science and Front-end Development with combination of work experience.

Candidates will be working on the following tasks:

Data Scientist at Vodafone:

• Data Science: Descriptive and predictive analytics: selection, definition, and execution of adequate algorithms, models, tests, visualizations, etc.
• Technology: Selection, definition, and execution of adequate programming languages/frameworks, file formats, data storage solutions, automatic data flows, etc.
• Architecture: Define and/or follow best practices for Big Data & amp; Analytics use cases while extracting, transforming, storing, and feeding data to/from different data sources using on-premises solutions as well as public cloud services.
• Management: Report to project managers, clients, external and/or internal teams. Estimate resources and timelines for different tasks and follow up during the full project life cycle.
• Innovation: Awareness of and continuous training in state-of-the-art techniques, models, frameworks, and technical approaches to be applied to Data Science activities.

Front-End Developer at Oneragtime:

• Define the technology stack / tools to be used in the frontend
• Suggest projects that will improve the product or code base
• Write scalable, maintainable, reusable, and well-tested software that adheres to best practices
• Make technical time estimation on future software deliveries
• Document solutions with clear and concise explanations
• Collaborate with Product Owners, Growth Hacker, UX / Product Designers

All successful applicants will be eligible for a 100% tuition fee scholarship (22.900 €/year) provided by Vodafone Business for Data Science and by Oneragtime for Front-end Development.

CANDIDATE’S COMMITMENT

Study Commitment: 3 hours/dayYou will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.

Work Commitment: 4+ hours/dayImmerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.

University requirements

• Bachelor's degree in the field of Mathematics, Statistics, Data Science, Computer Science or similar
• English proficiency

Work requirements

Data Science:

• Advanced knowledge and experience in SQL, Python, Spark/Scala, and bash
• Experienced use of Big Data technologies: Spark, HDFS, Kafka, etc.
• Hands-on experience with Data Science techniques: feature engineering,

Front-end Development:

• Proficient in HTML/JSX, CSS, and with strong fundamentals in Javascript ES6
• Understand Vue
• Familiar with UX/UI principles: Figma
• Familiar with Webflow
• Expertise with Web pack, gulp, similar frontend build tools (npm)
• Proficient in unit testing tools e.g. JEST or similar tools
• Proficient in either Sass, LESS, TailwindCSS, Bootstrap, Flexbox, or similar tools
• Understanding of REST API
• Familiarity with Docker is appreciated
• Familiar with SQL works (Bonus: if you understand Postgre)
Apply Now for:
Front-end Development
Data Science

UPD: Editorial is out

• +174

 » 5 months ago, # |   +7 I hope this time it's going to be a good round
•  » » 5 months ago, # ^ |   0 You can do anything, just don't give up!
 » 5 months ago, # | ← Rev. 2 →   +50 XiaochuanSun
 » 5 months ago, # |   +38 Hope a balanced Edu round this time.
•  » » 5 months ago, # ^ |   -10 Better luck next time
 » 5 months ago, # | ← Rev. 2 →   +21 Previous Edu was so bad with bad pset.. Hope this'll be better than before<3
 » 5 months ago, # |   +4 More like:Educational Codeforces Round 134 [Rated for Div. 1]
 » 5 months ago, # |   -6 The round hasn't EVEN started, and the post Already got downvotes, LOL !!
 » 5 months ago, # |   0 imagine gaining positive delta
•  » » 5 months ago, # ^ |   -8 Spoiler: i did
 » 5 months ago, # |   -14 After seeing the comments about previous bad edu rounds, I'm a little bit afraid of participating in this round.
•  » » 5 months ago, # ^ |   0 Agreed, but... also... yolo?
 » 5 months ago, # |   0 I hope this one isn't as inbalanced as the previous one.. Good luck for everyone!
 » 5 months ago, # |   0 New Specialist arriving.......
•  » » 5 months ago, # ^ | ← Rev. 4 →   +47 SpoilerWhy are you revealing my new title before the beginning of the contest?
•  » » » 5 months ago, # ^ |   -7 It may be mine new title.
•  » » » » 5 months ago, # ^ |   +13 It was a sarcastic comment.Hope you become specialist in today's round, all the best!
•  » » » » » 5 months ago, # ^ |   +1 Not in a sarcastic way just bit confident that I would made this time but Whenever I am very close to becoming a specialist, my contest goes bad. I feel depressed and bad but I will not give up.
•  » » 5 months ago, # ^ | ← Rev. 9 →   0 Good luck! I hope I can get a bit closer to Pupil today as well
•  » » 5 months ago, # ^ |   0 Better luck next time ;)
•  » » » 5 months ago, # ^ |   0 wtf brah!!!
•  » » 5 months ago, # ^ |   0 sad bhai
 » 5 months ago, # |   +6 About the work and study opportunities... why would anyone with these skills do a Master or internship if you are not even paid enough to live in the city? I mean, with the required skills, you can get a real job and get paid more.
 » 5 months ago, # |   0 Hi everyone! Glad to talk to you again. Let's hope for the best. I hope that today's contest will be excellent and interesting and everyone will like it. I wish you good luck and the best success!
 » 5 months ago, # |   -12 educational round then div 4 , this is goooood.
 » 5 months ago, # |   +33 WAforces
•  » » 5 months ago, # ^ |   0 ACforces
 » 5 months ago, # |   0 How to solve C ?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +2 Video Solution for Problem C HintIterate from the end of array a.
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 For minimum, for each $a_i$, we look for the smallest $b_j$ such that $b_j \geq a_i$. Note that $j \leq i$ (since it must always be valid to map $a_i$ to $b_j$). It's valid to map $a_i$ to $b_j$ because the elements between $a_j$ to $a_{i - 1}$ can be mapped to the elements $b_{j + 1}$ to $b_i$. Obviously, we can't map $a_i$ to anything smaller than $b_j$. So the minimum $d_i = b_j - a_i$, where $b_j$ is the smallest element in $b$ that's $\geq a_i$.Maximum is trickier. Consider the first index $i$ where $a_{i + 1} > b_i$. Now for each $j \leq i$, I claim there will always exist a valid mapping from $a_i$ to $b_i$. Proof: For $j < i$, we can simply map elements $a_i$ and below to $b_{i - 1}$ and below (since $i + 1$ is the first index where we can't do this) until we reach $a_j$, which we can map to $b_i$. Furthermore, $b_i$ is the maximum choice for $a_j$ because $a_{i + 1}$ and above cannot map to $b_i$ and below, so by pigeonhole principle, the elements from $b_{i + 1}$ and above can only be occupied by $a_{i + 1}$ and above. Therefore, $d_j = b_i - a_j$, where $i$ is the first index in which $a_{i + 1} > b_i$ and $j < i$. We can then treat $a_{i + 1}$ as the new start, and look for the next index of this property, and so on. My submission: https://codeforces.com/contest/1721/submission/169851465
 » 5 months ago, # | ← Rev. 2 →   -13 Who else thought that question B will get solved by BFS/Dijkstra's Algo?
•  » » 5 months ago, # ^ |   0 I tried to solve using bfs since the edges are not weighted but i got wa on test 2 do you know why
•  » » 5 months ago, # ^ |   +1 i thought it was dp and wasted alot of time then noticed test cases and then i thought for like 20 mins and ficured out greedy and then made a mistake with a bracket and waste another 30 mins and finally figured it out.
•  » » 5 months ago, # ^ |   0 used BFS on grid but ended up with TLE on TC-3 :)
•  » » 5 months ago, # ^ |   +5 That would have taken way too much running time
•  » » 5 months ago, # ^ |   0 You never want to go up or left. Now, any path, that can be cunstructed moving only right or down, will take you n + m — 2 steps to get to (n, m). So, i don't think, that Dijkstra or BFS is intended
•  » » 5 months ago, # ^ |   +3 It was my first idea as well but a quick glance at the bounds should immediately tell you that it's too slow. Since there's no "sum of $N$ is at most" condition and you can have up to $10^6$ cells to calculate distances too, the total runtime can get up to $10^{10}$ which is way too high.
•  » » 5 months ago, # ^ |   0 maybe if the constraints were smaller?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 for problem B : if they laser spans across whole n or m or both are the only cases when we can't reach right ?  if((sx+d>= n && sx-d<=1 ) || (sy+d >= m && sy-d <=1)) System.out.println(-1); else System.out.println(n+m-2); why won't this work
 » 5 months ago, # |   0 I gave up on C ? can any one at least explain the problem?? Post Contest Obviously.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +9 Video Solution for Problem C HintIterate from the end of array a.
•  » » 5 months ago, # ^ |   -11 That's why you are newbie Saitama
 » 5 months ago, # |   0 What is wrong with my approach to problem C?Approach : For Maximum : for each b[i] , find the largest j , such that a[j] <= b[i] , then mx[i] = b[j] — a[i]For Minimum : find the leftmost j , such that b[j] >= a[i] , then mn[i] = b[j] — a[i]
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 contrary test: a = {1 1 1 5}, b = {4 4 5 6}. Following your logic, mx[1] = 4, but it's actually 5
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Try it with this sample. 5 6 7 8 9 9 5 6 7 8 10 11  Ans should be0 0 0 0 1 1 0 0 0 0 2 2
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 TestcaseInput:136 8 109 11 12Your output:3 1 1 5 4 2The correct output:3 1 1 6 4 2 ExplanationOne array D where D[1] has the maximum possible value is the following:6 1 1So after adding D[i] to A[i] for each 1 <= i <= n, the resulting array B is:12 9 11And after we sort it in non-descending order we will obtain the same array as the one in the input.
•  » » » 5 months ago, # ^ |   0 can u please explain your approach for C?
•  » » 5 months ago, # ^ |   0 for minimum can we use lower_bound function??
•  » » » 5 months ago, # ^ |   0 yep
•  » » » 5 months ago, # ^ |   0 Also possible to use the fact that arrays are sorted and maintain a pointer that only moves rightwards
 » 5 months ago, # |   +2 the first edu round that i finally did good and solve ABC unexpectedly :>
 » 5 months ago, # |   0 How to solve D?
•  » » 5 months ago, # ^ |   0 same question here
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Solve for bits from most significant to least significant.For any bit b, iterate through a and store the prefix in a multiset. Set all bits to 0 except the bits you've already set, and of course, this current bit.Iterate through b and try to find the inverse prefix in the multiset and remove it. Set all bits to 1 except the bits you've already set, and of course, the current bit.(By inverse prefix, we mean the prefix that when xor'd with the key in the map will produce 1 on every bit. So to find an inverse prefix, take a prefix, and xor it with the 1-mask to get the actual prefix).If the multiset has nothing left after you're done, you can set this bit. Store the info that this bit is already set and move on.Probably my implementation will get hacked, but here it is: 169888210
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +4 My solution has a similar idea, but personally find it easier to understand:For each bit i from most to least significant: Sort a increasing and b decreasing. Compute the answer for the current state of a and b, lets call it k.If the ith bit of k is set, then set the final answers ith bit to 1.Otherwise set all ith bits in a and b to 0. This works, because you greedily only consider bits which are used in the final answer when sorting the arrays and disregard all other bits. This solution works in $O(32 \cdot n \log n)$code
•  » » » » 5 months ago, # ^ |   0 Can you explain, why we have to sort arrays in such way?
•  » » » » » 5 months ago, # ^ |   +1 You want to partition $a$ into 2 subsets: all $a_j$ with the ith bit 1 all $a_j$ with the ith bit 0 You do the same for bFor the highest bit its easy to see that sorting will work to partition them into 2 subsets, because all $a_j$ with the ith bit 1 are strictly greater than $a_k$ with ith bit 0. So sorting a in increasing order will put all $a_j$ with ith bit 0 in the lower part and all $a_j$ with ith bit 1 in the higher part.In order to increase the xor you greedily match all $a_j$ with ith bit 1 with $b_j$ with ith bit 0 and vice versa.Now as you move down to the lower bits, you want to keep the matching of the previous assorted partitions (if they are part of the final answer), so you keep those bits as they were. Otherwise you erase them. So to answer your original question (i hope this clears it up a bit):Sorting a increasingly and b decreasingly matches the numbers with 0s at the ith bit in a with the numbers with 1s in the ith bit in b by putting the 0s of the 1s in each partition of a (and reversed in b).
•  » » » » » » 5 months ago, # ^ |   0 Thank you very much!
•  » » » » 5 months ago, # ^ |   0 great solution thank you
 » 5 months ago, # |   -17 D is annoying implementation, unless I'm missing something obvious
•  » » 5 months ago, # ^ |   -15 You are missing Something obviousYou can mask bits
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Really? The implementation is fairly straightforward (though somewhat long) if you use a set, vector>>
•  » » » 5 months ago, # ^ |   0 Right I see now, I used set> and overcomplicated everything
 » 5 months ago, # | ← Rev. 2 →   -45 In problem E Prefix Function Queries, Why am I get TLE on test 17 ? I used the concept of GFG problem. Its clearly in O(|s|+q*|t|).Submission link
•  » » 5 months ago, # ^ |   +47 The issue is that while loop. Computing prefix function is amortized $\mathcal O(n)$, but when you have queries and can "rollback" some suffix of the string, you break the amortized analysis and devolve to $\mathcal O(nq)$.
•  » » » 5 months ago, # ^ |   0 Thanks. Then how to solve E?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +14 To speed up the while loop, we note that the loop is just repeatedly jumping len = lps[len - 1] until we find a character that matches. Thus, we can compute a jump table jump[i][c] that marks the first index we jump to from index $i$ before reaching character $c$. This gives us a $\mathcal O((|s| + q|t|) \cdot \Sigma)$ solution where $\Sigma = 26$ is the alphabet size.Submission for reference
•  » » 5 months ago, # ^ |   0 I'm in the same situation as you.169890422
•  » » 5 months ago, # ^ |   +26 This is far from "clearly" $O(|s| + q|t|)$.  else // (pat[i] != pat[len]) { if (len != 0) { len = lps[len-1]; } else // if (len == 0) { lps[i] = 0; i++; } } Look at this code path. The len = lps[len - 1] line might happen many times as $i$ is not increased. The "vanilla" KMP will run in $O(|s|)$ because there is some amortized analysis saying it does. But now that you have all these different queries, it may happen that the parts of KMP that took a long time will happen every time.
 » 5 months ago, # |   -33 D is so obvious, but the memory limit and implementation is so fucking annoying.
 » 5 months ago, # |   -6 B was very irritating
•  » » 5 months ago, # ^ |   +9 you are too
•  » » » 5 months ago, # ^ |   0 yeah idk the n rows m columns thingy was confusing , I looked up a few solutions and people seem to implement in a way that considers columns as horizontals & rows as vertical.Guess it should have been more specific like xth row yth column rather than saying (x,y) cell. I'm curious if it's just me.
•  » » 2 months ago, # ^ |   0 if they laser spans across whole n or m or whole is the only case when we can't reach right ? if((sx+d>= n && sx-d<=1 ) || (sy+d >= m && sy-d <=1)) System.out.println(-1); else System.out.println(n+m-2); why won't this work ?
 » 5 months ago, # |   0 Can anybody tell me where's the solution?thanks!
•  » » 5 months ago, # ^ |   0 Or there's no solution until now?
•  » » » 5 months ago, # ^ |   0 I think solutions(if you mean tutorial/editorial) will be published after the open hacking.
•  » » » » 5 months ago, # ^ |   0 Oh,thanks
•  » » » » » 5 months ago, # ^ |   0 Actually they're just lazy. Gotta wait more:(
•  » » » » » » 5 months ago, # ^ |   0 haha
 » 5 months ago, # |   +18 I would like to report that problem D of this round had already been discussed (main idea as well as code) on StackOverflow 1+ year back and I believe many have used this and would lead to an unfair advantage to them in today's round.
 » 5 months ago, # |   0 Can someone explain an easy way to implement C ? I was doing it with sets but I am getting TLE on TC-5. My solution was to check for every ai if there exists a range of values bi ( l <= i <= r ) greater than or equal to ai and the smallest di would be b[l]-ai and largest di would be b[r]-ai.
•  » » 5 months ago, # ^ |   -16 Your idea is correct. You can optimize it with 2 pointers technique.
 » 5 months ago, # |   0 Anyone care to explain their solution to D.
•  » » 5 months ago, # ^ |   0 SolutionBe greedy on MSB and check if its possible. If you are trying to make ans, then you only need to care about bits which are set in ans.So iterate from i = 31 to 0 set tar = ans|(1<
 » 5 months ago, # |   0 Is my approach for E correct (didn't have time to code it):First create a hash for each prefix of string so that we can efficiently compute hashes of substrings. Now for each prefix check whether it is a suffix of the original string in $O(N \log N)$, firstly just store hashes of prefixes in a map, then traverse all suffixes and try to match them to prefixes using map.Now we for each $i$ traverse intervals $(i,i)$, $(i,i+1)$, $(i,i+2)$, ..., $(i,i+9)$ and update maximum prefix that ends at $i-1$ that is also a suffix of the original string using the previously computed value. Now all that is left is for each query, for each prefix of $t$ add the maximum value + its length if its hash exists in the original string.Is this valid, seems good on sample checking by hand?
 » 5 months ago, # |   -8 can any one tell that why its giving tle on 3rd testcase in (B)  private static long find(int[][] arr,int sx,int sy,int d){ int n=arr.length; int m=arr[0].length; long one=0; long two=0; for(int i=0;i=distanceBetweenPoints(i, 0, sx, sy))one=imax*-1; if(d>=distanceBetweenPoints(i, m-1, sx, sy))two=imax*-1; two++; one++; } for(int j=0;j=distanceBetweenPoints(n-1, j, sx, sy))one=imax*-1; if(d>=distanceBetweenPoints(0, j, sx, sy))two=imax*-1; two++; one++; } if(one<0&&two<0)return -1; if(one<0)return two; if(two<0)return one; return min(one,two); } 
•  » » 5 months ago, # ^ |   0 Your algorithm is probably O(m*n). m and n can be up to 1000, and there can be up to 10^4 test cases. Worst case time complexity would be 1000 * 1000 * 10^4https://leetcode.com/problems/minimum-cost-homecoming-of-a-robot-in-a-grid/ recalled when I made that mistake in this problem
 » 5 months ago, # |   0 Nooo, i saw timer was on 3 minutes, so i thought i have enough time to upwrite D, but it finished like 10 seconds after i continued writing code... Could've got to expert, if solved D :(
•  » » 5 months ago, # ^ |   0 But nethertheless, great round! Thanks for nice edu!
 » 5 months ago, # |   0 How to optimize D? I got TLE on test 4.My algorithm : I maintained a vector of pair of vectors. Initially we have the pair of given 2 vectors. Now, from the highest bit to lowest bit, find if complementary number of bits are set in each pair of vectors. If yes, divide each vector into 2 vectors which can be paired with one another.Submission link : 169890132
•  » » 5 months ago, # ^ |   +43 Make a check if the vectors are empty. In this case, don't push them into the set.
•  » » » 5 months ago, # ^ |   0 Thank you so much, how could I miss that :(
•  » » » » 5 months ago, # ^ |   +4 I missed that too at first (and probably a lot more people).
•  » » » 5 months ago, # ^ |   +4 Thanks, man. I had the same idea and thought it was too slow, because of the TLE (and I can't seem to figure out how and why). You saved my day!
•  » » » 5 months ago, # ^ |   0 Strangely when I added this check into my code, my runtime only went from 1450ms to 1403ms: 169971754 vs 169857453. My solution checks for impossibility first before doing anything else though, so that might be it. Still, I'd expect the difference to be more substantial.
•  » » » » 5 months ago, # ^ |   0 This is because you are using a set instead of a vector, and only one instance of empty arrays is inserted.
•  » » » » » 5 months ago, # ^ |   +3 Oh shoot, thanks! Don’t know how that escaped me
•  » » 5 months ago, # ^ |   0 Don't add pairs of empty vectors.
•  » » 5 months ago, # ^ |   0 Instead of copying divisions to new vectors, you can simply rearrange and operate on indices similar to quick sort partitioning.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I tried to solve it with the same idea. I also got TLE on test 4. I tried to make it better by using pairs of numbers that show a range on the first vectors. I am getting MLE on test 15. I have no idea why it is using so much memory. Can anyone help me understand why my code is using so much memory while it should use much less? (just a few vectors should not reach the max limit memory.)https://codeforces.com/contest/1721/submission/169912449edit: I got the problem. It was because I was pushing unnecessary pairs to my vector. just like pushing empty vectors.
•  » » 5 months ago, # ^ |   0 Checking to see if you can achieve the bits before creating the new pairs would probably help. In your solution you potentially waste a lot of time pushing pairs of vectors into things and then discarding them.
 » 5 months ago, # | ← Rev. 2 →   -55 [Deleted]
 » 5 months ago, # |   0 I'm always stuck at DIV2D
•  » » 5 months ago, # ^ |   +11 One day you will not.
 » 5 months ago, # |   -6 Shouldn't Problem B be m rows and n columns? M is Y-axis and N is X-axis.
•  » » 5 months ago, # ^ |   +28 $x$-axis is from up to down almost always in CP.
•  » » » 2 months ago, # ^ |   -10 if they laser spans across whole n or m or whole is the only case when we can't reach right ? if((sx+d>= n && sx-d<=1 ) || (sy+d >= m && sy-d <=1)) System.out.println(-1); else System.out.println(n+m-2); why won't this work
•  » » 5 months ago, # ^ |   +7 Please noI'd rather prefer they didn't use x for Y-axis coordinates
 » 5 months ago, # |   0 God, I misinterpreted problem B and thought that robot is moving to a certain point that is given as part of the input... Wasted a lot of time due to this.
 » 5 months ago, # |   -38 took me an hour trying to understand C bad problem statement
 » 5 months ago, # |   +18 Making a checker for F seems very interesting. Does anyone know how it was done?
•  » » 5 months ago, # ^ |   +5 It probably only does checking for the each 2-query that the sum of edge indices matches the value printed on the last 1-query.
•  » » 5 months ago, # ^ |   +15 To check if the removal of a vertex results in a smaller maximum matching, it is sufficient to check that there is no alternating path from an unmatched vertex to its matched side (it doesn't matter which maximum matching we use for this check). This can be rephrased into dynamic connectivity. Note that the checker doesn't need to be fully online, so there's lots of options for the problemsetter here. Whether the sum of edges is achievable is probably not tested, although there are some sums that are clearly not achievable, so there are at least some cases where a WA can be created this way.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +36 It was kinda painful to implement.The interactor doesn't check everything, but it checks a lot. First of all, the fact that deleting a subset of vertices decreases the matching is checked using the following assumptions: it is always possible to remove just one vertex, so if the participant removes more, then he gets WA; suppose the participant has removed $k$ vertices. Then the matching should be decreased by $1$ with each deletion; but since deleting a vertex can reduce the matching at most by $1$, then it's enough to check that the matching in the resulting graph is reduced exactly by $k$. If it is so, then every operation has decreased the matching; if it is not, then the answer to some query was wrong. So, the interactor doesn't need to check the matching after each query, it checks the matching only in the end. Checking the sum of numbers in a matching is not perfect. You can, for example, print that the sum of edges is -1e18, and the interactor won't mind it. It relies on the fact that your solution doesn't know the moment when it has to process the query of type $2$ beforehand, so you can actually print some nonsense, but most probably you will get caught.
 » 5 months ago, # |   0 I have submitted two solutions for problem B because the previous solution submitted was hackable and now that solution is hacked, so will my most recent submission counts? I am asking this because my rank has been dropped after getting the old solution of problem B getting hacked
 » 5 months ago, # |   0 finally will make it to specialist :D
 » 5 months ago, # |   0 can someone tell me the rating of problem B
•  » » 5 months ago, # ^ |   0 900-1000
 » 5 months ago, # |   0 Is there anyone who was trying to solve C using binary search and wasted alot of time?
 » 5 months ago, # |   0 Anyone want to try to hack 169846064? Basically, I took the naive approach of recomputing the prefix function each query and put a trie on top of it to reuse computations. I made a hack where it runs in 763 ms (as compared to the current 311 ms) but maybe someone knows how to make a better test.
 » 5 months ago, # |   +16 I think E is too easy and standard and there should be a harder "string suffix structures" problem for me to solve.
•  » » 5 months ago, # ^ |   +3 How to solve E?
 » 5 months ago, # |   +3 Today's contest was really educational. But couldn't solve no more than two problem.
•  » » 5 months ago, # ^ |   0 joy bangla happy coding...
 » 5 months ago, # | ← Rev. 2 →   +5 Can anyone please tell me why my code is giving wrong answer for this test case Problem D Testcase 1 8 28 14 12 27 10 8 27 27 5 23 17 2 21 19 6 22 Correct answer 12 my code giving 9 Codell getBit(ll num, ll index) { return (num & (1 << index)) != 0; } ll n; vector vca, vcb; void helper(ll start, ll end, ll bit) { if (bit == -1 || start >= end) return; ll a[bit+1]={0}; ll b[bit+1]={0}; FOR(i, start, end+1) { FOR(j, 0, bit+1) { a[j] += getBit(vca[i], j); } } FOR(i, start, end+1) { FOR(j, 0, bit+1) { b[j] += (getBit(vcb[i], j) == 0); } } FORD(j, bit, -1) { if (a[j] != b[j]) continue; vector ansa(vca), ansb(vcb); ll sa = start, ea = end, sb = start, eb = end; FOR(i, start, end + 1) { if (getBit(vca[i], j) == 0) { ansa[sa++] = vca[i]; } else { ansa[ea--] = vca[i]; } if (getBit(vcb[i], j) == 0) { ansb[eb--] = vcb[i]; } else { ansb[sb++] = vcb[i]; } } vca = ansa; vcb = ansb; cout< "<> n; vca.resize(n); vcb.resize(n); cin >> vca >> vcb; helper(0, n - 1, 30); ll ans = INT_MAX; FOR(i, 0, n) { ans &= (vca[i] ^ vcb[i]); } cout<
 » 5 months ago, # |   +4 This contest sucks. _HDH noob.
 » 5 months ago, # |   +21 Brute force can AC problem E because of the too small $|t|$. AC Submission.That's too bad. I think problem E is really a bad problem.
 » 5 months ago, # |   +4 Bruh I knew how to solve D at 1h left but I got so many bugs it took me 1h past the contest to finally AC...
•  » » 5 months ago, # ^ |   +3 Same :(
 » 5 months ago, # |   +6 Am I the only one who solved D with binary search?
•  » » 5 months ago, # ^ |   +4 I thought about doing that, but I ultimately decided against that. I assume you mean binary searching on the answer, right? I didn't do that b/c I don't think it's guaranteed that if a value x works, then all values below x work.
•  » » » 5 months ago, # ^ |   +9 Yes, I did that. Actually, "if a value x works, then all values below x work" is an incorrect statement lol, but in the loop I checked can we make a number for a certain m which contains 1 in all bits where m contains 1. And seems like we can find out the asked number bit by bit
•  » » 5 months ago, # ^ |   0 Seems that if you can check whether answer $x$ is valid, you can get the optimal answer directly. So binary search is unnecessary.
 » 5 months ago, # |   0 Am I the only one who did E using Binary lifting and tree dp? all submissions seem way less complicated.
 » 5 months ago, # |   0 Can anyone help me improve this solution. I am just trying to gp the array elements based on count of setbits.
 » 5 months ago, # | ← Rev. 2 →   0 Could anyone explain why my solution of C is giving TLE when it should clearly run in O(nlogn) Submission:169910737
•  » » 5 months ago, # ^ |   0 Time Complexity for s.erase() is O(sizeof(set))
•  » » » 5 months ago, # ^ |   0 s.erase(iterator) is O(1) while s.erase(val) is O(sizeof(set)) as you explained
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Ok my bad, Maybe the problem is erasing an empty set is an undefined behavior
•  » » 5 months ago, # ^ |   +3
•  » » » 5 months ago, # ^ |   0 Sorry to pester you with my silly doubts but using multiset.lower_bound() is still giving me TLE. Is this normal? Submission: 169937456
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Your AC code 169944009
•  » » » » » 5 months ago, # ^ |   0 Thank you so much aryanc403 and indreshsingh. I was really sad after the contest since this question was utterly easy but i couldn't figure out my mistake.
 » 5 months ago, # |   -15 Can someone tell what is wrong with my code Question C — Min-Max Array Transformation (Div 2) #include #define ll long long using namespace std; const int N = 1e5 + 5; const int INF = 1e9; const ll modulo = 1e9+7; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while(t--){ int n; cin>>n; int maxVal = INT_MIN,minVal = INT_MAX; int arr[n],b[n]; for(int i=0;i>arr[i]; } int noPossible = false; for(int i=0;i>b[i]; } int maxd[n],mind[n]; int k = n; for(int i=n-1;i>=0;i--){ auto idx = lower_bound(b,b+k,arr[i]) - b; mind[i] = b[idx] - arr[i]; maxd[i] = b[k-1] - arr[i]; if(idx>=k){ noPossible = true; break; } if(idx==k-1 or b[k-1] == b[idx]){ k--; } } if(noPossible){ memset(mind,0,sizeof(mind)); memset(maxd,0,sizeof(maxd)); } for(int i=0;i
•  » » 5 months ago, # ^ | ← Rev. 2 →   +1 Here is a counter-example: 3 1 2 3 1 3 4 The maximum difference for $a_1$ should be 0. To see why, observe that $a_2 = 2$ cannot be mapped to $b_1 = 1$ (since $2 > 1$), which means that {$a_2, a_3$} must map to {$b_2, b_3$}. By the pigeonhole principle, this means $a_1$ can't map to {$b_2, b_3$}. Therefore, $a_1$ must be mapped to $b_1$ no matter what, so both the minimum and maximum $d_1$ are equal to $0$. The error in your code is how you compute the maximum. Greedily picking the largest possible $k$, which only decrements if idx==k-1 or b[k-1] == b[idx] is insufficient. My approach, instead, was to find the next index $k$ for which $a_{k + 1} > b_k$, which means indices $\leq k$ cannot be mapped to $b_{k + 1}$ or above, but they can be mapped to $b_k$ instead, to yield the maximum possible difference.
•  » » » 5 months ago, # ^ |   0 oh okay got it thanks
•  » » 5 months ago, # ^ |   0 Hope you can understand my submission easily ,and will find your mistake. 169935846
 » 5 months ago, # |   +12 is this problem D? image link
 » 5 months ago, # |   +29 To not keep you waiting, the ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!
 » 5 months ago, # |   0 Can anyone explain problem D?
•  » » 5 months ago, # ^ | ← Rev. 9 →   +3 The third test-case provides a nice hint. If my explanation is too long, feel free to skip to the end for the algorithm steps.Suppose the answer is $x$. Consider the leftmost 1 bit (MSB) of $x$. Let's say it's at position $k$. Elements of $a_i$ with a 0 in bit $k$ would be paired with a $b_i$ that has 1 in bit $k$, and vice versa. This means, if you were to sort $a$ according to bit $k$ only (ignoring all higher bit positions), and if you were to reverse-sort $b$ according to bit $k$ only, then the bitwise XOR of $a_i$ and $b_i$ will always yield a 1 in bit $k$.Okay, so it's easy to find the first $1$ in $x$, but how do we find the next $1$? Let's say that the second 1 from the left in $x$ is at bit position $k'$. This time, it's not enough to look only at bit $k'$ to pair $0$s in $a$ with $1$s in $b$ and vice versa, because we also need to make sure the relationship in bit $k$ is preserved. Essentially, bit $k$ partitions $a$ and $b$ into two (where the $0$-partition in $a$ has the same size as the $1$-partition in $b$ and vice versa) and then within each partition pair, we need to make sure bit $k'$ achieves a similar partition. It follows that if we(a) sort $a$ according to bit $k$ and reverse-sort $b$ according to bit $k$ as mentioned before,(b) for the partition in $a$ that has the same bit $k$, we sort these elements according to bit $k'$, while for the corresponding partition in $b$ with the opposite bit $k$, we reverse-sort these elements according to bit $k'$Then the bitwise XOR between $a$ and $b$ should now have both bit $k$ and bit $k'$ yielding $1$s. This partition idea may sound complicated to implement, until you realize that this is basically how numbers are sorted anyway! Sort by the most significant bit first, and then for those with the same MSB, we sort by the second most significant bit, and so on. It's just plain sorting! The only difference is that we skip the bit positions in which we're not able to form such pairs (i.e., some partition formed by $a$ does not have the same size as the corresponding partition formed by $b$), where $x$ will have 0 in such bit positions. But if we ignore these bit positions, then a sorted $a$ will map perfectly to a reverse-sorted $b$.This leads to the following algorithm: Sort $a$ and reverse-sort $b$ (this automatically prioritizes the leftmost bit position) For each bit position $k$, from leftmost to rightmost, check if the bits in position $k$ for ALL elements in $a$ are the opposite of the corresponding elements in $b$. If yes, we set the answer's bit $k$ to 1, because any arrangement of $a$ and $b$ that preserves this ordering of bit $k$ in their elements will produce a 1 in the bit $k$ of the answer. If no (at least one element of $a$ has the same bit $k$ as the corresponding element in $b$), then we clear bit $k$ to 0 for ALL elements of $a$ and $b$. Now we sort $a$ and reverse-sort $b$ again (does not have an impact on bit positions more significant than $k$, position $k$ itself is irrelevant, so the rearrangement considers $k - 1$ onwards) My submission: https://codeforces.com/contest/1721/submission/169955540
 » 5 months ago, # |   +3 In my opinion ,Rounds Created by awoo always contains intresting problems. Thanks a lot, keep creating.
•  » » 5 months ago, # ^ |   +4 Are you serious? Last edu round?
 » 5 months ago, # |   +1 Educational rounds — more like negative delta rounds :(
 » 5 months ago, # |   +1 got JUST enough for specialist ^_^ Lets gooo
•  » » 5 months ago, # ^ |   +1 Dammn! at the border you're... Congrats for becoming unrated for upcoming Div4 LOL.
•  » » » 5 months ago, # ^ |   +1 haha, true
 » 5 months ago, # |   0 Ohhh this was nice contest.
 » 5 months ago, # |   0 hope you will make contest again.
 » 5 months ago, # |   +1 in que 1 we can directly take character array of 4 size and sort them. then just see how many times elements changing
•  » » 5 months ago, # ^ |   +1 Alternatively, we can just enter each of the four characters into a set. The answer is the size of the set minus 1. 169957444
 » 5 months ago, # |   0 Hello. Can anyone help me understand why this solution WA2. Thank you!https://codeforces.com/contest/1721/submission/169843966(Please, don't downvote)
•  » » 5 months ago, # ^ |   +1 I haven't examined the code itself, but it seems you're calculating maximum incorrectly. Consider the following test-case: 3 1 2 3 1 3 4 The maximum difference for $a_1$ should be 0. To see why, observe that $a_2 = 2$ cannot be mapped to $b_1 = 1$ (since $2 > 1$), which means that {$a_2, a_3$} must map to {$b_2, b_3$}. By the pigeonhole principle, this means $a_1$ can't map to {$b_2, b_3$}. Therefore, $a_1$ must be mapped to $b_1$ no matter what, so both the minimum and maximum $d_1$ are equal to $0$. I'm not sure what you were trying to do for maximum, but my approach was to find the next index $k$ for which $a_{k + 1} > b_k$, which means indices $\leq k$ cannot be mapped to $b_{k + 1}$ or above, but they can be mapped to $b_k$ instead, to yield the maximum possible difference. 169851465
•  » » » 5 months ago, # ^ |   0 Thank you.
 » 5 months ago, # |   +8 Come on why do Edu Round editorials take so long
 » 5 months ago, # |   0 can anyone tell me why i get WA on test 2, please tell me how to correst it, and thanks a lot.please don't downvote!my record
•  » » 5 months ago, # ^ |   0 I didn't understand your program code, but here is a counter-test: 2 1 1 1 2 The minimum values for $d_1$ and $d_2$ are both 0, since either of them can be mapped to $b_1 = 1$. You can find the minimum $d_i$ by simply looking for the smallest $b_j$ such that $b_j \geq a_i$.
 » 5 months ago, # | ← Rev. 2 →   +1 Here's an interesting solution I found for E, not sure if it's new. Implementation here, featuring enough spaghetti to feed a family of five for a week.We do some precomputation first. Use a map m, where values are hashes of a substring of $S$, and the corresponding value is the maximal number $i$ such that the length $i$ prefix and suffix of $S$ are the same. To calculate this, we iterate $i$ independently of the substring, and check if the prefix and suffix have the same hashes in $O(1)$ time. If so, we add update m on substrings $S[i+1..i+1+j]$ (technically their hash values). As we'll see later, we only care about $j \leq 10$, so this takes $O(|S|\log |S|)$ time which is fast enough (we can use an unordered_map or gp_hash_table as well but time is not an issue). Note that if we double-check our hash equality by directly comparing the substrings, we TLE on TC 36 which is all a's, since comparing strings/generating substrings is linear in the length of the string so our program runs in $O(|s|^2)$ in that case.We consider every $|S|+i$ more or less independently (I will use uppercase letters). Let $T_i=T[1..i]$ denote the length $i$ prefix of $T$. Suppose we have some prefix string $x$ of $S+T_i$ that's also a suffix string. There are three possibilities:(1): Both the prefix and suffix strings lie in both $S$ and $T_i$. In this case, we can break $x$ up into $x_1,x_2,x_3$ (in that order) defined as follows: $x_1$ is the portion of the suffix string lying in $S$, $x_3$ is the portion of the prefix string lying in $T_i$, and $x_2$ is the remainder of $x$. To check if any $x$ of this type work, we iterate over $|x_3|:=j$, checking if the length-$j$ prefix and suffix of $T_i$ are the same. If so, then $x$ works if and only if the rightmost occurrence of $x_2$ in $S$ is as far right as it can be (i.e. occupies starting position $|S|-|x_2|$). In this case, the length-$|x_1|$ suffix of $S$ is also $x_1$, so we can use our precomputed m. There are at most $10$ values for $|x_3|$, so iterating over them is fast.(2): The prefix string lies entirely in $S$, but the suffix string does not lie entirely in $T_i$. This is more or less a simpler version of (1). We split $x$ into $x_1,x_2$ such that $x_2$ is the portion of the suffix string lying in $T_i$, and $x_1$ is the remainder. Since $x_2$ must be $T_i$ by definition, $T_i$ must appear in $S$ as a substring. Further, $x_1$ must also be the suffix string of $S$ when this happens. We can use m for this as well. Note that there's only one possible value for $x_2$.(3): The suffix string lies entirely in $T_i$. If $|S|>=i$, then that means the prefix string lies entirely in $S$. There's at most $10$ values for $x$, so we can iterate $j$ from $1$ to $i$ (inclusive) and check if $S[1..j]=T_i[i-j+1...i]$. Otherwise, we have to join $S$ and $T_i$, since the prefix string could partially lie in $T_i$ as well, but the actual check is the same. Since this case only occurs when $|S|\leq 10$, joining $S$ and $T_i$ is quick (if you join $S$ and $T_i$ no matter what, you should TLE). Either way, you iterate through at most $10$ possible values for $x$. Ignore the comment at the top lolTo find the final answer, we iterate through all $O(1)$ cases and update our maximum value each time. The final time complexity should be $O((|s|+q)\log |s|)$ which works if you're not being stupid.
 » 5 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 5 months ago, # | ← Rev. 3 →   0 Can someone find out why on earth this code got RE? thks in advance. Code (C++)#include #define x first #define y second #define N 100005 using namespace std; int t,n,a[N],b[N],ans,ord,cnt; paire[N]; bool ch(int k){ // cout<>k)&1)+((b[j]>>k)&1); } if(tot!=0) return 0; } return 1; } bool cmp1(int a1,int a2){ return (a2>>ord)&1; } bool cmp2(int a1,int a2){ return (a1>>ord)&1; } signed main(){ for(cin>>t;t;t--){ cin>>n; ans=0,cnt=1; e[0]={n,-1}; for(int i=0;i>a[i]; } for(int i=0;i>b[i]; } for(int k=29;k>=0;k--) if(ch(k)){ ord=k; ans|=(1<>ord)&1)!=((a[j-1]>>ord)&1)) break; if(j==e[i].x) continue; e[cnt]=e[i]; e[i]={j,cnt}; i=cnt,j=e[cnt++].x; } } cout<