Golovanov399's blog

Aim Tech Poorly Prepared Contest Editorial
By Golovanov399, history, 5 years ago, In English

We hope that no difficulties, misunderstanding and "wtf am i asked to do" thoughts ruined your fun!

Problem A: Nash equilibrium
Problem B: DAG
Problem C: Segment tree or Fenwick?
Problem D: Dijkstra
Problem E: Amazing bitset

In problems F, G and J we don't mention in the editorial that we assume you to have parsed the statement into a convenient programming-friendly format.

Problem F: Keep talking and nobody explodes -- easy
Problem G: Keep talking and nobody explodes -- medium
Problem H: Who needs suffix structures?
Problem I: Deja vu
Problem J: Keep talking and nobody explodes -- hard
  • Vote: I like it
  • +107
  • Vote: I do not like it

Comments Comments (35)
| Write comment?
»
5 years ago, # |
  Vote: I like it +105 Vote: I do not like it

I feel like I need to add a poorly prepared comment. Sorry I wanted to be more informative but I got no time, will edit later

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone provide a code for problem A. i think tutorial is causing the confusion. can anyone explain what is wrong in my logic ??

i iterated over rows and marked true the cell with maximum value if exists. and the iterated over columns and marked true the cell with minimum value if exists. then printed the first the cell which was marked in both case.

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

    Authors solution is wrong in all problems, didnt yoy read the announcement?

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

      ignore the announcement. can you explain the logic for this question ??

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

        For each row find maximum element(if there are multiple maximum elements, ignore that row), then iterate through its column and find minimum there(there has to be only 1 minimum in column for that element to satisfy all the conditions).Then compare i,j(row,column) and find pair with minimum i and j.

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

        No, but the whole point of the contest was that all the solutions had some bug in them that you had to guess and introduce into your own code. In this case, you had to take m first and then n while taking input.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody help me in C? I did it using a Fenwick tree. 70174969

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

    Cannot see your submission

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

      submissions are not public :(

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

    If were talking about solving the problem correctly, just use segmented tree to apply 2 operations on tree.Authors mistake in solution was that he didnt create new tree and array for each test, he used the same one for all tests which causes massive errors everywhere

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

      can elaborate a bit more? what do you mean by new array?

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

        You create an integer array full of zeros for each test Just like so: //Reading t for(int i=1;i<=t;i++) { cin>>n>>q; int a[n+1]={0}; //Build tree. //Process requests in next cycle... }

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

          thanks, AC :)

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

            Nice. You did it using Fenwick tree? If so, what did you change in correct fenwick solution to make it as incorrect as authors solution is?

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

              I crated a BIT array of maximum length globally, and did all the queries without doing any futher changes. Assume you have queries on a array of 1e5 length , just perform them, forget about the length of the array given. Just use n = 1e5 once.

              → Reply
»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Lol. I problem C when I tried to implement the correct solution first I did define function reset, but forgot to call it, then spent a few minutes wondering: are problemsetters trolling us and there is one problem with correct testcases, or I had really bugged something such simple as Fenwick tree. Assumed it's the former and submited it xD.

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

    Ideally we thought this will happen with each of the first 5 problems with at least one participant, but yet we know such cases only for C and E :)

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    Aren't you experienced enough contestant to use structs so that you are invulnerable to any bugs like this?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -30 Vote: I do not like it

      struct bad. class good.

      → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For E, isn't signed integer overflow undefined behavior? Moreover, i am calculating the answer by $$$\frac{b^n-a^n-(b-a)^n}{b^n}$$$. Does it mean that I have no chance of solving the problem... :(

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

    Sorry for that, it seems so. But you could've bruteforced meaningful ways to calculate this number and also the place where the overflow happens :)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      You can also notice, that if a testcase has a wrong answer then it differs from correct by $$$591263623$$$, which equals $$$2^{32} \pmod {1234567891}$$$

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D, I followed the instructions and chose the greatest distance to update other vertices. I used a boolean array to ensure that any vertex would only be used once to relax other vertices. However, this failed at Test 10. What else should I do?

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

    My assumption is that in case of tie you choose the least indexed vertex instead of the greatest

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

    Same here :( I got correct results on 11/12 open tests and failed test 10 :(

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

    If you are still interested, here is my code. You can probably stress test it against your solution on small test cases.

    if you find the difference, please share it with us :)

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

      The difference is how multiple edges are handled.

      In your solution, all edges are kept, while in mine, only the lowest is kept.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What does the word 'distance' in problem D mean?

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I did J by hand, deducted each if statement starting from top to bottom.

  • First statement : If digit 39 is odd, rotate digit 39 by 9 times, else rotate digit 37 by 1 times.
  • All digits are initially 0, so this IF should result ELSE. But we can see in the output digit 39 is rotated by 9 times and there are no other rotations stated on digit 39, so this statement went through IF. Hence this statement is mixed up.
  • And so on...

HANDFORCES B)

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

When the test cases and other's codes will be available to see? I want to know what I'm missing.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I still don't know why Problem.D get wrong answer on 8, a little bit sad.

I simply use algorithm dijkstra, but I don't how to get passed all datas.

Can someone tell me the reason? Thanks a lot.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone point out thing i am missing in this solution to problem A: Nash Equl. Here is the link : link i can't find any solution....

→ Reply