Can someone explain for 1970C3 - Game on Tree (Hard) why my submission 260659612 didn't gave TLE?
Maybe number of going parents are limited, but I couldn't find the limit.
And I think these submissions are strange too: 259726359, 259723352.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 162 |
2 | cry | 161 |
3 | maomao90 | 160 |
4 | -is-this-fft- | 159 |
5 | awoo | 158 |
6 | atcoder_official | 157 |
7 | nor | 155 |
7 | adamant | 155 |
9 | maroonrk | 152 |
10 | Dominater069 | 149 |
Can someone explain for 1970C3 - Game on Tree (Hard) why my submission 260659612 didn't gave TLE?
Let's root of tree be node $$$1$$$. Then before queries for each node find out Ron will win or loose if he starts from it and first move is to one of it childs. Store the number of loosing childs of node $$$x$$$ in $$$dp1[x]$$$. If Rone starts on $$$x$$$ node, if $$$dp1[x] = 0$$$ he maybe win if he go to parent of $$$x$$$, else $$$x$$$ is winning and Ron has $$$dp1[x]$$$ childs to go in first move. Fore each query node $$$u$$$ if $$$dp1[u] \neq 1$$$ (Ron will win even if doesn't go to parent, i.e. move to one of $$$u$$$ childs on first move). Else only option to win is go to parent in Ron's first move. Let $$$p[u]$$$ be parent of $$$u$$$. Then Hermione wins if goes to loosing child (which is not $$$u$$$ cause it's activated) when $$$1 < dp1[p[u]]$$$ or $$$(dp1[p[u]] = 1$$$ and $$$dp2[p[u]] \neq u)$$$, else she has to go parent, and Ron will do these with $$$p[p[u]]$$$ too, and so on.
See the code too. I hope there's no problems with my explanation, if so please let me know.
Maybe number of going parents are limited, but I couldn't find the limit.
And I think these submissions are strange too: 259726359, 259723352.
UPD: I suppose no. Thanks lrvideckis for explaining my mistake in this comment.
I think PQ takes too much memory because of what happened in CF Round 923.
In this contest, because of I couldn't solve E, I read F, after some time I found solution. In the end of my solution, I have to find any path from $$$mn.ss.ss$$$ to $$$mn.ss.ff$$$ which doesn't contain a node more than one time, in this code I used dijikstra for it(I don't know why I didn't use bfs). And it used more than 256 megabytes.
Today, I used bfs instead of dijikstra in this code, and I suprised, it took only 43 megabytes. In time 2, in memory 6 times smaller than previous code. I'm sad about I didn't use bfs in contest, but I'm happy about I learned a lesson.
Did you have any experience like these?
I have a request for everyone reading this blog: please post a comment sharing what you do/did for IOI training (or perhaps for other OIs). I'm primarily interested in hearing what you actually do/did, not what you would recommend to someone else who's training for IOI (though if you want to give advice, please feel free to do so).
Which algos, CF rating needed for each medal?
In which rating I should start to try IOI problems?
In which rating I'll be able to get bronze/silver/gold at IOI?
I was trying to solve IZHO14_bank on oj.uz. In problem $$$n, m <= 20$$$ and Time Limit is 1s.
Time complexity of my solution is $$$O(2^m \cdot m \cdot n)$$$. It's $$$TLE$$$ because $$$2^{20} \cdot 20 \cdot 20 = 419 430 400 > 10^8$$$.
My both code have same time complexity but my $$$1^{st}$$$ code is $$$TLE$$$, $$$2^{nd}$$$ got $$$100$$$ score.
Can someone explain why my $$$2^{nd}$$$ code isn't $$$TLE$$$ $$$?$$$
$$$1^{st}$$$ submission https://oj.uz/submission/854216 gives $$$TLE$$$,
$$$2^{nd}$$$ submission https://oj.uz/submission/854864 got $$$100$$$ score.
2 months ago, I posted a blog hoping to find OI groups on CF since most sites are blocked in my country. Unfortunately, I couldn't find.
In CF blogs, for practicing to OIs, suggested is solving easier OIs. But I have only CF with 2017-2023 IZHO, 2002-2023 IOI, and some from gym. I can get some points on IZHO, but I can't solve full and IOI is hard for me.
Is CF enough to get medal at IZHO, IOI?
In which rating I'll be able to solve(get points on) IOI problems? Or isn't it possible to answer?
In which rating I'll be able to get bronze, silver, gold at IZHO, IOI? Or isn't it possible to answer?
I don't know why but in my country many sites are blocked.
oj.uz, atcoder.jp, dmoj.ca, cses.fi, luogu, vjudge.net, qoj, acmicpc.net...
Luckily Codeforces isn't blocked in my country, and I'm looking for OI groups on CF.
If you know such groups please comment it. It will be very helpful.
Update: I can access blocked sites with Tor browser, still it'd be good if I find OI groups on CF because it's a bit slow.
Name |
---|