JuanPabloAmezcua's blog

By JuanPabloAmezcua, history, 3 weeks ago, In English

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
  • Vote: I like it
  • +134
  • Vote: I do not like it

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

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!

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

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

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

    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.

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

I love this key takeaways thing

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

    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.

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

      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 ?

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

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

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

        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.

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

          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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (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

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            3 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

285980247

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

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

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?

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

    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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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"

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

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

            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.

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

            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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              I get that. Thanks

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

B was same as this Codechef Problem lol

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

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Great way of writing Editorial

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

the contest was near to shit for me :)

but the editorial is one of the best ones.

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

    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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guessed the awnser. getting AC was the proof

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Based.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

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

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

https://codeforces.net/contest/2022/submission/286452965

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

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

code
»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

submission link:check out