Codeforces Round #909 (Div. 3)

12 месяцев назад, # |

hope this round will help me reach cyan

→ Ответить

calebmartim

12 месяцев назад, # |

+21

I really enjoyed your first div 3 round (Codeforces Round 881 (Div. 3)). Very much looking forward to this one =)

→ Ответить

Akizuki_Kanna

12 месяцев назад, # |

Wish I could be a pupil tonight！！！

→ Ответить

ilqw

12 месяцев назад, # |

As a tester I recommend you to participate in round, and don't forget to read all problems statements, it can be usefully)))

→ Ответить

ashiknur

12 месяцев назад, # |

m1, m2, m3 codeforces sites are not working.

→ Ответить

12 месяцев назад, # |

+10

Thx. Very nice round. Enjoyed problem G alot!

→ Ответить

12 месяцев назад, # ^ |

What is so special about it?

→ Ответить

12 месяцев назад, # ^ |

I liked mixture of merge sort tree and dfs. Maybe it was not intended, but i liked my solution.

→ Ответить

12 месяцев назад, # ^ |

I solved same way, it's good problem tho, i'm not saying it's bad problem

→ Ответить

12 месяцев назад, # ^ |

can you tell me ur idea to G ?

→ Ответить

RD_TheCoder

12 месяцев назад, # ^ |

contest running bruh :|

→ Ответить

12 месяцев назад, # ^ |

← Rev. 2 →

Well, lets count $$$tin$$$ and $$$tout$$$ ($$$tin_v$$$ = first time we entered vertex $$$v$$$, $$$tout_v$$$ = time we leaved vertex $$$v$$$ completely). Vertex $$$u$$$ is an ancestor of $$$v$$$ if and only if $$$tin_u \le tin_v$$$ and $$$tout_u \ge tout_v$$$, but $$$tout_v > tin_v$$$, so it brings us down to this condition: $$$tin_u \le tin_v \le tout_u$$$. Now lets make every $$$p_i = tin_{p_i}$$$. Every query we need to see if there is a number from $$$tin_x$$$ to $$$tout_x$$$, that is included in segment $$$[l; r]$$$. This can be done using segment tree in $$$O(log^2n)$$$ per query.

→ Ответить

12 месяцев назад, # ^ |

But why constraints in F are so low? My solution is linear with 10 lines of code...

→ Ответить

12 месяцев назад, # ^ |

← Rev. 2 →

+15

How do you verify that the answer is correct faster than $$$O(n^2q)$$$?

→ Ответить

12 месяцев назад, # ^ |

-9

We build a bamboo tree and just hung $$$n$$$-th vertex to $$$d$$$-th. In this case path from $$$n$$$-th vertex to $$$1$$$-st vertex will be exactly $$$d$$$.

→ Ответить

12 месяцев назад, # ^ |

← Rev. 3 →

+16

You didn't understand my question. How does the contest system make sure that your output is correct faster than in $$$O(n^2q)$$$? They can't assume everyone will use the bamboo solution.

→ Ответить

12 месяцев назад, # ^ |

Oh, okay, i got it now. Thanks

→ Ответить

handsomeliu012

12 месяцев назад, # |

-10

Didn't notice that only people competed in 5+ rounds are rated......

Already spent 1+ hour on the 7 problems

Sad QAQ

→ Ответить

adityagamer

12 месяцев назад, # ^ |

+10

That qualification is for being a trusted participant.

"The round will be rated for all participants with rating less than 1600"

→ Ответить

handsomeliu012

12 месяцев назад, # ^ |

Yeah, I understand the constraint. I really enjoyed the 1+ hour anyway

→ Ответить

rope_and_snake

12 месяцев назад, # |

B,C >> D,E

→ Ответить

BaoCoder613

12 месяцев назад, # ^ |

pC has tedious implementations. I'd say E is quite easy as I solved it in 10 minutes (compared to 80 minutes for C).

However, B and C are easier when it comes to finding ideas. However, proving your idea works and implementing it makes it a lot more difficult, compared to E (can't say anything about D).

→ Ответить

ExplodingFreeze

12 месяцев назад, # |

What's the intended solution to G? The only two solutions I could think of seem completely overkill:

Merge Sort Tree on DFS order times of the inverse values of the permutation.
SQRT Decomposition on whether each node is a parent of at least one node in the buckets $$$[p_1, p_{\sqrt{N}}], [p_{\sqrt{N} + 1}, p_{2 \cdot \sqrt{N}}], \ldots, [p_{k \cdot \sqrt{N} + 1}, p_n]$$$. For the upto $$$2 \cdot \sqrt{n}$$$ remaining nodes that don't lie completely in a bucket check them each in $$$O(1)$$$ using dfs order ancestor checking.

Is there an easier approach?

→ Ответить

12 месяцев назад, # ^ |

Euler's tour

→ Ответить

ExplodingFreeze

12 месяцев назад, # ^ |

This is what I mean by "DFS Order".

→ Ответить

12 месяцев назад, # ^ |

Thats overkill in that? Do dfs?

→ Ответить

Sarthak3204

12 месяцев назад, # ^ |

← Rev. 3 →

Can you explain why my Mo's algo solution gave TLE on test case 15.Submission

→ Ответить

ARMINIUS

12 месяцев назад, # ^ |

I think sack (DSU on tree) is easier

→ Ответить

sp4c3_c0wb0y

12 месяцев назад, # ^ |

← Rev. 2 →

I tried implementing Sack (DSU on trees) along with Segment Tree for point updates and range queries but I was getting TLE'd.

→ Ответить

EJIC_B_KEDAX

12 месяцев назад, # ^ |

Author's solution was MST on DFS order.

→ Ответить

12 месяцев назад, # ^ |

You scared me with MST... I thought you were talking about Minimum Spanning Tree, before i read the editorial...

→ Ответить

https://codeforces.net/contest/1899/submission/233153059

12 месяцев назад, # ^ |

Actually, i have no idea how you can do minimum spanning tree of dfs order... But we'll skip that point

→ Ответить

zhangtianhan

12 месяцев назад, # ^ |

I used a persistent segment tree with DFS order to pass G.

→ Ответить

Ambitous

12 месяцев назад, # ^ |

+12

consider DFN.

We call the dfn interval of the i-th node's subtree is dfn[i] ~ dfp[i]. also we call the dfn[p[x]] is pdfn[x]

So for a query l r x, we're actually querying is there any pdfn[l~r] in the dfn[x]~dfp[x].

We can take all queries offline and use seg tree queries

→ Ответить

Tony1234

12 месяцев назад, # ^ |

+18

It's possible to use small to large merging. Instead of adding a node's ID, add the position in which its ID appears in the permutation. Then a query can just be solved by binary searching on the set of values at each node.

→ Ответить

Honeynutz

12 месяцев назад, # ^ |

I solved it answering query offline with DSU

→ Ответить

650iq

12 месяцев назад, # |

E was easier than B wtf

→ Ответить

elotelo10

12 месяцев назад, # ^ |

Also F was easier than B

→ Ответить

atc

12 месяцев назад, # ^ |

based

→ Ответить

fernandezpalomojosue

12 месяцев назад, # |

← Rev. 4 →

Problem F,on example,2nd test case, in the third query already exist a path with distances 3 between 2 leafs , 5-4-2-3, but the answer wasn't -1 -1 -1.I'm receiving WA veredict for that?

→ Ответить

King_is_here

12 месяцев назад, # |

Greedy-forces :)

→ Ответить

Mehrad2

12 месяцев назад, # |

oh f i just solve G 1 minute after contest time woooooooow

→ Ответить

vector.beginning_of_OI

12 месяцев назад, # |

I finished the G at the last minute, and because I forgot to write "return 0" ,I got compilation error and I passed it only 1 minute after the contest.

→ Ответить

Kolyanchick

12 месяцев назад, # ^ |

it's very sad... Good luck in next rounds. My friend got same situation with E

→ Ответить

Kolyanchick

12 месяцев назад, # |

← Rev. 2 →

-6

In D it's hard to prove that 1 and 2 the only correct combination without same numbers. Bad problem in my opinion.

→ Ответить

harsh-apcr

12 месяцев назад, # ^ |

Its not that hard to prove :

Condition of the problem is equivalent to $$$a_i/a_j = 2^{a_i}/2^{a_j}$$$

WLOG assume $$$a_i>a_j$$$, we get $$$a_i/a_j = 2^{a_i-a_j} \leq 1e9$$$ $$$\iff a_i-a_j <= 30 \iff a_i/a_j \leq 30/a_j+1 \leq 31$$$

$$$2^{a_i-a_j} \leq 31 \iff a_i-a_j \leq 4 \iff a_i/a_j \leq 4/a_j + 1 \leq 5$$$

$$$2^{a_i-a_j} \leq 5 \iff a_i-a_j \leq 2 \iff a_i/a_j \leq 2/a_j+1 \leq 3$$$

$$$2^{a_i-a_j} \leq 3 \iff a_i-a_j \leq 1$$$

→ Ответить

Mehrad2

12 месяцев назад, # |

come onnnnnnn if the time was just one minute moreeeee ohhhhhhhhhhhhhhhhh

→ Ответить

__SAK__

12 месяцев назад, # |

One of the easier contest I've had in a while

→ Ответить

.dragonman164

12 месяцев назад, # |

Problem Statements are too hard to understand.

→ Ответить

_ahmed_tawfik_

12 месяцев назад, # |

-6

low quality problems on Greedy_forces

→ Ответить

gaurangg

12 месяцев назад, # |

-8

In G, if It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 1e5. shouldn't Binary Lifting work?

I got TLE on TC 10. My Submission

→ Ответить

stalkcl

12 месяцев назад, # ^ |

bruh the sum of $$$q$$$ over all test cases do not exceed $$$10^5$$$, not the sum of $$$r_i - l_i$$$

→ Ответить

detective...dots

12 месяцев назад, # |

← Rev. 2 →

D will appear in my nightmares

other than that, the contest was great

→ Ответить

MONISM

12 месяцев назад, # |

Free hack : submission

→ Ответить

650iq

12 месяцев назад, # |

What was the solution to D? I observed something that only 1 and 2 matters.. but couldn't get to the solution

→ Ответить

codack_mayank

12 месяцев назад, # ^ |

ai * 2^aj = aj * 2^ai

let suppose (aj>ai)

2^(aj-ai) = (aj/ai);

now

aj/ai can be max 1e9, so aj-ai can be a maximum of 30,

so now for every ai, chek possibilities for numbers in ai+1 to ai+30;

→ Ответить

ibrahimwq

12 месяцев назад, # |

← Rev. 3 →

O(n log(n)) solution of G using persistent segment tree 233188158

→ Ответить

12 месяцев назад, # |

+19

$$$O(nq)$$$ solution for G: 233198776

Limits $$$n, q \le 10^5$$$, TL=3sec should be non-existent in 2023 :)

→ Ответить

12 месяцев назад, # ^ |

it is hackable right ?

→ Ответить

12 месяцев назад, # ^ |

← Rev. 2 →

I don't think so, it's $$$\dfrac{nq}{8}$$$ because of vectorization, so should be fast enough

→ Ответить

12 месяцев назад, # ^ |

1e10 / 8

is 1e9 and I know that O(1e9) is at least need 5 second to run

→ Ответить

12 месяцев назад, # ^ |

+19

Of course not, $$$10^9$$$ simple operations is very fast on modern CPUs.

$$$10^9$$$ executions of some complicated code is slow, but $$$10^9$$$ processor operations is fine

→ Ответить

12 месяцев назад, # ^ |

← Rev. 3 →

-7

I tested your code ON C++ 17 and the code got TL

→ Ответить

12 месяцев назад, # ^ |

← Rev. 2 →

Pragmas enable vectorization, without vectorization it's just $$$nq$$$, not $$$\dfrac{nq}{8}$$$

And C++20(64) matters because 64bit compiler can handle 8 integers at the same time, while 32bit compiler can handle only four (as far as I understand)

→ Ответить

12 месяцев назад, # ^ |

← Rev. 2 →

thank you for answering my questions

→ Ответить

Sokol080808

12 месяцев назад, # ^ |

sad

→ Ответить

DuongForeverAlone

12 месяцев назад, # |

← Rev. 6 →

D could be solved without knowing the fact that only the combination of 1 and 2 is valid.

The statement equivalents to: Count the number of pair (i, j) such that $$$a_i * 2^{a_j} = a_j * 2^{a_i}$$$. Suppose $$$a_i > a_j$$$, then we have: $$$a_i = 2^{a_i - a_j} * a_j$$$. Knowing this, we can loop for each $$$a_j$$$, how many $$$a_i$$$ could satisfy this equality, and add it to the answer. The case when $$$a_i = a_j$$$ should be handled separately. My solution: submission

→ Ответить

12 месяцев назад, # |

First contest I could fullsolve, wow!

→ Ответить

treasuryonly

12 месяцев назад, # ^ |

You are expert now! Congratulations!

→ Ответить

12 месяцев назад, # ^ |

Thank you!

→ Ответить

AnanasClassic

12 месяцев назад, # |

Really great round! In my opinion, the condition of problem D was too confusing, but the problem is still good

→ Ответить

NguyenDucThanh

12 месяцев назад, # |

← Rev. 2 →

What will i receive when i hack a problem successfully?

→ Ответить

shevlopmes

12 месяцев назад, # ^ |

+25

glory and honour

→ Ответить

treasuryonly

12 месяцев назад, # |

Problem D is fun to understand the statement and enjoyable to solve, I really like it!

Thank you guys for the contest!

→ Ответить

rohitsatpute480

12 месяцев назад, # |

Problem B was difficult to understand

→ Ответить

12 месяцев назад, # |

can anyone tell me why people having fewer solve count and people having same solve count and high penalty have better rank than me. Thanks!

→ Ответить

Just_sri

12 месяцев назад, # |

Which data structure do I need to know to solve G?

→ Ответить

--WhoAmI

12 месяцев назад, # |

Found a cheater Salman_Johir. This 233189111 is his submission. He copied this code from this video's code. Look at the both code. He just has changed the variables' name.

→ Ответить

Medeali

12 месяцев назад, # ^ |

come on problem C is just an application of a known algorithm

→ Ответить

--WhoAmI

12 месяцев назад, # ^ |

Problem C is an application of a known problem, but if you check the code of the video and the code of the cheater Salman_Johir you will see: Their code is exactly same, code with 10-12 lines can be coincident due the algorithm,but if you give it a check you will see every bit of the code is similar.

And this guy's contest number 904 was totally copied and his both solutions were skipped!

Check here

→ Ответить

Salman_Johir

12 месяцев назад, # ^ |

kid,focus on your goal not others.good luck

→ Ответить

12 месяцев назад, # ^ |

This is why you're still newbie. Imagine cheating in div3 rounds. Skill issue.

→ Ответить

NexTopper

12 месяцев назад, # |

very week pretest in problem C

→ Ответить

Gassa

12 месяцев назад, # |

+15

Thank you for the problems!

It's nice there is a short and witty solution to each one (except G).

→ Ответить

nonsense

12 месяцев назад, # |

-8

i got an O(n) solution that was hacked for problem D (TLE). The official solution is O(nlogn). Anyone throw some light on this? https://codeforces.net/contest/1899/submission/233176732

→ Ответить

raidenblackout

12 месяцев назад, # ^ |

← Rev. 2 →

Unordered maps can be hacked because of how collisions are handled. You can use custom hashing functions as parameters to the unordered map to solve that problem.

struct custom_hash {
    static uint64_t splitmix64(int64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(int64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
typedef unordered_map<long long, int, custom_hash> safe_map;

→ Ответить

coderchamp7

12 месяцев назад, # |

My submission for D got hacked https://codeforces.net/contest/1899/submission/233134841. Is it cause I used unordered_map instead of map? :)

→ Ответить

Imran435

12 месяцев назад, # ^ |

Nope, but rather because you are using int to store the number of pairs.

Think about worst case scenario, if I put all the $$$N$$$ values of array $$$a$$$ equal to $$$2$$$, then the number of pairs would be $$$N*(N-1)/2$$$, ain't it?

And $$$N$$$ can be upto $$$10^5$$$, can u store this value in int? or do u need to use another data type?

→ Ответить

coderchamp7

12 месяцев назад, # ^ |

I have defined the macro #define int long long Btw hacked by TLE not WA :)

→ Ответить

Imran435

12 месяцев назад, # ^ |

Oh! I did not see that!!!

Then it must've been the notorious unordered_map collisions resulting in $$$O(N^2)$$$ time complexity from $$$O(NlogN)$$$

→ Ответить

Imran435

12 месяцев назад, # ^ |

Here 233255221 it works by using custom hash for the map.

Never ever use raw unordered_map in contests, always use the above custom_hashed_map.

You can read more about it in this blog.

→ Ответить

Yevsieiev_Mykyta

12 месяцев назад, # |

You didn't write that there would be hacks...

→ Ответить

12 месяцев назад, # |

← Rev. 2 →

got AC on Problem C during contest but got tle on system testing......?isn't its complexity O(n)!!!

Code : 233167945

UPDATE:: got TLE because of "auto" iterator!

TLE : 233167945

AC : 233276048

→ Ответить

12 месяцев назад, # ^ |

No, it's not; you have a nested loop when you iterate through vector v.

→ Ответить

12 месяцев назад, # ^ |

overall it would check not more than n times r nested loop is used for the alternating subarrays so it wont iterate over n time

→ Ответить

12 месяцев назад, # ^ |

Well, then how else do you explain your TLE?

→ Ответить

12 месяцев назад, # ^ |

← Rev. 2 →

For "AUTO" iterator

TLE : 233167945

AC : 233276048

Thank you for replying!

→ Ответить

12 месяцев назад, # ^ |

Either way, your code is not $$$O(n)$$$. Your new submission just passes, when in reality an $$$O(n)$$$ solution would take ~60 ms to pass.

→ Ответить

12 месяцев назад, # ^ |

the exact submission got AC after resubmitting?

AC : 233277883

→ Ответить

m_nature

12 месяцев назад, # ^ |

← Rev. 3 →

+13

Basically, you got unlucky because it got TLE during system testing (There is no guarantee that it will run with the exact same time every time, because computers don't work like that)

But 982ms/1000ms should give you a hint about why there is a high chance it will get TLE and need to optimize your algorithm

→ Ответить

12 месяцев назад, # ^ |

← Rev. 6 →

The AC code passed in 982 ms / 1000 ms, that's very very close to the time limit. Maybe the use of the range-based for-loop had something to do with your code getting TLE, maybe it didn't. We can't really know since if your code is that close to the time limit, even the same exact code can pass on one submission and get TLE on another.

If you're wondering why your "$$$O(n)$$$" solution is on the verge of TLE, it's because you create an array int a[MAXN]; every test case. Creating and initializing an array of length $$$n$$$ is $$$O(n)$$$ and since you're initializing an array of length $$$MAXN$$$, the time complexity ends up being $$$O(t\cdot MAXN)$$$ which is quite slow.

→ Ответить

12 месяцев назад, # ^ |

-8

Same... I guess Its just a system failure :\ 233286944

→ Ответить

12 месяцев назад, # ^ |

-8

Even though I'm using an unordered map. Everything should work just fine.

→ Ответить

12 месяцев назад, # ^ |

-8

And to be honest, I dont even understand why in the contests where the all problem tests are executed during the online sumbmission, the "aftertesting" is the case.

→ Ответить

_Nadaf_

12 месяцев назад, # |

Best contest

→ Ответить

Udit_Mehra

12 месяцев назад, # |

it was interesting. but, i wasted time to search something good to solve problem B, i thought to bruteforce that 'k' at first, as it was.. but don't know why i felt that stupid and moved to C:). Now i saw it's E was easier than that, it was likely not arranged in increasing difficulty :) also, i felt C easier than B.

→ Ответить

12 месяцев назад, # ^ |

B > A, C, D, E, F

→ Ответить

fasarten

12 месяцев назад, # |

← Rev. 4 →

Can someone explain what is wrong with my solution? My O(n) solution for D got hacked https://codeforces.net/contest/1899/submission/233160169

→ Ответить

A4n0n4

12 месяцев назад, # ^ |

I'm not a python user so I can't get you an 100% precise answer but : - I found that dictionary using only string keys are way faster than other dictionaries, this would have been enough to get you an AC : https://codeforces.net/contest/1899/submission/233292415 - It's also faster to use pypy instead of python3 (there is even a warning when submitting a code)

As for the reason of your code being too slow, i tried to rewrite your sum a couple times and couldn't find anything way faster than what you wrote so it's most probably the insertions in the dictionary that are too slow. I saw that the worst insert case is 0(n), which happen if there are tons of conflict in the hashmap. So maybe the hack that got you to be too slow is designed to create lots of conflicting keys... This last part is a guess but I thought the first part was worth sending this answer.

→ Ответить

--Baygesis--

12 месяцев назад, # |

Can anyone please tell why my O(n) solution got tle on problem D. https://codeforces.net/contest/1899/submission/233294769

→ Ответить

https://codeforces.net/blog/entry/62393

12 месяцев назад, # ^ |

→ Ответить

12 месяцев назад, # ^ |

← Rev. 4 →

Yeah, I sure do think that intentionally including the test that will eliminate unordered_map solutions of div3 participants would be great)) Also still have no idea why TL dint't pop out when I ACTUALLY submited.

→ Ответить

12 месяцев назад, # |

Please some help me. my rank in common stading is 2198 But in friend standing and profile contest page it is 2619 and and my rating change is calculated on 2619 rank

→ Ответить

12 месяцев назад, # ^ |

Common standings, when "unofficial participants" is off, doesn't show all rated participants. From the announcement:

Remember, that only trusted Div. 3 participants will be included in official standings. To qualify as trusted participant you need:

Participate in at least five rounds (and solve at least one problem in each of them)
Do not to have a point 1900 or greater in the rating

Regrdless of these extra restrictions, the rouns is still rated for everyone with < 1600 rating. Your rank among all rated participnts is the 2619, but your rank among trusted participants is 2198.

→ Ответить

12 месяцев назад, # ^ |

Thanks bro but i still have a doubt. Participants near 2619 rank have lower solve count than me and participants near 2198 rank same solve count and penalty as mine and still my rank is below to those who have solves less problem than me. Sorry for annoying question and terrible english

→ Ответить

12 месяцев назад, # ^ |

The people around 2619 in the trusted participant standings also have a lower rank among all rated participants:

Your rank among trusted participants (link):

Your rank among all rated participants (link):

Near 2619 located random guy's rank among trusted participants (link):

Same random guy's rank among all rated participants (link):

→ Ответить