### Golovanov399's blog

By Golovanov399, history, 4 months ago, ,

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

• +107

 » 4 months ago, # |   +105 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
•  » » 4 months ago, # ^ |   +5 Nice one!
 » 4 months ago, # |   0 J problem O(1) was ment to be here, but i dont have time to add it
 » 4 months ago, # |   0 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.
•  » » 4 months ago, # ^ |   0 Authors solution is wrong in all problems, didnt yoy read the announcement?
•  » » » 4 months ago, # ^ |   0 ignore the announcement. can you explain the logic for this question ??
•  » » » » 4 months ago, # ^ |   0 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.
•  » » » » » 4 months ago, # ^ |   0 i did the same thing but it did not worked
•  » » » » 4 months ago, # ^ |   0 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.
 » 4 months ago, # |   0 can anybody help me in C? I did it using a Fenwick tree. 70174969
•  » » 4 months ago, # ^ |   0 Cannot see your submission
•  » » » 4 months ago, # ^ |   0 submissions are not public :(
•  » » 4 months ago, # ^ |   0 I did it using segmented tree
•  » » 4 months ago, # ^ |   +3 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
•  » » » 4 months ago, # ^ |   0 can elaborate a bit more? what do you mean by new array?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 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... }
•  » » » » » 4 months ago, # ^ |   0 thanks, AC :)
•  » » » » » » 4 months ago, # ^ |   0 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?
•  » » » » » » » 4 months ago, # ^ |   +10 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.
 » 4 months ago, # |   +51 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.
•  » » 4 months ago, # ^ |   +8 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 :)
•  » » 4 months ago, # ^ |   -23 Aren't you experienced enough contestant to use structs so that you are invulnerable to any bugs like this?
•  » » » 4 months ago, # ^ |   -30 struct bad. class good.
 » 4 months ago, # |   +5 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... :(
•  » » 4 months ago, # ^ |   +3 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 :)
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +10 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}$
 » 4 months ago, # |   0 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?
•  » » 4 months ago, # ^ |   0 My assumption is that in case of tie you choose the least indexed vertex instead of the greatest
•  » » » 4 months ago, # ^ |   0 I've tried both, but no luck.
•  » » 4 months ago, # ^ |   0 Same here :( I got correct results on 11/12 open tests and failed test 10 :(
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 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 :)
•  » » » 4 months ago, # ^ |   0 The difference is how multiple edges are handled.In your solution, all edges are kept, while in mine, only the lowest is kept.
 » 4 months ago, # |   0 What does the word 'distance' in problem D mean?
 » 4 months ago, # |   +11 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)
 » 4 months ago, # |   +5 When the test cases and other's codes will be available to see? I want to know what I'm missing.
 » 3 months ago, # | ← Rev. 3 →   0 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.
 » 2 months ago, # |   0 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....