Блог пользователя JuanPabloAmezcua

Автор JuanPabloAmezcua, история, 6 недель назад, По-английски

Hola Codeforces community! Sorry for the delay, we were solving some details of our national contest. We hope you enjoyed and learned a lot from this contest, we made it with much love. Our team worked day and night these last days to make sure you had a valuable experience :)). If you have any doubts about the editorial, please let us know in the comments, we are happy to help you. The editorial was prepared by jampm and me. Btw, best meme of the round.

2022A - Bus to Pénjamo

Step 1
Step 2
Step 3
Code:
Key Takeaway

2022B - Kar Salesman

Step 1
Step 2
Step 3
Alternative Solution
Proof 1
Proof 2 (by Errorgorn)
Code:
Key Takeaway

2022C - Gerrymandering

Step 1
Step 2:
Step 3:
Step 4:
Code:
Key Takeaways

2022D1 - Asesino (Easy Version)

Hint 1
Hint 2
Hint 3
Solution to D1
Code:

2022D2 - Asesino (Hard Version)

Hint 4
Hint 5
Hint 6
Hint 7
Hint 8
Hint 9
Solution
Code by Marckess:
Bonus
Main takeaways

2022E1 - Billetes MX (Easy Version)

Hint 1
Hint 2
Hint 4
Hint 5
Hint 6
Hint 7
Hint 8
Answer to hint 8
Hint 9
Answer to hint 9
Solution
Code:

2022E2 - Billetes MX (Hard Version)

Please read the solution to E1 beforehand, as well as all the hints.

Solution 1
Solution 2
Code by Marckess:
Bonus
Main takeaways
Разбор задач Codeforces Round 978 (Div. 2)
  • Проголосовать: нравится
  • +142
  • Проголосовать: не нравится

»
5 недель назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

The solution code for Problem C shows "you are not allowed to view this page" error. If it opens for anyone, can they share the code in comments!

»
5 недель назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to use B's Alternative Solution(binary search) to solve this problem?

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    The one I saw consisted in simulating the construction presented in the formal proof (just that W=value_being_processed_in_the_binary_search) making sure you don't sell two cars of the same model to the same customer and that all the cars will be sold.

»
5 недель назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

I love this key takeaways thing

»
5 недель назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

For E1/E2 about checking the validity of the grid , why is the following statement true.

We can deduce that if there is a cycle with xor of weights distinct to 0 in this graph, there would be a contradiction, and arrays X and Y can't exist

  • »
    »
    5 недель назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Cycle in this graph looks like this r1-c1-r2-c2-r1,we know that each edge has a weight equal to value of ricj(connecting edge i-j). Let's see what will be the cells in the grid are in this cycle => r1c1 , r2c1 , r2c2 , r1c2 , This actually corresponds to a rectangle in the grid, and we know the xor of corners must be zero , so any cycle must have a zero (path)xor for there not to exist any contradiction.

    Update :)

    R1 — C1 — R2 — C2 — R3 — C3 — R1 => should be zero (This is not a rectangle anymore)

    Proof ( if i am not wrong ) :-

    Instead of going directly from C2 to R3 , we can go from C2 — R1 — C2 — R3 (path xor from C2 to R3 remains same , as C2 to R1 and R1 to C2 cancels off).

    R1 — C1 — R2 — C2 — R1 — C2 — R3 — C3 — R1 now dividing above path to two parts

    R1 — C1 — R2 — C2 — R1 (this is a rectangle , so must be 0 path xor) R1 — C2 — R3 — C3 — R1 (same as above)

    0^0 = 0

    So any cycle can be broken down into multiple rectangles , and we know xor of each rectangle must be zero , so xor of any number of rectangles should be zero.

    Meaning a cycle should have zero xor.

    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      yeah that is true , but the thing that confused my mind was , you can still get a cycle in the graph without having any rectangles in the grid. For example :

      0011

      0110

      1100

      1001

      (0 = unassigned cells , 1 = assigned cells)

      In this grid there is no rectangle , however if you plot the graph you would see all edges form a big cycle. So that means XOR of them should be 0. But why is that ?

      • »
        »
        »
        »
        5 недель назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        Yes you have a valid point and I am as much as confused as you are right now! This is just indicating that I haven't understood that the concept utilized clearly:(

      • »
        »
        »
        »
        5 недель назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        Let's say Row vertices are Ri,column vertices are Ci, now in which ever path we go from Ri to Rj the xor of path is always same, provable with some case work and it is exactly equal to Ri^Rj, Same holds for Columns, now when a cycle is formed it is either Ri to Ri or Ci to Ci , now if the grid is valid, path xor must be equal to Ri^Ri , which is indeed zero.

        Update :)

        R1 — C1 — R2 — C2 — R3 — C3 — R1 => should be zero (This is not a rectangle anymore)

        Proof ( if i am not wrong ) :-

        Instead of going directly from C2 to R3 , we can go from C2 — R1 — C2 — R3 (path xor from C2 to R3 remains same , as C2 to R1 and R1 to C2 cancels off).

        R1 — C1 — R2 — C2 — R1 — C2 — R3 — C3 — R1 now dividing above path to two parts

        R1 — C1 — R2 — C2 — R1 (this is a rectangle , so must be 0 path xor) R1 — C2 — R3 — C3 — R1 (same as above)

        0^0 = 0

        So any cycle can be broken down into multiple rectangles , and we know xor of each rectangle must be zero , so xor of any number of rectangles should be zero.

        Meaning a cycle should have zero xor.

        • »
          »
          »
          »
          »
          5 недель назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          I see , when you rephrase the problem as "can you get any bipartite cycles with xoring a bunch of 4 length bipartite cycles" it suddenly seemed much more reasonable. Playing with the cases , it is easy to realize you can get any length cycles by adding the 4 length cycles next to each other and then when you have the same length you just order the nodes to get the desired cycle. This makes so much sense , Thx for the help.

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why this greedy approach for Problem-B gives WA on test2. 285737349

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    (Copy and pasted from a message I sent in discord)

    The code fails on the following test (example)

    1 3 2 4 4 3

    Optimal strategy: Get 3 customers to purchase cars 1 and 2: 1 1 3 Get 1 customer to purchase cars 2 and 3: 1 0 2 Get 1 customer to purchase cars 1 and 3: 0 0 1 Get 1 customer to purchase car 3: 0 0 0

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks, I was breaking my head for 2 hours. Took a break and while walking read your comment. I missed it earlier somehow : lol

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You're not alone on that, I also spent the entire contest trying to use greedy and I couldn't figure out why it didn't work :(.

        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          nik_exists could you please tell how u found this test case where it was failing ?

          • »
            »
            »
            »
            »
            »
            3 недели назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            This was an example test case where your code went wrong, I don't know if this exact test case is in the system tests (though I'd say it's fairly likely that something like this is there), I simply ran a test case generator and compared the answers of the correct solution to the greedy solution.

            • »
              »
              »
              »
              »
              »
              »
              3 недели назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              where did you find the test case generator ? U wrote it ?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 недели назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Yep, wrote it myself, here's the code if you are interested (outputs the input first, then the expected output second so I can easily put it into CPH)

                Code (warning, this does spoil the solution to the problem)
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 недели назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Thanks a ton for your help. I didn't even know about the CPH extension on vs code. I just downloaded it, and it's gonna help a lot.

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

285980247

Why it is giving WA on test case 2. For Problem B

»
5 недель назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In D1, We know that if ask(i,j)!=ask(j,i) then one of them must be the impostor, However, I'm slightly confused as I queried on pairs that are distinct (i.e 1,n 2,n-1 and so on). Since the grader was adaptive, I declared j as impostor if ask(i,j)!=ask(j,i), since it's possible for any of them to be the impostor and since the queries are independent of the previous ones.

Why do we need to verify again which one is the impostor once we get the above condition?

  • »
    »
    5 недель назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    if query(i,j)!=query(j,i) happens than it is guranted that other than i and j all people are genuine (no one is imposter) so what you can do is query any of other person with either i or j ,suppose u did it with i and result comes same for both(i ,other and other,i) than j would be imposter and i result comes out to be different than i would be imposter .... since n>=3 so answer will always be possible in atmost n+1 queries

    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      See, according to the question, the grader is adaptive (the fixed order isn't decided beforehand) ,so isn't it so that I can claim any one of them to be the impostor and still the answer would be correct?

      • »
        »
        »
        »
        5 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        i don't think that's correct i believe that there is equal probability that any of two could be imposter, so u would have to confirm among them rather than assuming , you should focus on this line "However, it is guaranteed that there exists an assignment of roles that is consistent with all previously asked questions under the constraints of this problem"

        • »
          »
          »
          »
          »
          5 недель назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Yes, my assumption goes in line with the statement! "There exists an assignment of roles that is consistent with all the PREVIOUSLY ASKED questions". Since the previously asked questions were all on entirely different pairs, we haven't eliminated any of the elements from the currently-being-tested pair from the possibility of being the impostor, as all the queries (1,n) (2,n-1) (3,n-2)... are independent of each other.

          Hence my assumption lies in line with the consistency of data on previously asked questions. JuanPabloAmezcua correct me if I am wrong.

          • »
            »
            »
            »
            »
            »
            5 недель назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            ok suppose that after you considered any one as imposter out of two(let u consider u as imposter btw u and v) and you ask one more query (u,1 and 1,u) i am considering that 1 and n query is safe, which means 1,n gave same results for 1,n and n,1. If 1 and u gives same for both (u,1)and (1,u) dosen't this disapproves the assumption which we made earlier that u is imposter and are all the queries still consistent? the answer is no so we do have to verify once again with any other element .sorry for bad English.

          • »
            »
            »
            »
            »
            »
            5 недель назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится

            Your assumption doesn't work because your guess being consistent with all the previous answers is necessary, not sufficient. According to your (very stupid) logic, you could just guess at the start who the impostor is, since technically you didn't ask anything, and it could techinically be anyone.

            • »
              »
              »
              »
              »
              »
              »
              5 недель назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Ahh now that you say it, indeed it's very stupid of me to think so.

              I get that. Thanks

»
5 недель назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

B was same as this Codechef Problem lol

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    I have seen it atleast 3 times now, and x <= 10 is a bit misleading towards a dp approach :(

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think B is a well known problem, I have solved this problem (or some more difficult variant) at least 5 times.

»
5 недель назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Great way of writing Editorial

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

errorgorn beautiful proof for B! I've been thinking for 3 days straight to solve it and never succeeded, but I don't feel sad bc I'm so inspired by your solution!

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

BTW, key takeaway for B is hilarious cuz trying to find the pattern in small cases for this particular problem will take you in the wrong direction with 99% probability.

»
5 недель назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

the contest was near to shit for me :)

but the editorial is one of the best ones.

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Can you explain to me how you came up with the solution for B during the contest? What was the way of thinking, why did you decide to give your solution a try and did you prove to yourself that it would pass all tests?

    Thanks in advance.

    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I guessed the awnser. getting AC was the proof

      • »
        »
        »
        »
        5 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Based.

        • »
          »
          »
          »
          »
          5 недель назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          first i noticed that the answer is atleast MAX number of the array.

          then i tried to make examples that the answer is more then the MAX. after few examples i found that the answer is ceil(SUM / x) and is worked for the samples and i submitted the code

»
5 недель назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

If someone is looking for a BS(binary search) solution for B then here it is

https://mirror.codeforces.com/contest/2022/submission/286452965

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Why this approach of choosing the top x models with maximum left cars every time doesn't work?

code
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why my sol for D1 is giving wrong output format Unexpected end of file — token expected

submission link:check out

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It was really beautiful! Thank you.