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
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
Nice one!
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.
Authors solution is wrong in all problems, didnt yoy read the announcement?
ignore the announcement. can you explain the logic for this question ??
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.
i did the same thing but it did not worked
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.
can anybody help me in C? I did it using a Fenwick tree. 70174969
Cannot see your submission
submissions are not public :(
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
can elaborate a bit more? what do you mean by new array?
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... }
thanks, AC :)
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?
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.
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.
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 :)
Aren't you experienced enough contestant to use structs so that you are invulnerable to any bugs like this?
struct bad. class good.
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... :(
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 :)
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}$$$
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?
My assumption is that in case of tie you choose the least indexed vertex instead of the greatest
I've tried both, but no luck.
Same here :( I got correct results on 11/12 open tests and failed test 10 :(
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 :)
The difference is how multiple edges are handled.
In your solution, all edges are kept, while in mine, only the lowest is kept.
What does the word 'distance' in problem D mean?
I did J by hand, deducted each if statement starting from top to bottom.
HANDFORCES B)
When the test cases and other's codes will be available to see? I want to know what I'm missing.
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.
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....