CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)

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

+59

Finally a div1+2 round after half month.

→ Ответить

Liuxizai

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

+15

But the provincial team selection contest will be held in tomorrow morning. I'm going to miss this round :(

→ Ответить

vrintle

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

Isn't this usual nowadays ?

→ Ответить

RecursiveCo

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

+16

Hope I can bounce back from my horrendous performance last time.

→ Ответить

animish01

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

bruhh so like me

→ Ответить

Marky

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

Gl. Hope you dont fail system testing again. (:

→ Ответить

RecursiveCo

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

Thanks ;)

→ Ответить

tibinyte

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

← Rev. 2 →

+50

Nostalgia hit me.

→ Ответить

SATSKY_2024target_IGM

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

+33

My first div1...ready to face the challenge

→ Ответить

hamodyosama

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

so excited !

→ Ответить

CedeaT0

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

As a tester, problems are educational and wonderful, hope everyone can enjoy

→ Ответить

_Hosam

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

+34

TON is about 2.10$, Thank me later :)

→ Ответить

EASON_LI

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

hope to be Expert

→ Ответить

Math_is_Good

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

You are already Expert bro . What are you talking about? This time you will reach it . I will try not to blunder this time.

→ Ответить

MagicalFlower

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

+31

As a tester, give me TON.

→ Ответить

Golovanov399

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

+60

How are the first two letters of your nickname black (at least in chrome mobile)

→ Ответить

dalex

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

+20

Ligature

→ Ответить

CLUMSY_BOT

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

+94

Ultra legendary grandmaster

→ Ответить

oversolver

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

+52

f and l are connected in chrome, so it uses bfs to fill letters!

→ Ответить

BaoGhetTxDongHoa

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

← Rev. 2 →

Hope I will solve A anh B @@ As a participants, hope everyone have the best work!!

→ Ответить

programpiggy

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

-40

I will AK it using Genshin Impact:)

→ Ответить

ballpoint_pen

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

（

→ Ответить

KAREYEV

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

← Rev. 2 →

→ Ответить

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

Gigafrog

Frogachad

→ Ответить

siddhant4583agarwal

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

← Rev. 2 →

Where will these ton tokens be transferred? I mean we haven't filled a wallet address whole registration neither is there a link to put our wallet address on website or any other place.

→ Ответить

great_fortune

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

+33

in past times, the wallet was asked after only those who won something

→ Ответить

mykhail0

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

you can put your ton wallet address in your account settings

→ Ответить

__fn__

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

Can anyone explain why we can read many times ".... give me a TON"?

→ Ответить

jcccc

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

+26

As a tester, I think this contest is very worthwhile to participate in. I hope everyone who join this contest can get satisfactory results.:)

→ Ответить

The_Dragon_Warrior

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

+30

We need a TON of positive delta rating!

→ Ответить

kanomahoro

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

+49

I hope to reach 2100, and I wish everyone all the best!!

→ Ответить

JEE_MAIN_LOOSER

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

Will try to cross 1500 this time. Looking forward to solve upto 4 problems.(atleast 3).

→ Ответить

Sourav.Kumar007

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

← Rev. 2 →

facing long in queue problem!!

→ Ответить

tn757

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

+19

Will a scoring distribution be announced?

→ Ответить

jackylova_fan_fan_fan

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

+28

I'm jiangly fan,jiangly is No.1!!!

→ Ответить

Gaze_n_Miss

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

+15

I really wanna reach 1900 today. The mark has been psyching me out for so long now. I dont wanna care about my rating!!!! I wish me and you all the best!! (I just wish it a tiny bit more for myself :D)

→ Ответить

FARAJI

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

+15

Definitely, you can. Best Wishes.

→ Ответить

zsc985246

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

+19

Where's score distribution?

→ Ответить

zja601

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

+18

Where's score distribution?

→ Ответить

testmayank123

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

What Happened to tourist ?

→ Ответить

franklidev

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

← Rev. 2 →

+21

No worries. Anything can happen. As I'm a tourist fan, I believe that tourist will beat No.1 next time.

→ Ответить

yllo

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

+39

jiangly! best of the best

→ Ответить

Wind_Eagle

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

+21

I'm very excited to see editorial for task H!

→ Ответить

tn757

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

Good round! Sadly I ran out of time for D and I think I would have been able to solve with ~10 more minutes.

→ Ответить

sil.

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

hard round.

→ Ответить

SecondThread

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

+13

Problems were great overall, but needing to use Fibonacci Heap for E in Java to not TLE was obnoxious.

→ Ответить

FlakeLCR

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

+13

standard heap runs fine in pypy

→ Ответить

Tutis

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

What exactly was your solution, you should be able to use bucket sort since values are in $$$[0, n]$$$.

→ Ответить

SecondThread

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

Small to big with a disjoint set, where you merge the smaller priority queue of edges into the bigger priority queue every time you need to merge two nodes.

→ Ответить

Tutis

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

Very convoluted. Suppose you add all vertices with $$$a_i = X$$$ to the graph with all $$$a_i \leq X-1$$$. If you can defeat $$$X$$$, you can defeat the component. If you can defeat $$$X$$$ now, you could have defeated $$$X-1$$$ before, which means you were able to defeat the component. You can maintain if the whole component is defeatable together with its size in DSU.

→ Ответить

fonmagnus

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

+44

Problem B is the same problem as one of the problem in Constructor Open Cup Contest yesterday

→ Ответить

RDDCCD

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

+16

Ah... An interesting coincidence :( The two contests are so close.

→ Ответить

Ra16bit

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

Actually there was a small difference: solution was guaranteed in Constructor Open Cup, and today there was a -1 option.

→ Ответить

jmyszka

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

The time of which of the submissions counts to the result on codeforces? The first or last?

→ Ответить

Sulfox

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

← Rev. 2 →

+96

Historic Submission: https://codeforces.com/contest/1810/submission/200000000

→ Ответить

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

+14

nightcrawler0112 Orz

→ Ответить

nightcrawler0112

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

+26

had it been AC ;) But yeah great achievement!!

→ Ответить

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

+32

B is almost absolutely the same as a problem in Constructor Open Contest 2023 which was yesterday

→ Ответить

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

-8

Submited D in last second but system didnt register it, also B is harder than C or D

→ Ответить

teejorob

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

I just drew a binary tree from 1 and got the greedy idea, and I found B quite easier than C (just my opinion) Didn't even get time to look at D

→ Ответить

Penguin07

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

+10

Problem E is solvable using "Kruskal Reconstruction Tree" technique. The weight of edge (u, v) is max(a[u], a[v]). After we built the tree, we climb from leaves with a[u] = 0 and check if we can climb up to the root in the reconstruction tree.

→ Ответить

Mirali777

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

It's also solvable with Boruvka's algorithm + BFS

→ Ответить

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

+56

I solved it with DSU and merging sets

→ Ответить

wery0

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

+21

Also solvable by shuffling all zeroes and performing BFS from each of them. The only optimization is to start only from zeroes which we had never reached before.

→ Ответить

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

Wow, that is smart. What is the expected complexity of your solution?

→ Ответить

wery0

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

← Rev. 4 →

I would like to know that too.

Edit: Even without shuffling, this algorithm will visit each node at most $$$\log(n)$$$ times. So the upper bound complexity is $$$O(m \log^2 n)$$$. Maybe with shuffling we can get smth better.

→ Ответить

applepi216

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

I did this too: I think it's $$$O(m\log n)$$$ since the expected number of 0s you start from is $$$O(\log n)$$$ and each time you can explore almost all the edges in the graph?

→ Ответить

kanishk779

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

-8

Could you explain how the expected number of 0s we start from are $$$O(log n)$$$ ?

→ Ответить

gabrielliu2001

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

Correct me if I'm wrong, I think you don't need to shuffle the zeroes as the worst case will only visit all N nodes at most log(N) times.

→ Ответить

wery0

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

← Rev. 3 →

Yeah, got it, you are right. So we don't need to shuffle and the overall complexity is at most $$$O(m \log^2 n)$$$ using priority queue inside BFS.

→ Ответить

NeroZein

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

why are we visiting each node at most $$$logn$$$ times ?

→ Ответить

cockatooo

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

← Rev. 3 →

This complexity analysis is so hard. I came up with the solution immediately but didn't dare code it because I though it was $$$O(n^2)$$$. Now I play around some linked-list cases and can see that it is indeed impossible to reach $$$O(n^2)$$$, but can you please elaborate on how to prove $$$O(mlog^2n)$$$?

Edit: it was in the editorial.

→ Ответить

kanishk779

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

-8

I did the same thing. Here is my solution. 200012713

→ Ответить

tgp07

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

I upsolved the prob using a similar strategy, But I didn't realize that that optimization would be enough, so after performing each BFS, I combined all visited nodes into a "super-node" to make sure that i didn't iterate over each node too many times. The core logic is super similar tho.

→ Ответить

vecna

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

Any hints for D?

→ Ответить

Serikbay777

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

try to keep the minimum and maximum possible length of the tree after each query

→ Ответить

vecna

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

thanks, was very close to this just made some calculation mistakes

→ Ответить

Chimpanzee

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

How to do E?

→ Ответить

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


bool isPossible(long long int mid, long long int height, long long int a, long long int b)
{
    if(((a-b)*(mid-1LL)*1LL) + a >= height) return true;
    else return false;
}
long long int calDays(long long int height, long long int a, long long int b)
{
    if(height == 0) return 1;
    if(height <= a) return 1;
    long long int left = 1; long long int right = 1e18;
    while((right - left) > 1)
    {
        long long int mid = left + ((right - left)/2);
        if(isPossible(mid, height, a, b)) right = mid;
        else left = mid+1;
    }
    if(isPossible(left, height, a, b)) return left;
    else return right;
}

In question D, I was trying to find number of days taken by snail to reach height h, given a and b using Binary search. Is something wrong in my approach as I am getting WA in TC5.

→ Ответить

orke2001

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

← Rev. 2 →

probably overflow on (a-b)*(mid-1LL)

→ Ответить

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

← Rev. 2 →

So, taking long long right = 1e9 will solve the overflow issue? BTW I don't think overflow is the problem, because I have submitted the code with a value of right less than 1e9. And still I got WA in TC5.

→ Ответить

orke2001

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

IDK, I did long long right = 2 * 1e18 / (a-b) to avoid this issue

→ Ответить

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

Thanks man! Overflow was problem. Got it Accepted.

→ Ответить

orke2001

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

I think setting right = 1e9 is also bad, for example, when a=2,b=1, h = 1e15

→ Ответить

MuhammadSawalhy

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

Same problem with me! But why BS doesn't work here??????????????

It is equivalent to the direct math formula, both calculate the same.

→ Ответить

https://codeforces.com/contest/1810/submission/200007256

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

It is working well. You just have to be careful of the overflow.

→ Ответить

MuhammadSawalhy

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

← Rev. 3 →

I was already careful! My binary search limits is 0 and 2e9 Submission: 200007394

Update: The problem is that we need the limit to be upto 1e18 which may lead to overflow. Thanks!

→ Ответить

reversir

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

Why did I get WA?

→ Ответить

ayush_n

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

← Rev. 3 →

Can anybody Tell me why my code fail in Problem C

https://codeforces.com/contest/1810/submission/200015122

→ Ответить

EOWL

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

Firstly,You haven't considered all possible start mex values(according to your code you have checked for 1 and 2) and even after this,all possible combinations of insertions and deletions that are possible are not considered (try looking at the editorial or look into my submission for a better understanding of it) Happy Codeing:)

→ Ответить

arthurg

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

Any ideas why this D is failing pre-tests? I spent 1 hour debugging and could not find the bug:

https://codeforces.com/contest/1810/submission/199997167

→ Ответить

fonmagnus

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

I think the tree height can be more than 2e9 (for example if a snail has $$$a = 10^{9}, b = 1$$$ and $$$n = 10^9$$$)

→ Ответить

arthurg

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

thank u !!

→ Ответить

RecursiveCo

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

I got 7 WAs on D trying to use binary search before realizing it was just math...

→ Ответить

rigvedinho

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

← Rev. 2 →

is Div2D solvable with just math?

→ Ответить

Mohamed_Hesham

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

Yes

→ Ответить

huikang

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

← Rev. 3 →

Determining whether a node is good (you can start from the node and reach the entire graph) is just implementation.

The solution of E is quite straightforward when you observe that if a node is not good, the nodes it can reach are also not good.

Edit: Systest accepted, but not sure if there is an test case that will TLE this

→ Ответить

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

← Rev. 3 →

+45

Nice div1+div2 contest. Solved A-E. My solution of F passed pretest but it's very likely to get TLE on system test.

A: We just to need check if there's any i where a[i]<=i.

B: We can only get odd number by operation, so if n%2==0 there's no solution. Otherwise, we can represent (n-1)/2 in binary, and add 1 to all digits (for example: 17 -> (17-1)/2=8 -> 8=1000(2) -> answer is 2 1 1 1).

C: First we can remove all numbers and add single 1, which costs n*c+d. Otherwise, assume the size of the final permutation we get is k (and k>1), and there are m missing numbers in range [1, k] in the initial array. Then we need to add m numbers and remove (n-(k-m)) numbers, the cost is c*(n-(k-m))+d*m = c*n + (c+d)*m — c*k. If we let k+=1 and m+=1 (which means, k+1 is a missing number in the initial array), the cost will increase by d, so in any optimal answer, k must be a number in the initial array. So we can iterate for every possible option of k and get the answer.

D: Implementation problem. We just need to maintain the upperbound and lowerbound of h for each type-1 query, and for type-2 query we need to check if the answer for (h_max, a, b) and (h_min, a, b) are the same. Be careful for case a>=h.

E: DSU. We sort edges (u, v) by the value of max(a[u], a[v]) and add them by this order. First mark all nodes with a[u]==0 as good. WLOG assume a[u]>=a[v]. When mergeing (u, v), if v is good and the size of component of v is not greater than a[u], we mark all nodes in the component of (u, v) good. To defeat all monsters, we need the graph to be connected and all nodes are good.

F: The answer is ceil(log_m(sum(m^a[i]))). We need to maintain the base-m representation of sum(m^a[i])) by a segment tree, and update it by binary search.

Update: Upsolved F with atcoder library: 200024728

→ Ответить

GILGAMESH

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

← Rev. 2 →

Amazing performance today! (despite FST!)

→ Ответить

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

← Rev. 3 →

FST((

Anyways congratulations with almost becoming red!

→ Ответить

great_fortune

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

gratz! Great performance anyway, amazing result of your constant upsolving

→ Ответить

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

Can you please explain logic behind (n-1)/2 in B?

→ Ответить

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

← Rev. 4 →

Let f(x)=(x-1)/2 and see how operations affect f(x):

Operation 1: x --> 2*x-1

f(x)=(x-1)/2 f(2*x-1)=x-1

which is: f(x) --> 2*f(x) (put a 0 after a binary number)

Operation 2: x --> 2*x+1

f(x)=(x-1)/2 f(2*x+1)=x

which is: f(x) --> 2*f(x)+1 (put a 1 after a binary number)

→ Ответить

FARAJI

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

For problem B, I didn't get this point "Otherwise, we can represent (n-1)/2 ". Can you explain a little bit more?

→ Ответить

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

Yeah i dont get it too lol

→ Ответить

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

I think he is trying to say that since number is always odd as we progress from 1 to our desired number n, that we can go from n downwards in this fahsion:

we could get to n etiher by number (n-1)/2 or by number (n+1)/2, whichever of them is odd(other one always isnt) is the number from which we came to n

→ Ответить

XxDantexX

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

Could you (or someone else) please elaborate the logic behind your algorithm for E? I don't seem to understand it at all. Thanks!

→ Ответить

RedDreams

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

+30

Although managed to solve D and probably will get positive delta, still problem D was awful in my opinion. There was nothing interesting about it. It just required being extra careful, which is very annoying.

A was ok, B and C were nice.

→ Ответить

NguyenYinder

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

I don't understand problem D, anyone help me:((

→ Ответить

apt_dpd

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

Me too

→ Ответить

Abito

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

-28

Problem D is really orz

→ Ответить

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

As a contestant who won 4TONs, please give me TONs

→ Ответить

Z-wzy

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

+15

Jiangly!!!

→ Ответить

gabrielliu2001

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

May I know why my problem A's submission is still in pretest passed stage?

→ Ответить

onebit1024

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

weak pretests on E? I passed pretests in 295 ms and seemed to have failed systests :(. Hurts more since I was going to reach CM.

→ Ответить

onebit1024

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

Looks like this is on me. My solution is the same as edi's except I set visited as 0 for all nodes each time I bfs instead of setting visited as 0 only for nodes visited in the last bfs which significantly worsens complexity.

Still sad how the pretests didn't catch this.

→ Ответить

Alex239

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

A round with a 200000000 parcel?

→ Ответить

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

← Rev. 2 →

+31

Congratulate nightcrawler0112 for submitting the 2e8-th solution 200000000 in this contest!

→ Ответить

nightcrawler0112

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

+52

wish it was an AC

→ Ответить

SorahISA

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

+41

Due to a network failure, I accidentally submitted my solution to problem D twice (see 199967726 and 199967904) and got a resubmission penalty. Is there a way to get my score back?

Also, hats off to everyone who prepared this fantastic contest, and I'm excited to finally become red after 5.25 years of cp!

→ Ответить

Dream-On

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

+10

congrats more to see from you

→ Ответить