By awoo, history, 2 years ago, translation, In English

Hello Codeforces!

On Aug/27/2022 17:35 (Moscow time) Educational Codeforces Round 134 (Rated for Div. 2) will start.

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:

Harbour.Space

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

  • Vote: I like it
  • +174
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I hope this time it's going to be a good round

»
2 years ago, # |
Rev. 2   Vote: I like it +50 Vote: I do not like it
XiaochuanSun
»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Hope a balanced Edu round this time.

»
2 years ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

Previous Edu was so bad with bad pset.. Hope this'll be better than before<3

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

More like:

Educational Codeforces Round 134 [Rated for Div. 1]

»
2 years ago, # |
  Vote: I like it -14 Vote: I do not like it

After seeing the comments about previous bad edu rounds, I'm a little bit afraid of participating in this round.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

New Specialist arriving.......

  • »
    »
    2 years ago, # ^ |
    Rev. 4   Vote: I like it +47 Vote: I do not like it
    Spoiler
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      It may be mine new title.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        It was a sarcastic comment.

        Hope you become specialist in today's round, all the best!

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

WAforces

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    Video Solution for Problem C

    Hint
  • »
    »
    2 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.net/contest/1721/submission/169851465

»
2 years ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Who else thought that question B will get solved by BFS/Dijkstra's Algo?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    That would have taken way too much running time

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I gave up on C ? can any one at least explain the problem?? Post Contest Obviously.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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]

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    contrary test: a = {1 1 1 5}, b = {4 4 5 6}. Following your logic, mx[1] = 4, but it's actually 5

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Testcase
    Explanation
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for minimum can we use lower_bound function??

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yep

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Also possible to use the fact that arrays are sorted and maintain a pointer that only moves rightwards

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

the first edu round that i finally did good and solve ABC unexpectedly :>

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same question here

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

      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

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you explain, why we have to sort arrays in such way?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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 b

          For 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).

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        great solution thank you

»
2 years ago, # |
  Vote: I like it -17 Vote: I do not like it

D is annoying implementation, unless I'm missing something obvious

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    You are missing

    Something obvious
  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Really? The implementation is fairly straightforward (though somewhat long) if you use a set<pair<vector<int>, vector<int>>>

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Right I see now, I used set<pair<int, int>> and overcomplicated everything

»
2 years ago, # |
Rev. 2   Vote: I like it -45 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    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)$$$.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Then how to solve E?

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it +14 Vote: I do not like it

        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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm in the same situation as you.169890422

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it -33 Vote: I do not like it

D is so obvious, but the memory limit and implementation is so fucking annoying.

»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

B was very irritating

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell me where's the solution?

thanks!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Or there's no solution until now?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think solutions(if you mean tutorial/editorial) will be published after the open hacking.

»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    Your idea is correct. You can optimize it with 2 pointers technique.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone care to explain their solution to D.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Solution
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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<n;i++){
            if(d>=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<m;j++){
            if(d>=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);
    }
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :(

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But nethertheless, great round! Thanks for nice edu!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    Make a check if the vectors are empty. In this case, don't push them into the set.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much, how could I miss that :(

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        I missed that too at first (and probably a lot more people).

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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!

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is because you are using a set instead of a vector, and only one instance of empty arrays is inserted.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Oh shoot, thanks! Don’t know how that escaped me

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't add pairs of empty vectors.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Instead of copying divisions to new vectors, you can simply rearrange and operate on indices similar to quick sort partitioning.

    Submission: https://codeforces.net/contest/1721/submission/169880265

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.net/contest/1721/submission/169912449

    edit: I got the problem. It was because I was pushing unnecessary pairs to my vector. just like pushing empty vectors.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
Rev. 2   Vote: I like it -55 Vote: I do not like it

[Deleted]

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm always stuck at DIV2D

»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Shouldn't Problem B be m rows and n columns? M is Y-axis and N is X-axis.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Making a checker for F seems very interesting. Does anyone know how it was done?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +36 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

finally will make it to specialist :D

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I think E is too easy and standard and there should be a harder "string suffix structures" problem for me to solve.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Today's contest was really educational. But couldn't solve no more than two problem.

»
2 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can anyone please tell me why my code is giving wrong answer for this test case Problem D

Testcase
Code

My idea is to start from the highest bit and try to pair a[i] and b[i] where the both bits are different

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

This contest sucks. _HDH noob.

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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...

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Am I the only one who solved D with binary search?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Seems that if you can check whether answer $$$x$$$ is valid, you can get the optimal answer directly. So binary search is unnecessary.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only one who did E using Binary lifting and tree dp? all submissions seem way less complicated.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me improve this solution. I am just trying to gp the array elements based on count of setbits.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could anyone explain why my solution of C is giving TLE when it should clearly run in O(nlogn) Submission:169910737

»
2 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Can someone tell what is wrong with my code

Question C — Min-Max Array Transformation (Div 2)

#include<bits/stdc++.h>
#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<n;i++){
			cin>>arr[i];
		}
		int noPossible = false;
		for(int i=0;i<n;i++){
			cin>>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<n;i++){
			cout<<mind[i]<<" ";
		}
		cout<<endl;
		for(int i=0;i<n;i++){
			cout<<maxd[i]<<" ";
		}
		cout<<endl;
	}


	//set for precision
	// cout << fixed;
 //    cout << setprecision(12);
	return 0;
}

Submission Id — https://codeforces.net/contest/1721/submission/169917249

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hope you can understand my submission easily ,and will find your mistake. 169935846

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

is this problem D? image link

»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

To not keep you waiting, the ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem D?

  • »
    »
    2 years ago, # ^ |
    Rev. 9   Vote: I like it +3 Vote: I do not like it

    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:

    1. Sort $$$a$$$ and reverse-sort $$$b$$$ (this automatically prioritizes the leftmost bit position)
    2. 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.net/contest/1721/submission/169955540

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In my opinion ,Rounds Created by awoo always contains intresting problems. Thanks a lot, keep creating.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Educational rounds — more like negative delta rounds :(

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

got JUST enough for specialist ^_^ Lets gooo

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Dammn! at the border you're... Congrats for becoming unrated for upcoming Div4 LOL.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Ohhh this was nice contest.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope you will make contest again.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

in que 1 we can directly take character array of 4 size and sort them. then just see how many times elements changing

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Alternatively, we can just enter each of the four characters into a set. The answer is the size of the set minus 1. 169957444

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello. Can anyone help me understand why this solution WA2. Thank you!

https://codeforces.net/contest/1721/submission/169843966

(Please, don't downvote)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Come on why do Edu Round editorials take so long

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.

»
2 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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<int, int> 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 lol

To 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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone find out why on earth this code got RE? thks in advance.

Code (C++)

Edit: solved. (found that sort got an infinite loop. :( )