Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Golovanov399's blog

By Golovanov399, history, 3 weeks 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

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