By awoo, history, 12 months ago, translation, In English

Hello Codeforces!

On Nov/03/2023 17:35 (Moscow time) Educational Codeforces Round 157 (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, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Artem Ferume Ilikaev, Ruslan AcidWrongGod Kapralov, Alexey ashmelev Shmelev, Alex fcspartakm Frolov, Dmitry DmitryKlenov Klenov, Dmitry dmitryme Mescheryakov, Elena elena Rogacheva and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Please note that the problems of this round partially intersect with the problems of the Southern and Volga Russian Regional Contest. If you took part in that contest, please refrain from participating in the round.

Good luck to all the participants!

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

Harbour.Space
WORK & STUDY OPPORTUNITY IN BARCELONA — BIMBA Y LOLA x HARBOUR.SPACE UNIVERSITY

BIMBA Y LOLA has partnered with Harbour.Space University to offer a Master's Degree scholarship in Computer Science, as well as work experience as a Junior Java Developer at the Development Team in BIMBA y LOLA.

At BIMBA Y LOLA, they understand the importance of counting on the most creative professionals, those with an enterprising spirit and passion for their work. They are seduced by talent, sensibility, initiative, an analytical nature, commitment to quality, a keen eye and a love for detail. And, of course, a clear vocation for fashion.

If you share these values, we are offering a young, dynamic and stimulating environment; one in which to progress and develop professionally; a company present in over 18 countries and embarked on an ambitious international expansion plan.

All successful applicants will be eligible for a 100% Tuition Fee Scholarship (29,900€/year) provided by BIMBA Y LOLA.

Requirements:

  • Spanish and English language proficiency is a MUST
  • Bachelor's degree in the field of Mathematics, Statistics, Data Science, Computer Science or similar

The candidate should be familiar with:

  • Agile Methodologies (scrum)
  • GIT
  • Java 8/11+
  • Spring
  • Maven
  • JUnit
  • Mockito
  • UML
  • HTML
  • CSS
  • Javascript
  • ReactJS
  • SQL Server/MySQL

Desirable skills:

  • Azure
  • Azure DevOps — Pipelines
  • Docker
  • Kubernetes
  • Helm
  • Jira
  • Confluence

Apprenticeship Summary:

  • 100% Tuition Fee Scholarship to study a Master’s Degree in Computer Science for one year.
  • 4 hours/day internship on campus.
  • Competitive compensation.
  • Opportunity to join the company full-time after graduation.
  • Please note that preselected candidates will be requested to pay a non-refundable Application Fee of 125€ for assessment.

Candidate’s commitment:

  • Study Commitment: 4 hours/day
  • ‍You will complete 15 modules (each three weeks long) in one year.
  • Daily class workload is 3 hours, plus homework to complete in your own time.
  • Work Commitment: 4+ hours/day

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

Apply here →

UPD: Editorial is out

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

| Write comment?
»
12 months ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

My comment is on top (yeee) ... By the way thanks to authors for their hard work <3... Hope we'll enjoy the round.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Educational round....ok(finger crossed)

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the crossed finger trick do not worked for me (sad wale emoji)...

»
12 months ago, # |
  Vote: I like it +82 Vote: I do not like it
It is what it is
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nothing scares me more than edu round.

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why has the frequency of edu rounds decreased?

Not complaining, just curious!

»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Artem Ferume Ilikaev, Ruslan AcidWrongGod Kapralov, Alexey I_Remember_Olya_ashmelev Shmelev, Alex fcspartakm Frolov, Dmitry DmitryKlenov Klenov, Dmitry dmitryme Mescheryakov, Elena elena Rogacheva and me.

I think the writer list on the Contest page doesn't reflect this correctly, it's currently just the usual BledDest-Neon-Roms-adedalic-awoo.

»
12 months ago, # |
  Vote: I like it -22 Vote: I do not like it

Educational Rounds are mathforces af. Would skip this one.

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

    You said the exact same thing last time as well.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      and I don't even understand what he means, if Edu rounds were mathforces I would've farmed the hell out of it

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Right?!

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i think he failed in maths in his high school :}

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Who are you lil bro and how would you farm Edu rounds if they were mathforces?

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If it were mathforces, I would gain rating over number theory tasks every contest, and take advantage of less implementation and more math/observation. That doesn't seem to happen to me anyways if you look at my contest record.

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            isnt almost every div2 just observation and constructive stuff tho lol (maybe im just having recency bias)

»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

edu rounds always bring me fear

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

Hoping for the final +14 for purple!

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Ah well, C really threw me off. Guess next contest then.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GL everyone

»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Damn that Problem C is a good one. (T_T)

»
12 months ago, # |
Rev. 3   Vote: I like it -16 Vote: I do not like it

Another great problem C in educational round.

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

    I got TLE! Created 5 arrays according to string sizes.
    Accordingly, there will be 4 pairs that produce even sums ((1, 3), (1, 5), (2, 4), (3, 5)).
    Also, count among themselves meaning among array of length 1, 2, 3, 4, and 5.
    Got TLE for this!

    Any leads how to solve it?

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

      1) We can observe that two strings i,j will be lucky only if their parity is same since we want even length ticket.

      2) So we can solve separately for odd (1,3,5) and even (2,4) since max length is 5 only. Now we just need to see among even and odd, let me consider even case. The combinations possible are 2+2, 2+4, 4+2, 4+4.

      3) Since we want both halves to have same value, for 2+2 and 4+4 case, we will simply use map to store strings with same value and add it to answer. For example if there 3 strings of length 2 with value as 5 (maybe 23,14,32 etc...), then for each we will add 3 since we can concatenate to itself. This case will be same for 1+1,3+3,5+5.

      4) Now for special cases like 2+4, 4+2 we just need to check what is the relation for example in 2+4 case, let ticket be ab+cdef. We want a+b+c = d+e+f, which is same as a+b = d+e+f-c. So we for every 2 length string we will add number of 4 length strings whose d+e+f-c = value of current 2 length string.

      5) You can consider different cases like this for example in 3+5 case we want number of 5 length strings such that their last 4 — first digit = value of 3 length string.

      Hope this helps

»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

E's statement is worse. Furthermore, it would be helpful to have an example or explanation provided for the problem

»
12 months ago, # |
  Vote: I like it +14 Vote: I do not like it

implementationforces

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D is goated

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

How to solve D?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    you can observe that $$$a_{1} ⊕ a_{i} = b_{1} ⊕... b_{i-1} .$$$ Thereafter try to find $$$b_{1}$$$ bitwise

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

»
12 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Today's D problem is easy if you remember this problem exists

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ig you are talking about the hard version because easy version can be solved using bitmask dp

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to choose $$$b_0$$$ in D? Any observations, brute force approaches?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint — You have to choose each bit of b0 independently.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Determine if each bit of b0 should be 1 or 0 by comparing with how many 1s should exist in the final array.

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

    First initalize it with 0, and caluclate every $$$b_i$$$. Notice now that if you flip a bit in $$$b_0$$$ for ever $$$b_i$$$ that bit flips as well. We can precalculate the number of apperences for each bit in the solution of correct $$$b$$$. Now we can simply compare the occurences of bits in our current solution and the number of bits in the correct solution. If they are the same we do nothing, else we flip.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Very smart approach! I used a very stupid 01 trie solution...

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        me too but i think it's not stupid and easy to think and implement(

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you please explain how does a trie help here?

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

          Let:

          $$$c_{1} = a_{1}$$$

          $$$c_{2} = a_{1} \oplus a_{2}$$$

          ....

          $$$c_{n - 1} = a_{1} \oplus a_{2} ... \oplus a_{n - 1}$$$

          The trivial solution would be we iterate $$$b_{1}$$$ from $$$0$$$ to $$$n - 1$$$ and find out the maximum value of $$$b_{1} \oplus c_{i} (1 <= i <= n - 1)$$$ by brute force. If this value is less or equal than $$$n - 1$$$, then we successfully find out a valid $$$b$$$.

          However, the algorithm above is $$$O(N^2)$$$ To optimize it, we can use the 0-1 trie. Insert all the $$$c_{i}$$$ to a trie from the highest bit to the lowest bit. Then, we can obtain maximum value of $$$b_{1} \oplus c_{i}$$$ by traversing this trie rather than brute force. The time complexity becomes $$$O(NlogN)$$$

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

    From b[i]^b[i+1] = a[i], we can deduce b[i] = b[1]^a[1]^a[2]^...a[i-1]. Since, the answer always exists all prefixes a[1], a[1]^a[2], ..., a[1]^a[2]^a[3]^...a[n-1], will be unique. So just fix b[1] and check for maximum and minimum XOR

  • »
    »
    12 months ago, # ^ |
    Rev. 3   Vote: I like it +62 Vote: I do not like it

    Most likely people will tell you a solution which considers each bit separately (it is easier to code), but when this problem was proposed, I solved it in a different way

    Spoiler
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I mean, you can just bruteforce for all values of $$$b_1$$$ in $$$[0,n)$$$ and output the one where $$$max=n-1$$$ and $$$min=0$$$, right? That should be trivial using a binary trie storing all prefix XORs.

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Also i don't think it is required to check the min , checking max is suff ig

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Isn't that the exact same thing as what the parent comment from BledDest says?

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          BledDest's method focuses on which index to change to $$$0$$$, my method focuses on the literal value of $$$b_1$$$. Kinda similar I guess.

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            BledDest's method focuses on which index to change to 0 , my method focuses on the literal value of b1 . Kinda similar I guess.

            Are we reading the same thing? Quoting him...

            Iterate on the first element in the resulting array (let it be x ).

            The first element of the resulting array IS b1. So he's saying the EXACT same thing. (I hope I am not wrong here, it would indicate my final brain calls have finally passed away)

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

              For what can come as the first element he is using whatever is in the array, I am using literally the interval $$$[0,n)$$$. Little details do matter

              • »
                »
                »
                »
                »
                »
                »
                »
                12 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                For what can come as the first element he is using whatever is in the array,

                That is not specified anywhere in his comment?

                I (reasonably) assume he means iterating over x in [0, n) only.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  "find the maximum value of $$$x⊕c_i$$$ with descent on the trie"

                  That's the part implying he is using the prefix XOR values as $$$b_1$$$. Yeah I apologise, the difference in detail is too minor (just a small implementation advantage)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Oh no need to apologise, I simply wanted to confirm my understanding, I often second guess myself otherwise.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How does solving each bit independently gives correct answer? We also need to ensure that those bits need to appear in correct combination with each other. For example,(in bits), 000, 001, 010,011,100. And 000, 001, 010, 000, 111. Both have same frequency of each bit but they occur at different positions.

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        If some bit $$$x$$$ has the same frequency of $$$0$$$'s and $$$1$$$'s in the resulting sequence no matter how you choose it in the starting element, then it means that $$$n$$$ is divisible by $$$2^{x+1}$$$; and if we flip it, every number in the sequence just transforms from $$$b_i$$$ to $$$b_i \oplus 2^{x}$$$, which is a bijection when $$$n$$$ is divisible by $$$2^{x+1}$$$.

        So, any such bits in the answer can be flipped without breaking anything.

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

          My question is different. You are answering when frequency of a bit x is same in a set of numbers. My question is: There can exist 2 sets of numbers where frequency of each bit in the two sets are same but the sets are not same. S1 = {00,01,11}, S2 = {10, 01, 01}.

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            Since b[0] ^ b[i] = a[0] ^ a[1] ^ ... ^ a[i — 1], if you fix ith bit for b[0], then ith bit of b[i] is uniquely determined.

            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes, it is uniquely determined but how will you ensure that it is 0,1,2,3,4,...,n-1 only and not something else?

              • »
                »
                »
                »
                »
                »
                »
                »
                12 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Suppose at ith bit there are a $$$ 0's$$$ and b $$$1's$$$ in $$$0,1,...n-1$$$ and p be the number of $$$1's$$$ at ith bit in prefix array. Then you can check if $$$ith$$$ bit of $$$b_{1}$$$ can be 0 if $$$p=b$$$ and $$$a>0$$$ otherwise it will be 1.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                If we know the total quantity of $$$1$$$'s in each bit, we know the sum of all numbers. And for every set that is different from $$${0, 1, 2, \dots, n-1}$$$, its sum is strictly greater than required.

      • »
        »
        »
        »
        12 months ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        That's how I reason about it:

        For $$$i$$$-th bit of $$$b_1$$$, the necessary condition is that $$$b_1, b_1 \oplus b_2, b_1 \oplus b_3, ..., b_1 \oplus b_n$$$ has the same number of set bits as sequence $$$0, 1, ..., n - 1$$$.

        The only way for this condition to not be sufficient is if setting any bit for $$$b_1$$$ works.

        That can only happen when there are initially more 1 bits in sequence than 0 bits (specifically there is one more 1 bit), which can't happen due to the nature of $$$0, 1, ..., n - 1$$$ sequence (at any n, number of 1 bits is not greater than number of 0 bits)

        EDIT: i wrote some bullshit. Setting any $$$i$$$-th bit in $$$b_1$$$ works, if n is divisible by the $$$2^{i + 1}$$$, and it doesn't affect the answer, because there's always pair $$$(x, y)$$$ in $$$0, 1, ..., n - 1$$$, such that $$$x \oplus y = 2^{i}$$$

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

      Considering each bit separately is also much easier to reason about, because the condition "every prefix xor of $$$a$$$ should have same number of set bits as sequence $$$0, 1, ..., n - 1$$$" is sufficient and quite natural to get across

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

      how we ensure that the elements of the array will be unique?

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

        for a solution $$$x_0$$$, if the resulting array has any $$$i,j$$$ such that $$$(x_0 \oplus c_i)=(x_0 \oplus c_j)$$$, then $$$c_i = c_j$$$, which means for any value of $$$x$$$, $$$(x \oplus c_i)=(x \oplus c_j)$$$, therefore there won't be any solution at all, which contradicts the constraint in the problem.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why should problems like C appear in CF?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell what the approach was for C. I was doing a 0(n2) but it was giving a TLE. Without checking all the combinations how is it possible?

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      any target number would be at max 10, iterate over each number

      Ex, 93746

      9 3746 => (3+7+4+6) — (9), here we will check if we have any three-digit sum with this sum

      Similarly, we will check for: 93 746 937 46 9374 6

      Also, we can add a number from the backside as well, so check for suffix as well.

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes but how will you check in less than O(n^2) that"s my doubt

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Used trie, looking for solution that doesn't use it

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

      iterate over lengths of parts and then over largest of them => you can deduce sum of digits of smallest one (precalc them all)

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      since the maximum number of place is 5 you can just hash all option and then check for the correct ones.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They should have given a smaller test case to fail the solution where (i,j) and (j,i) both does not satisfy. Wasted too much time thinking it was symmetric.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good contest

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1895/submission/231204890 , Can anyone tell me why I am getting TLE , Sorry I am just dumb !

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because it is O(n^2)

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution is $$$O(n^2)$$$ if there are n/2 with length 4 and n/2 with length 2.

»
12 months ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

I like problem C, even though I have not solved it because I had overcomplicated implementation.

»
12 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Can anyone hack this? I did a randomized solution to D:

https://codeforces.net/contest/1895/submission/231206864

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you hack a randomized solution? I can get your code to fail against some tests on my local machine, but if I try to hack you then it'll fail since the seed is different on the grading server. Is there any way to determine what the seed would be on the grading server? If not, then I don't think your solution is hack-able.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      If everyone creates an unique test case, then he will be hacked for sure.

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

    What does randomized solution mean?

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

    Done

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Is there a way I can see the test case?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    N=2**16+1 input b[0] = 2 ** 16 b[i]= i xor b[0]

    answer must be: a[i] = i

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cannot find a good solution for D and bashed trie.

»
12 months ago, # |
  Vote: I like it -25 Vote: I do not like it

I'm not sure if this problem https://leetcode.com/problems/decode-xored-permutation/ is like today's problem D. These two questions are too similar. I think some people may have just modified the code a bit and moved it over, but I believe everyone wouldn't do that.

But this really affects my mood. In fact, I was looking for the problem for almost half an hour and I finally found it when the contest has finished for 30 seconds. Hope I will see every problem next round new, not existing.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    I'm going to return to Specialist!!! Ah I'll never take a part in any edu. round anymore!!!!

    screaming

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

    it's kinda easy when n is odd (you can simply calculate first element knowing xor of all of them), but could not find proper solution when n is even >_<

    was sure that optimized n^2 goes through, but spend toooooo much time making up formulas

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there any way to actually calculate b[0] in problem D ? I tried to compute XORs from 0 throught n-1, and it is equal to XORs of all prefixes ^(n times) b[0] . But sadly it doesn't help when n is even.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't exactly know why your solution is correct for odd $$$n$$$, the way I found $$$b[0]$$$ is first to find the prefix XOR of the array $$$a$$$. Then count the number of occurrences of each bit in the prefix XOR array. Compare it with the number of occurrences of each bit from $$$0$$$ to $$$n - 1$$$.

    The bits whose number of occurrences is not equal should be in $$$b[0]$$$. (We can see that if the number of occurrences of some $$$i$$$-th bit is $$$k$$$, then choosing that bit in $$$b[0]$$$ will change its number of occurrences to $$$n - k$$$.)

    The remaining numbers can be calculated easily.

»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

for G, splay tree: TLE Red black tree: AC(500ms)

don't know why :(

»
12 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Two solutions that look similar 231191280 231185745

»
12 months ago, # |
  Vote: I like it +36 Vote: I do not like it

How can I solve F?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    Count number of arrays with minimum element $$$<x+k$$$ then subtract out number of arrays with max element $$$<x$$$. To do first part consider the number of difference arrays on $$$n$$$ elements, $$$(2k+1)^{n-1}$$$ then consider that you can shift the array up/down to decide where the minimum element will be with $$$x+k$$$ options. To find what we need to subtract out I did matrix expo.

  • »
    »
    12 months ago, # ^ |
    Rev. 5   Vote: I like it +43 Vote: I do not like it

    Let an array $$$a$$$ be good if

    • $$$a_i \ge 0$$$ and
    • $$$|a_i - a_{i-1}| \le k$$$

    Now the answer is equal to (the number of good arrays that contain an integer in range $$$[0, x+k)$$$) minus (the number of good arrays that only contain integers in range $$$[0, x)$$$).

    The number of good arrays that contain an integer in range $$$[0, x+k)$$$ is equal to $$$(x + k) \cdot (2k + 1)^{n-1}$$$

    Proof:

    The number of good arrays that only contain integers in range $$$[0, x)$$$ can be calculated with fast matrix exponentiation:

    Let $$$A[n]$$$ be an $$$x \times 1$$$ matrix where $$$A[n]_i$$$ is equal to the number of good arrays of length $$$n$$$ that only contain integers in range $$$[0, x)$$$ with final element equal to $$$i$$$.

    The number we want to calculate is $$$A[n]_0 + A[n]_1 + \dots + A[n]_{x-1}$$$.

    Clearly, $$$A[1]_0 = A[1]_1 = \dots = A[1]_{x-1} = 1$$$.

    Let $$$M$$$ an $$$x \times x$$$ matrix: $$$M_{ij} = 1$$$ exactly when $$$|i - j| \le k$$$.

    We can notice that $$$A[i+1] = MA[i]$$$. This means that $$$A[n] = M^{n-1}A[1]$$$.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thnak u so much for your detailed explanation!

      But how can you come up with that? I just cannot think of this bijection myself.

      Is there some basic logics under it or any problems similar to this problem?

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

      I have another way to argue why the number of good arrays contain a element in $$$[0, x + k)$$$ is $$$(x + k)(2k + 1)^{n - 1}$$$.

      consider fixing the difference array of $$$a$$$, clearly there are $$$(2k + 1)^{n - 1}$$$ ways to do this, then for each difference array, we can add the whole array with any integer(that is, translate the array horizontally), and let focus on the minimum of this array, clearly it must be no less than $$$0$$$ and less than $$$x + k$$$ to be a good array, so for a difference array, there are $$$(x + k)$$$ ways to do that, thus the number of good array is $$$(x + k)(2k + 1)^{n - 1}$$$.

»
12 months ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

[ Deleted ]

»
12 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Is there a case for D where the elements in the answer array can satisfy all the XOR properties, and whose sum is equal to the sum of [0, n-1], but is not correct? As in some elements might have duplicates and the max element can exceed n-1. My solution goes over the 2^19 ways to either set the ith bit in the first element on and off for each of the 19 bits. Then I just check the total sum in o(1) time for all of these ways to see if it matches the intended sum.

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

    Such a counterexample is not possible. The fact that a solution exists guarantees that all arrays you can generate consistent with A have distinct elements. There is only 1 possible sequence of N distinct integers that has the same sum as 0+1+2+..+N-1, so your solution works.

    You can prove this more formally by noticing that given A, the generated sequence B is determined entirely by the choice of the initial element B[0]. More formally, we can define B(n) as the candidate sequence B that starts with n:

    B(n)[0] = n
    B(n)[i] = B[i - 1] ^ A[i - 1] = n ^ A[0] ^ A[1] ^ .. ^ A[i -1]  (1 ≤ i < N)
    

    Then it's clear that B(x)[i] = B(0)[i] ^ x, and therefore B(y)[i] = B(x)[i] ^ (x ^ y).

    It follows that if there is any value of x such all elements of B(x) are distinct (which the problem guarantees), then for all x, all values of B(x) must be distinct, because you can't make two distinct value equal by XOR'ing them with the same constant.

»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Why did the problemsetters use setTestCase in the validators for single-test problems C and D (and also in some other problem recently)? Samples look ugly, and the use of this function here is pointless.

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

    There are no setTestCase calls in either of them. Idk why it became ugly on cf recently, but I also noticed that.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ideas
A There can be two cases 1. When x >= y In this case we can just move along the path and pick the key until we reach the chest. 2. When x < y In this case we can greedily pick the chest when we see it until k + x <= y Then we can traverse the leftover distance twice to reach the chest again. So basically min(k + x, y) + 2 * (y - min(k + x, y))
B To get the min path just sort the array choose first N points as X coordinates of each pair Choose the next N points as Y coordinates.

C A thing to notice is that O + O = E & E + E = E. Keeping this in mind the only way we can get even lengths are := 1 + 1, 1 + 3, 3 + 1, 1 + 5, 5 + 1, 2 + 2, 2 + 4, 4 + 2 To find these pairs fast you can notice for the S(s(1) + s(3)) the sum S[0,1] is nothing but s(1) + s(3)(0) and for S(s(3) + s(1)) the second sum is s(3)(2) + s(1). Similarly form these formulas for all other pairs and store each unique sum is 5 seperate maps (Since size of string is atmost 5).

»
12 months ago, # |
  Vote: I like it +7 Vote: I do not like it

awoo For Question D of today's contest, my submission had wrong answer on test 2, Test 2 was part of the samples, but still I got penalty for submitting a code that gave a wrong answer on samples, please look into it

Thank you

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Took too much time to solve C :(

»
12 months ago, # |
  Vote: I like it -11 Vote: I do not like it

In Problem E, is the card returned to the hand of the player who beat the opponent's card?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    From the statement:

    After a card is beaten, it returns to the hand of the player who played it. It implies that each player always has the same set of cards to play as at the start of the game.

    Does this not answer your question?

»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anyone please explain C?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Each combined ticket consists of two snippets ("snippets" meaning strings in the input). There are three possible cases:

    1. The two snippets are equal length, e.g. "123" + "222" = "123222" ($$$1+2+3 = 6 = 2+2+2$$$).
    2. The left snippet is longer than the right, e.g. "1234" + "11" = "123411" ($$$1+2+3=6=4+1+1$$$).
    3. The right snippet is longer than the left, e.g. "26" + "1234" = "261234" ($$$2+6+1 = 9 = 2 + 3 + 4$$$).

    Define count(len, sum) as the number of snippets in the input that have length len and the sum of the digits is sum. It's easy to precalculate and store these in an array count[6][46] or something (since length is limited to 5, and therefore sum of digits is limited to 45).

    Now for each snippet, consider how many of each of the three cases you can generate.

    For case 1, a snippet s with length l and sum s can appear on the left side exactly count(l, s) times (i.e., it can be paired with each snippet [including itself!] that has the same length and digit sum). That's the easy case. (You might ask: what about when s appears on the right side? Ignore that case to avoid double counting.)

    For case 2, a prefix of s of length k will be the first half, and the remaining digits will be part of the right half. So for example, if we have s="1234567" which has length 7, we can construct tickets "123456|7abcde" or "12345|67abc" or "1234|567a" (where '|' marks the middle). Consider the first one: "123456|7abcde". Here, the left side has sum 1+2+3+4+5+6 = 15, so the right side must have the same sum. The right side already has a 7, so the remaining 5 digits (*abcde*) must have sum 15-7=8. So the number of tickets of the form "123456|7abcde" is count(12-7, 1+2+3+4+5+6-7). Similarly, the number of tickets of the form "12345|67abc" = count(10-7, (1+2+3+4+5)-(6+7)) You can generalize this to something like: $$$count(|s| - k, \sum s_{1..k} - \sum s_{k..|s|})$$$ for all $$$|s|/2 < k < |s|$$$.

    Case 3 is exactly the same as case 2 but using suffixes instead of prefixes.

»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

this contest proved how bad i am at implementation.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide test cases for problem C? I'm struggling to come up with good ones to test my code. Thank you.1895C - Torn Lucky Ticket 231207578

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was anyone able to pass a randomized solution for problem D?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?i have no idea? need help

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    For each number, calculate the length,the length of the first half and the sum of digits in the first half of the prefix it needs as a suffix,and put them in a three-dimensional bucket. Then use all the numbers to match these as prefix. 231178050

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?__

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

    The problem says that once a card is beaten, the player draws it back, so it is always optimal to play the best card $$$b_j$$$ against a card $$$a_i$$$ such that attack of $$$b_j$$$ > defense of $$$a_i$$$, and the defense of $$$b_j$$$ is maximum among such possible cards. This means we can make directed edges among the cards of Alice and Bob.

    Those cards for which there are no possible opponent cards which beats them, are considered to end the game. Now, as we have a directed graph, we can easily use dfs to find out which the result for every card $$$a_i$$$. Note that, for every component in the directed graph, there would be at most one cycle in that component.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the question D of this contest, when can ai be equals to 2*n.

Is it even possible, If yes then the case??

As max value of A^B is A+B but not for A==B. Please help

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's impossible but he promised that it's always possible to construct at least one valid array b from the given sequence a.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I figured out that we only need to find b1 as all other values can be derived from b1 since b2 = a1 ^ b1, b3 = a1 ^ a2 ^ b1 ... bN = a1 ^ a2 ^ ... ^ aN-1 ^ b1. But I can't find fast way to determine if a b1 if valid how did you do that or if you have any other idea?

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can just enumerate it, and try to check the answer in $$$O(\log n)$$$.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why am i still unrated for this contest?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    now it is showing that i haven't even given this contest . What is happening?

»
12 months ago, # |
  Vote: I like it +45 Vote: I do not like it

What happened on problem E? Why are there many judgement failed?

»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

What's wrong with problem E?

Everyone got Judgement failed in system test.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think the standard solution of problem e may be wrong

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

now it is showing the contest but no change in rating.

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

    That is common. All of these kind of contest(div3, div4 and edu) have an open hack. And the rating change will be much slower.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh thanks . But will it show unrated until the rating is changed or does it show unrated if the rating won't change at all.

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It show unrated until the rating is changed.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem can easily be solved by https://www.geeksforgeeks.org/find-maximum-xor-given-integer-stream-integers/ and i read some comments saying that it was like another problems i think thats not ok that problems repeated

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think D is not repeated because the main focus of this question is to transform it into "find the max after xor given integer". It is easy to solve the latter lol.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The reduction to this basic 01trie trick requires some non-obvious steps, such as taking the prefix sum, then proving that the prefix sum must be unique, and finally reducing it to the condition of max XOR-sum $$$\leq n-1$$$. And also that problem on leetcode only involves the case where $$$n$$$ is odd, which is trivial and imo does not provide additional insight to the even case.

»
12 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Why are they not judging E? Did someone TLE/RE Hacked the main solution or smth?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    It was a hack with a java21 generator, but the judging system wasn't re-configured to support them. I already fixed it.

»
12 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Isn't it a bit late for not putting Editorial?

»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Why not release full 5-hour version of a regional contest? What's the point in spoiling half of the problems?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think 5h for a rated contest is too much because of time zone difference and usual life stuff that might take over and not let many fully concentrate on the contest for so long

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For F,why can (k — x + 1) be more than n.The situation doesn't follow condition 1.

»
11 months ago, # |
Rev. 4   Vote: I like it +2 Vote: I do not like it

MikeMirzayanov and awoo, User ALL_LOWERCASED, Sir-Ahmed-Imran and I got the solution of the problem D skipped because of similarities. But the code of the Trie which was common was taken from this website, the code which we used is at the bottom of the page.The code was available before the contest.