Educational Codeforces Round 158 [рейтинговый для Div. 2]

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

← Rev. 2 →

B > D > C

→ Ответить

qiu_tianhan

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

I agree

→ Ответить

Dauren_Miras

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

B>D>C

→ Ответить

Dauren_Miras

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

Bro, I'm your fan

→ Ответить

BallBreaker

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

E<A

→ Ответить

Ahmet_Emre

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

me who builded a segment tree on D for no appearant reason

→ Ответить

Ashwini_Tiwari

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

speedforce

→ Ответить

Ashwini_Tiwari

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

SpeedForces

→ Ответить

wazz

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

why in D, test case 1 the output 7 is incorrect?

→ Ответить

CaveVenom1

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

← Rev. 2 →

There are 2 equivalent worst-case lightning strikes.

Here is the test case: 2 1 5 6 4 3

First example:

8 damage onto 6
7 damage onto 5
6 damage onto 1
5 damage onto 2
4 damage onto 4
3 damage onto 3

Notice the damage toward the end is exact so you can't do better than 8. The other worst case is:

8 damage onto 6
7 damage onto 4
6 damage onto 3
5 damage onto 5
4 damage onto 1
3 damage onto 2

Again, we have exact damage at one point, so we can't do better.

EDIT: Fixed bad formatting.

→ Ответить

legend_palash

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

what? means do cf is asking us to check only 2 ways and get the ans for Div2D?

→ Ответить

CaveVenom1

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

No I was just giving examples why it can't be 7. We have to account for our worst case possibilities; it isn't how can we play optimally, since the lightning strikes are random.

→ Ответить

legend_palash

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

Ohk.. Now I got the problem. ty

→ Ответить

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

But what happen if 8 damage onto 2? Or it doesn't the worst case what's the worst case mean? Thankyou

→ Ответить

killshot50924

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

"Firstly, Vasya chooses an index i of some monster (1≤i≤n) and the initial power of the spell x"

the first monster can be chosen. If you choose the 6-hp monster, you will certainly kill all with 8 spell power.

→ Ответить

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

oh i get it now! thanks you. so hard to understand it for me

→ Ответить

legend_palash

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

yeah I was also getting 7 as the output. as we can move from 6->5->4->3->1->2. Here 7 looks like optimal ans

→ Ответить

CaveVenom1

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

It doesn't matter if we "can move" there. We always have to take the WORST case.

→ Ответить

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

← Rev. 3 →

Suppose you start by hitting the 6 HP monster, and the following happens:

hit 6 HP monster with 7 dmg
hit 5 HP monster with 6 dmg
hit 1 HP monster with 5 dmg
hit 2 HP monster with 4 dmg
hit 4 HP monster with 3 dmg
hit 3 HP monster with 2 dmg

The last monster lives.

If you pick any monster further left as the starting point, the 3 HP monster lives in some scenario. If you pick any monster further right as the starting point, the 2 HP lives in some scenario.

→ Ответить

https://codeforces.com/contest/1901/submission/234100259

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

Because...a power of $$$7$$$ isn't enough to kill all monsters? Why do you think it is enough? Remember that you can only choose the starting monster, you can't affect the order they're killed in after that.

→ Ответить

wazz

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

yes I misread it sadly

→ Ответить

electric_boogaloo

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

← Rev. 2 →

Bruh I was convinced D was supposed to be solved with monotonic stack, turns out it was much easier than that.

Also had to completely guess C, not a good time.

→ Ответить

dark__moon

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

Where's Tutorial?

→ Ответить

Ibrahim

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

← Rev. 2 →

Why is my solution for B not working? subtract the minimum ovral from all elements subtract 1 from it add it to the answer, then for each island between 0s add the maximum to the answer . why is this wrong?

→ Ответить

Pozay

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

Islands can be created while running. For example

2 4 4 3 5

Let's say you start by removing 1 from all :

1 3 3 2 4

remove min from all and add to answer

0 2 2 1 3

ans = 1

Your answer would then be to add 3 to this (return ans = 4) But if you run the algorithm, after a pass you're going to end up with :

0 1 1 0 2

ans = 2

Problem here is you created a new island that you didn't account for, so the answer would be 5, not 4 !

You had to take care of the case when you start descending (4 -> 3 in original array) and then you start ascending (3 -> 5 in original array)

→ Ответить

tgp07

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

+28

I thought C was harder than D lol

→ Ответить

handleisinuse

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

I was trying to solve D with BS, Is there a BS solution for D?

→ Ответить

Synaptic_Savant

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

I solved it Using BS.

→ Ответить

asr_003

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

can you explain your "possible" function please...

→ Ответить

Sidney3

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

I solved B with two sets

→ Ответить

Moyou

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

The same to me

→ Ответить

mrggrm

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

Without a single hope for something good, I solved problem C on the 18th attempt

→ Ответить

mdmahabub55

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

I solved Problem A with 13 time's try.!

→ Ответить

dark__moon

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

Where's Tutorial?

→ Ответить

_Lactosi

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

Thanks for the great round! Could someone please share solution to D?

→ Ответить

infrapolar

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

→ Ответить

_Lactosi

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

Thanks

→ Ответить

infrapolar

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

Idea is finding damage to destroy the right part and the left part relative to some element.

→ Ответить

bananasaur

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

Fix some position of $$$k$$$, then find the lowest possible damage a monster at each position could receive.

For $$$k=1$$$, the first monster receives at least $$$x$$$ damage, the second at least $$$x-1$$$, the third at least $$$x-2$$$, and so on.

For $$$k=2$$$, the first monster receives at least $$$x-n+1$$$ damage (when only the last lightning strike hits it), the second receives at least $$$x$$$ damage, the third receives at least $$$x-2$$$ (in the worst case, the second lightning strike hits the first monster, and the third strike hits the third monster), and so on.

Now you'll find a pattern:

For $$$i<k$$$, the minimum damage dealt is $$$x - n + i$$$ (zero indexed)
For $$$i=k$$$, $$$x$$$ damage is dealt
For $$$i>k$$$, the minimum damage dealt is $$$x+1-i$$$

So for any $$$k$$$, the minimum $$$x$$$ required is $$$\max(\max_{i<k}(a_i+n-i), a_k, \max_{i>k}(a_i - 1 + i))$$$. You can use prefix and suffix maximums to compute this for all values of $$$k$$$ and return the minimum answer.

→ Ответить

asr_003

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

very well explained.

→ Ответить

Chrisedyong

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

Can someone explain me what is incident edge?

→ Ответить

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

An edge is incident to a node if that node is one of the edge's endpoints.

→ Ответить

Chrisedyong

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

so the number of incident edges = the number of degrees of a node?

→ Ответить

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

+14

Yes, the number of incident edges of a node equals the degree of the node.

→ Ответить

Chrisedyong

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

+12

Today I learn. Thanks

→ Ответить

sahaun

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

These terms should be defined in the statement imo. Also, authors can use more familiar terms, like "degree", which should also be defined

→ Ответить

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

It's not easy to know which terms are "well-known" and which are not, especially if you aren't a native english speaker. There will always who doesn't know some term. That's why the clarificiations -system and google exist.

→ Ответить

sahaun

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

+14

I often see very common terms like tree, permutation, subarray, subsequence etc. defined. Gave me the notion that defining these terms was the standard.

Although I don't need it, I like it better than without.

→ Ответить

pb_messi

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

E>>>D, D and C are relatively easy compared to other edu rounds.

→ Ответить

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

D maybe, but not C

→ Ответить

qiu_tianhan

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

C is too difficult to guess

→ Ответить

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

Yeah, kind of

→ Ответить

ruokay

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

messed it up, but i dont think its too bad :)

→ Ответить

boostorna

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

C is far easier than B imho but I guess people are good at different styles of problems.

→ Ответить

codack_mayank

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

What I think is that people below 1500 rating think too greedy that today's C will be easier for them but the people above 1600 try to think in a more generic way that's why they were not able to come up with the logic that answer will only depend on the highest and lowest element.

We should try to balance both things I guess to perform the best.

I also was not able to solve C but solved D in just 15 mins, sadly :(

→ Ответить

kartikey_wariyal

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

me newbie who take more then 1 hour for B and a was easy

→ Ответить

tryGrind

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

how to solve B? how to solve C?

→ Ответить

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

← Rev. 2 →

+10

When a teleportation happens, there is a source and destination. My approach was to count how many source teleportations are required and how many destination teleportations are required.

For each $$$i$$$ in which $$$c_i > c_{i - 1}$$$, there must have been $$$(c_i - c_{i - 1})$$$ teleportations with destination $$$c_i$$$. Add that to the destination count.

For each $$$i$$$ in which $$$c_i < c_{i - 1}$$$, there must have been $$$(c_{i - 1} - c_i)$$$ teleportations with source $$$c_{i - 1}$$$. Add that to the source count.

Furthermore, add $$$c_1 - 1$$$ to the destination count, and also add $$$c_n - 1$$$ to the source count. Return the maximum between source and destination counts.

Consider when there are two distinct values $$$a$$$ and $$$b$$$. No matter which value of $$$x$$$ you pick, the difference between $$$a$$$ and $$$b$$$ reduces to either $$$\left\lfloor\frac{b - a}{2}\right\rfloor$$$ or $$$\left\lfloor\frac{b - a}{2}\right\rfloor + 1$$$. The former is optimal and can be achieved by simply choosing either $$$a$$$ or $$$b$$$ as your $$$x$$$.

If you have more than two distinct elements, all you need to do is ensure that the smallest and biggest values coincide, and this guarantees that all other values will coincide too. Simply find the difference between the largest and smallest elements, and then return the number of bits in the binary representation for this difference.

→ Ответить

Soultaker

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

+12

For B: you don't need to consider source counts at all. It suffices to count how many times the token must be teleported to each square, which is $$$max(c_i - c_{i - 1}, 0)$$$ for the $$$i$$$-th square ($$$i > 1$$$) and $$$max(c_i - 1, 0)$$$ for $$$i = 1$$$ (since the token starts at square 1 for free).

So the solution is basically $$$\sum_{i=1}^n \max(c_i - c_{i-1}, 0)$$$ if you define $$$c_0 = 1$$$.

→ Ответить

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

I just realized that source count must always be equal to the destination count, due to the way they are calculated, so yeah, you can count either one and it should be the answer.

→ Ответить

1braincellremaining

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

why does coincidence of the smallest and the largest number ensure that all the numbers in between coincide too?

→ Ответить

Soultaker

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

Think about the problem in binary. You are performing $$$m$$$ operations, where at each operation, you add a value $$$x_k$$$ ($$$0 ≤ k < m$$$) to all $$$a_i$$$ and then shift right, discarding the least-significant bit for each number.

Here is one useful insight: if you have a solution of the form: add $$$x_0$$$, shift, add $$$x_1$$$, shift, ..., add $$$x_{m-1}$$$, shift; then there is an equivalent solution of the form: add $$$s$$$, shift, add $$$0$$$, shift, add $$$0$$$, shift, ...; where $$$s = x_0 + 2x_1 + 4x_2 + \dots + 2^{m-1}x_{m-1}$$$; i.e., the number of shift operations stays the same, but you add everything in the first operation.

So a different way to formulate the problem is: pick integers $$$s$$$ and $$$n$$$ so that $$$shift(a_i + s, n) = shift(a_j + s, n)$$$ for all pairs $$$i, j$$$, and $$$n$$$ is minimal.

Now if you have $$$a_i ≤ a_j ≤ a_k$$$, then $$$shift(a_i + s, n) = shift(a_j + s, n) = shift(a_k + s, n)$$$ iff. $$$shift(a_i + s, n) = shift(a_k + s, n)$$$, so you only need to consider the minimum and maximum values of $$$a$$$.

→ Ответить

Soultaker

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

For C: it's useful to realize that to minimize the difference after division you only need to consider adding either $$$0$$$ or $$$1$$$.

Specifically, if $$$a < b$$$, then:

If $$$a$$$ is odd, and $$$b$$$ is even, you must add $$$1$$$.
If $$$a$$$ is even, and $$$b$$$ is odd, you must add $$$0$$$.
If $$$a$$$ and $$$b$$$ have the same parity you can add either $$$0$$$ or $$$1$$$.

→ Ответить

alpha1215

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

or you can always choose x = max + 1

→ Ответить

rayan_zk

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

← Rev. 2 →

Thanks LightBrand99 for the explanation. For problem B could you please guide through your thought process (ie, how you came up with the above solution)?

my thought process - couldn't solve with this

→ Ответить

people_plus_plus

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

The task B is:

you have an array $$$a_1,a_2,\ldots,a_n$$$. One operation use choose $$$[l,r]$$$ and decrease all $$$a_i$$$ by $$$1$$$ ($$$l \le i \le r)$$$.

This is basic problem. Answer is $$$\sum\limits_{i=1}^{n+1} \frac{|a_i - a_{i-1}|}{2}$$$, where $$$a_0 = a_{n+1} = 0$$$.

→ Ответить

people_plus_plus

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

To solve this on contest you just need to notice that in this problem your operation is choosing subarray and decreasing all values in it by $$$1$$$.

→ Ответить

rayan_zk

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

Thanks

→ Ответить

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

what is the solution for C? I chose x equal to 0 until the last one decided to be 0 or 1. can you give me some idea. Thankyou

→ Ответить

Rushdi

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

← Rev. 2 →

my solution was if the max element in the array is even and the min element in the array is odd we choose 1

else we choose 0

we keep doing this until the array become equal

→ Ответить

pnzrdlr17

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

If the parity of the max element and the min element is same it doesn't matter what you choose, the difference will be halved anyways, as the difference would be even too.

Otherwise, the difference is odd and so it is better to choose 1 if min element is odd and choose 0 if its even. You can infer the same wrt max element in this case.

→ Ответить

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

thanks

→ Ответить

ksandr1v

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

Just always choose min value.

→ Ответить

Amer_Oniza

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

← Rev. 5 →

In problem C :
Why is this solution rejected?
in test case ( 2 )
2
5 4

→ Ответить

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

← Rev. 2 →

Assuming that you're talking about this submission: 234119469

Notice how you printed an extra $$$5$$$ for the first test case even though the number of operations was $$$0$$$. The contest system thought that this $$$5$$$ was your number of operations for the second case (it was the next token in the output file) and $$$5 > 2$$$ so the verdict is WA.

→ Ответить

CallmeSourav

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

nearest integer to 1.5 is 1 or 2 ?

→ Ответить

YocyCraft

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

+43

A. The answer is max(a[1], a[i+1]-a[i], 2*(x-a[n])), where 2*(x-a[n]) means you need to go from n-th gas station to point x and go back.

B. The operations means you need to choose some segments to add 1 to these segments, and find the minimal amount of segments. Assume a[0]=0 we have ans=sum(max(a[i]-a[i-1],0))-1 where -1 means we don't need to teleport for the first segment.

C. If you choose x[1], x[2], ..., x[k] for operations, the final value of a[i] will be floor((a[i]+x[1]+2*x[2]+4*x[3]+...+2^(k-1)*x[k])/2^k), so in order to make a[i] become equal, we need that max(a[i])-min(a[i])<2^k because x[1] can be chosen arbitrarily.

D. We use binary search for answer, and we need to check if x is a valid answer. Assume we use the spell on the i-th monster, and for j<i, the minimum possible damage it will take is x-(n-i)-(i-j)=x-n+j, which means we must have x-n+j>=a[j] <--> a[j]-j<=x-n. For j>i, the minimum possible damage is x-(i-1)-(j-i)=x-j+1, which means x-j+1>=a[j] <--> a[j]+j<=x+1. And we must have a[i]<=x. Therefore, if we pre-calculate prefix maximum of a[j]-j and suffix maximum of a[j]+j, we can check all i for 1<=i<=n if i-th monster is a valid initial target in O(n).

E. The problem means we need to build a subtree from the initial tree, and take the sum of a[u] for all deg[u]!=2. So we can let dp[k][u]=the answer if the highest node in the tree we build is u, and deg[u]=k. Note that we don't need to distinguish cases where k>=3.

→ Ответить

Rushdi

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

what do you think the rating for problem E is ?

→ Ответить

OmarAboutaleb77

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

It should be 2200-2300 according to CF bot.

→ Ответить

sahaun

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

Use CLIST!

→ Ответить

Khan_2020

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

In problem E,what is the highest node in the tree?And what do we return as the answer?

→ Ответить

GoneTomorrow

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

In problem D, you are under-estimating the actual amount of damage monsters will take. How are you sure that would yield a correct answer?

→ Ответить

Jhdrgfj.

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

I think D is easier than C. It took me 1h to solve C, but D only took 15min.If I slove D first may I can have rk1000- :(

→ Ответить

CallmeSourav

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

closest integer to 1.5 is 1 or 2 ? and why

→ Ответить

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

+10

Are you talking about problem C? If yes, you probably missed the part where it said rounding $$$y$$$ down to the nearest integer. We're rounding down and the nearest integer below $$$1.5$$$ is $$$1$$$, not $$$2$$$.

→ Ответить

CallmeSourav

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

crying inside wasted all my time in problem c....... crying outside ...... i will become candidate master by june 2024

→ Ответить

treasuryonly

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

My solution for problem C (234118115) is to choose x = min and keep making max = (max + min) / 2 until max == min, not pretty sure about this but got AC.

I hit the tab SUBMIT CODE when there was 10 seconds left but it kept loading the page until the message Contest is over displayed.

Thank you guys for the contest!

→ Ответить

Pozay

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

Did this, but was getting some TLE so added some ugly heuristics to try and make it work. I'm really bad at C++ apparently ahhhhh. Welp thanks for confirming at least that my idea was sound !

→ Ответить

OmarAboutaleb77

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

What is the logic behind choosing x = min? I always chose x = 0 or x = 1.

→ Ответить

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

← Rev. 2 →

If x = min or x = max, the difference between max and min decrease by the floor of half. This is easy to observe mathematically. For other choices, it is possible for the difference to decrease by either the floor or the ceiling of half, depending on the parity of the original min, original max, and your chosen x. This requires a little more case work for a mathematical proof, but one can intuitively deduce that the difference can't possibly be reduced further than the floor of half, so it is optimal to stick with that.

→ Ответить

treasuryonly

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

I just tested with some cases by choosing min and it seems to be correct, plus there was just about only less than a minute left (and I couldn't make it in time as in my comment).

→ Ответить

cr7_better_than_messi

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

As a not tester, i don't know problems.

→ Ответить

Jhdrgfj.

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

I think D is easier than C. It took me 1h to solve C, but D only took 15min.If I slove D first may I can have rk1000- :(

→ Ответить

Mr.Greedy

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

With just 3 seconds left, I got the adrenaline rush.

→ Ответить

schmosby

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

Huge gap between ABCD and EF, not to mention that ABCD are probably under 1500-ish.

→ Ответить

Mr.Greedy

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

+16

With just 3 seconds left, I got the adrenaline rush. A SuperOverKill BFS 234117586

→ Ответить

avighnakc

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

Wow, good job

→ Ответить

Folka

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

WOW but it seems your code is semi-complicated while the solution is each time x = max_number + 1

because, (x+x+1)/2 = x while (x+x+2)/2 = x+1 so what ever happened all numbers will not exceed max_number and make the min_number be equal to max_number you can check my submission 234086134

→ Ответить

hundunlilun1

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

Wow, good job;

→ Ответить

avighnakc

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

C > D > B > A

→ Ответить

asthma

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

For me, it was D > B > C > A. C came intuitively to me and I found D much harder.

→ Ответить

Ruthless__

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

Problem sets seemed really interesting to me...Hope to see more contests like this!

→ Ответить

OmarAlSeddik

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

Solved C but couldn't solve B because I forgot to use long long instead of int and somehow missed that as I was staring at my screen for an hour. It hurts so much... :(

Oh well... We live and we learn! I'm new at this so there's so much for me to learn, including the absolute basics lol.

→ Ответить

OmarAboutaleb77

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

That's why I use

#define int long long

I know it's bad practice but I've made that mistake way too many times.

→ Ответить

iaadi8

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

can you explain your answer?

→ Ответить

OmarAlSeddik

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

B: I noticed a pattern from the provided input->output examples that the result is just the sum of the difference between each element and the element before it but only if the element before it has a higher value, plus the final element — 1.

C: Just always pick the minimum element in the array as x. Always. The number of times it takes for all elements in the array to equal each other is equal to the number of times it takes for the maximum element to get to the minimum element with the given equation.

So, I did just that. Stored the minimum element and the maximum element, and then made a while loop that does the operation with a counter.

→ Ответить

iaadi8

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

Thanks

→ Ответить

Folka

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

← Rev. 2 →

Very interesting contest but I had a connection problem so I delayed for 20 minuets and solved " D " after the contest end :(

→ Ответить

LordOrbit

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

← Rev. 2 →

Really interesting tasks and one of the most balanced round for last months. I will be glad to see next rounds from the authors!

→ Ответить

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

← Rev. 2 →

-18

" very balanced round in recent months "

Problem D: 1987

Problem E: 255

Its decreasing by 10. Ideally it should decrease by 2 on each step to be balanced.

→ Ответить

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

What are that numbers?

→ Ответить

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

Solve count

→ Ответить

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

But D solved more than 255 people? Am I wrong?

→ Ответить

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

Check in official standings. Those submissions were made after contest

→ Ответить

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

← Rev. 4 →

What I was actually trying to say is that you confused D with E and C with D

→ Ответить

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

You are right. Fixed this.

→ Ответить

LordOrbit

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

There should be tasks that separates div2 and new div1 participants. The last two were just for latter ones

→ Ответить

GNlDA

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

bruh

→ Ответить

tvmpqx_8601

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

Since there is no yet editorial: how to solve F?

→ Ответить

jeroenodb

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

Thank you for problem F! It was really satisfying to solve.

→ Ответить

Osama_Fahim

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

← Rev. 3 →

Problem C:

234129053

can someone please explain why I am getting memory limit exceeded for this code ?

→ Ответить

tvmpqx_8601

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

When x=0 and y=1 you get infinite loop which allocates large amount of memory

→ Ответить

Osama_Fahim

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

Thanks Sir

→ Ответить

asthma

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

In problem D, can anyone explain why I'm getting WA on test 6:

submission

→ Ответить

love_you

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

for test n = 7 a = {5, 5, 5, 4, 4, 4, 4} your solution return 11 but right answer is 10

→ Ответить

heesooyaam

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

could smbd prove greedy solution for B, pls?

→ Ответить

md_nihal

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

← Rev. 4 →

For first move, you will need a[1]-1 moves always

you can always move to A[i] from A[i-1] if A[i]<=A[i-1] without Teleporting

But if A[i]>A[i-1] you need to Teleport A[i]-A[i-1] times

Ans can be

$$$ A[1]-1+\sum_{i=2}^{n} max(A[i]-A[i-1],0)$$$

→ Ответить

people_plus_plus

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

That greedy solution you are talking about? Probem B is: we have array $$$a_1,a_2,\ldots,a_n$$$. Find minimum number of following operations we have to do to make array all zeroes. Operation is take a subsegment $$$[l,r]$$$ and decrease all values by $$$1$$$.

It's easy to proof that if we use our operation on segment $$$[l,r]$$$ and can use it on segment $$$[l', r'] (l' < l, r < r')$$$ we should use it on segment $$$[l', r']$$$.

→ Ответить

amin_2008

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

messed up on C a lot

→ Ответить

Izuku__Midoriya

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

-8


solve() {
	ll n ;
	cin >> n;
	ll a[n+4];
	ll mx = 0;
	ll mn = 1e18;
	for(ll i = 1; i <= n ; i++){
		cin >> a[i];
		mx = max(a[i],mx);
		mn = min(a[i],mn);
	}
	ll cnt = 0;
	vector<ll>v;
    for(ll j = 1 ; j <= 35 ; j++){
    	if(abs(mx-mn) == 1){
          if((mx>0 && mn > 0) && (mx%2 == 0) ){
          	v.push_back(1);
          	//cout << "f"<<endl;
          	cnt++;
          	break;
          }
          if((mx > 0 && mn > 0) && (mx%2 == 1)){
          	v.push_back(0);
          	cnt++;
          	break;
          }
          //else continue;
    	}
    	if((mx-mn) == 0 ){
    		break;
    	}
 
    	mx = 0;
    	mn = 1e18;
    	for(ll i = 1; i <= n ; i++){
    		a[i] = (a[i]/(ll)2);
    		mx = max(a[i],mx);
    		mn = min(a[i],mn);
 
    	}
    	v.push_back(0);
    	cnt++;
 
    }
    if(cnt > n){
    	cout << cnt <<endl;
    	return;
    }
    else{
    	cout << cnt << endl;
    	for(auto x:v){
    		cout << x<<" ";
    	}
    	cout << endl;
    }
 
 
 
 
 
 
}

why my code is failing . Can anyone give me any case ?

→ Ответить

silenttkillerr

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

Any counter Test for this solution of C https://codeforces.com/contest/1901/submission/234171914

→ Ответить

variety-jones

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

Take a look at Ticket 17155 from CF Stress for a counter example.

→ Ответить

sidd.reddy1607

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

In D, won't it be smart to always choose the monster with the highest health at the beginning? I'm unable to come up with a counter-example as to when this won't work

→ Ответить

lisashi

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

← Rev. 2 →

What if there are multiple monsters with highest health?

Also try this case

7
3 1 4 2 2 2 2

If you start with 3, the minimum power is 8 If you start with 4, the minimum power is 9

→ Ответить

sidd.reddy1607

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

Thanks for the test case! It makes sense as to why we have to consider every possible index now.

→ Ответить

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

← Rev. 2 →

Check out this test:

8
1 11 1 1 12 1 1 1

Here, if we choose the monster with 12 health we need x = 17, but if we choose to start from the monster with health 11 we only need x = 16.

We can't choose the monster with 12 and have x = 16 because we kill that monster and all monster to the right and our power decreases to 12, we kill the monster to the left of it with 12 and we get to 11, we kill the left monster again and we are down to 10, this is less than what we need to kill the monster with 11 health.

→ Ответить

mastercheif

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

2 1 5 6 4 3, in this test case if i choose starting monster as 1 and power as 8 then kill all the monsters to the left the power left is 6 then go left and kill 5 ,then power becomes 5 and then move to left ,now we get stuck at monster 6 because we have only power of 5.then why is the answer 8? or am i making some mistake pls point that out?

→ Ответить

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

The answer is 8 because you can choose to start at the monster 6 and for every option you take at whatever point in time you can always kill all the monsters.

→ Ответить

mastercheif

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

but we are told that the answer should work even in the worst case, so why won’t the case i mentioned be considered.

→ Ответить

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

It should work in the worst case for the starting element that you have chosen, that's why the problem comes down to finding the starting element for which the worst case is the least of all the other worst cases.

→ Ответить

mastercheif

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

understood, thanks .

→ Ответить

Dawnq

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

+113

In this round，Im_dik from Chongqing Nankai Secondary School defeated the famous Legendary Grandmaster Um_nik. It's so fun!

→ Ответить

yvbf

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

I am curious about the input size n (5 times of 10^5 but not usual 1 or 2) in problem E, is it intended? I kept getting MLE and RTE during the contest and, it turns out RTE is stack overflow (I should have thought it through), while I only left two local variables in the usual tree-DP recursive function. After exact those two local variables out of the recursion stack, it is an Accepted code. It seems that the stack size setting for Java in CF is a small number of MB, while I never thought it would be an issue, at least not in tree-DP. (BTW I used 128MB in local dev-environment setting.)

But thanks to this problem, now I have got a snippet of code to do tree-DP-traversal without recursion. =)

→ Ответить

I_believe_I_can_fly

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

← Rev. 2 →

The system test finished and my tricky solution 234102255 for problem E is still alive. Can anyone provide a hack test or it is actually true ?

→ Ответить

flame_boy

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

Waiting for editorial

→ Ответить

iamhariom_28

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

In problem D, for test case 2, 1, 5, 6, 4, 3 why spell of 7 is not the minimum because if we start with index 4(value = 6) and damage = 7, then index = 3 getting damage 6, then index 5 getting damage 5, index 6 getting damage 4 and index 2 and 1 getting damage 3 and 2 respectively. Can anyone suggest where I am doing wrong?

→ Ответить

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

If you start at index 4 with power 7 you than kill the index 5 with power 6 and the index 6 with power 5, now you don't have enough power left to kill the monster at index 4. Remember, since the monster killed is chosen randomly between the 2 options possible (or 1 if there are no 2 possible options), you have to account for the worst case scenario. Sure, power 7 would've worked if you killed index 3 first, then the indexes >4 and than the indexes <3, but that's only one case, we have to account for all possible cases.

→ Ответить

yashkumar22072002

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

so basically if we choose index 'i' so there are two possiblites that either go to the right of till end and the the other half and another one like go to left of i to the start and then go for the other half ?

→ Ответить

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

Those are not the only cases. For example, in an array with 5 elements (1-indexed), if you start at index 3, you can also go 3->4->2->5->1. At any moment in time, if there are 2 indexes that you've not visited adjacent to indexes that you have visited, you can go in either one of the 2, that's why it's important to account for all possible ways. But yes, in the solution, you're basically assuming the worst case scenario, that is, if the index is to the left of the starting element you're assuming it first went to the right and only then came left so that by the time it reaches that index, the power will be the minimum. The same goes for when the index is to the right of the starting index, only in reverse.

→ Ответить

n_azifa

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

I have submitted one problem successfully still didn’t get any rate.It's showing unrated..why!!

→ Ответить

Md_Masaud_Hasan

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

One of the best edu rounds.

→ Ответить

n_azifa

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

I Have completed 1 problem successfully still didn’t get any rate.It's showing unrated.why so!!

→ Ответить

Merciful_soul

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

this round is rated or unrated idk. I think this round unrated because rate not given soooo longgg

→ Ответить

Intuition2.0

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

A simple logic for the problem c : if max_element of array is even then we add 1 to array otherwise add 0 234215511

→ Ответить

KazoeYakuman

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

I participated this contest but my rating didn't change. Why?

→ Ответить

1xx55

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

just wait for a few days and it will change.

→ Ответить

KazoeYakuman

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

thx

→ Ответить