Educational Codeforces Round 126 [Rated for Div. 2]

3 years ago, # |

D = Cses Polynomial Queries

"Template": https://mirror.codeforces.com/blog/entry/78923?#comment-644972

→ Reply

3 years ago, # ^ |

← Rev. 2 →

+38

Problem D is actually even easier, you don't need any range data structures.

If you have $$$k$$$ open APs which together add a sum $$$s$$$ to some position $$$i$$$, when moving to $$$i - 1$$$, it will add a sum $$$s - (k - start_{i})$$$ where $$$start_{i}$$$ is the number of APs which start at $$$i$$$.

So by just storing the number of APs starting from a point (which can be trivially set when we add a new A), we have all the information we need to just simply solve it with a single iteration.

Submission — 153184495

→ Reply

3 years ago, # ^ |

Wow, that's neat

→ Reply

stlukasz

3 years ago, # ^ |

← Rev. 2 →

How can you solve D with this technique from Polynomial Queries? I have an AC on CSES and honestly, I don't know how to use it here

→ Reply

3 years ago, # ^ |

once you modify your code to add 1*x, 2*x, 3*x... k*x to a range instead of (1,2,3..k) where x is a constant, then you should be able to solve the problem greedily from right to left

→ Reply

sergeev.PRO

3 years ago, # |

interesting round. B is brilliant problem

→ Reply

Ghaith

3 years ago, # |

Greedyforces

→ Reply

3 years ago, # |

I LOVEEEEEE SEGMENT TREES

→ Reply

average_treap_enjoyer

3 years ago, # |

-6

I hate this round.

→ Reply

JEE_MAIN_LOOSER

3 years ago, # ^ |

Why ??

→ Reply

bobrik228228

3 years ago, # |

B — cringe C — cringe D — cringe

→ Reply

3 years ago, # ^ |

Don't forget A — cringe ;)

→ Reply

3 years ago, # ^ |

I dp-ed A b/c I'm stupid

→ Reply

3 years ago, # ^ |

Just usual A is something simple in few lines, didn't expect it to be a greedy with quite long implementation as for problem A

→ Reply

3 years ago, # ^ |

what was your greedy?

→ Reply

3 years ago, # ^ |

Choosing min (abs(a[i]-a[i-1])+abs(b[i]-b[i-1]), abs(a[i]-b[i-1])+abs(b[i]-a[i-1])), basically what bottom comment does

→ Reply

3 years ago, # ^ |

implementation doesnt need to be long: Code

→ Reply

3 years ago, # ^ |

Hm, makes sense. Actually was doing exactly same thing, just it code turned out a bit longer, right

→ Reply

3 years ago, # ^ |

-28

Actually, comparing to last 2 months rounds A should have been B, B should have been C, C shouldn't have been in this contest B/

My friend solved D and E, couldn't solve C — that tells everything about this contest.

→ Reply

3 years ago, # ^ |

I thought that A was harder than usual, but a simple dp will solve it. C was okay for its place, but B had an interesting observation. I tried to bash it with a solution similar to my solution for this problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=1182

→ Reply

quagmire

3 years ago, # ^ |

same lol.

→ Reply

misaka18931

3 years ago, # ^ |

+18

and cringe E (indeed)

→ Reply

3 years ago, # |

← Rev. 2 →

Is this approach roughly correct for E or am I way off and / or overkilling it?

Lets call components that contain both $$$(1, i)$$$ and $$$(3, i)$$$ but not $$$(2, i)$$$ for some i to be "partitionable".

These partitionable components must be connected by vertical lines spanning all $$$3$$$ rows in some columns, lets call them "partitioning lines".

Suppose a component has multiple "partitioning lines", lets call the rectangle formed by each adjacent pairs of "partitioning lines" of the same component a "partitioning rectangle".

After counting the partition lines and partitioning rectangles, lets go ahead and remove $$$(2, i)$$$ for each partitioning line. Now each partionable component has been partitioned.

Then the answer for a range is (the number of components that are partially or fully covered) — (the number of partitioning lines covered) + (the number of partitioning rectangles that are fully covered).

This can then be calculated using Mo's with a per-operation time of O(1) using a few supplementary arrays to represent the corresponding ranges.

→ Reply

3 years ago, # ^ |

I thought it was a segment tree problem, but my implementation was too buggy to finish it in contest time :(.

→ Reply

Ant_Man

3 years ago, # ^ |

+35

It can be done with a segment tree. For a range you should store the number of components in it and the connectivity information among its six vertical border cells. These are enough to merge two adjacent ranges.

→ Reply

3 years ago, # ^ |

← Rev. 2 →

Oh, that seems super obvious now that you mention it... Thanks for the help.

→ Reply

lrvideckis

3 years ago, # ^ |

I had much trouble fitting this solution in constraints

→ Reply

nyacho_dayo

3 years ago, # ^ |

How do you merge two ranges? I had the same approach but got TLE. My implementation now is to build a new graph with 12 vertices (6 from the left range and 6 from the right) and do BFS on it, which seems to be too slow. Is there a better way to combine ranges?

→ Reply

Bobrosoft

3 years ago, # ^ |

← Rev. 2 →

I had the same problem as you. I've managed to overcome it: https://mirror.codeforces.com/contest/1661/submission/153229389 (look at the method "combine").

Basically, the idea is that we can just map either the left-side components to their right-side counterparts or vice versa. If on one side we have only one component, then it is always good to map something to it, since it can potentially merge some components from the other side. If on both sides there are two components, then the mapping direction doesn't matter, because disjointed components on each side will stay disjointed.

Alternatively (that's what I did in the code), you can map from the side with two components. The idea is the same, the direction only matters when there is 1 component on one side and 2 on the other.

Sorry for a messy explanation, it's kinda hard to put it into words. :D If you have any questions, feel free to ask, I'll try to clarify.

→ Reply

Bobrosoft

3 years ago, # ^ |

Example:

1 - 7
1 - x
1 - 8

Here, we want to map 7 -> 1, 8 -> 1, because it will merge them.

1 - 7
x - x
2 - 8

Here, we can either map 1 -> 7, 2 -> 8 or 7 -> 1, 8 -> 2, it doesn't matter.

→ Reply

FC_Viiiiictor_K

3 years ago, # |

C is indeed a good greedy problem and I got AC after six WAs, LMAO

→ Reply

Osama_Gharib

3 years ago, # ^ |

What's the solution? i tried using binary search initially to find minimum required days

→ Reply

3 years ago, # ^ |

I used binary search on the number of days. Note that you first have to make all the elements of the array have the same parity.

→ Reply

Osama_Gharib

3 years ago, # ^ |

i did the same except the part of similar parity. What's the intuition behind it?

you can check my submission sorry for the spaghetti code https://mirror.codeforces.com/contest/1661/submission/153212636

→ Reply

3 years ago, # ^ |

Well, noticing that the operation on even days, which is adding two to a height of a tree, does not change the parity, so you must use the odd day operations to equalize the parities

→ Reply

3 years ago, # ^ |

same

→ Reply

FC_Viiiiictor_K

3 years ago, # ^ |

+12

My solution is to count how many 1s and 2s you need:

ll need1=0,need2=0;
for(int i=1;i<=n;i++){
    need1+=(maxv-heit[i])%2;
    need2+=(maxv-heit[i])/2;
}

When need2>=need1, it's obvious that you can take one 2 as two 1s and get the best solution:

ll tmp=(need2-need1)/3;
need2-=tmp;
need1+=tmp*2;
cout<<min(daysneed(need1,need2),daysneed(need1+2,need2-1))<<endl;

When need2<need1, you need to consider the possibility that the maximal height may increase by 1:

if(need1>need2){
    ll ans=daysneed(need1,need2),tmp1=n-need1,tmp2=need1+need2;
    need1=tmp1;
    need2=tmp2;//this is how need1 and need2 behave after increasing the maximal height by 1
    ll tmp=(need2-need1)/3;
    need2-=tmp;
    need1+=tmp*2;
    ans=min(ans,min(daysneed(need1,need2),daysneed(need1+2,need2-1)));
    cout<<ans<<endl;
}

This is not obvious and you can find this possibility by analysing this case:

10 1 1 1 1 1 1 1 1 1 2

Hope I could help you. Excuse me for my bad English. :)

→ Reply

Osama_Gharib

3 years ago, # ^ |

Thanks for the clear explanation.

→ Reply

ChaosAngel

3 years ago, # ^ |

I also thought of this initially, that you can calculate how many days you will need because, roughly speaking, after handling parities, 1/3 of your growth requirement will be handled by odd days and 2/3 by even days so we can solve for the final day. But this is a bit annoying at the edge, it needs some precise handling, so I just binary searched instead of explicitly solving these computations.

Many BS problems have direct formulae, but you will find that doing the BS saves a lot of implementation and headache at the cost of a log factor.

→ Reply

3 years ago, # |

Every time i'm promising myself to never ever participate into a edu round, but every time I return back hoping on nice problems

→ Reply

Sakura_mw

3 years ago, # |

Any hints for D would be appreciated, no idea completely..

→ Reply

EasonCookie197

3 years ago, # ^ |

You can do the operations greedily from right to left.

→ Reply

Sakura_mw

3 years ago, # ^ |

thx..！got it

→ Reply

ParsaAp

3 years ago, # ^ |

Create a from the end.

→ Reply

Sakura_mw

3 years ago, # ^ |

thx..! I overestimate it..

→ Reply

3 years ago, # |

Any proof of A why taking smaller element in one array in an index and the bigger for the other array works?

→ Reply

alimurodov

3 years ago, # ^ |

collecting smaller elements in one array, and bigger elements in another array, because |ai — aj| must be minimum

→ Reply

3 years ago, # ^ |

what's the name of the character in your pfp?

→ Reply

sayemsub15

3 years ago, # |

← Rev. 4 →

B took away all the time

→ Reply

tezk

3 years ago, # |

WA problem C because I use int instead of long long int. God I feel so titled right now

→ Reply

Thallium54

3 years ago, # |

+17

I was literally one second late for submitting E, otherwise I would become master today (I'm crying

→ Reply

EasonCookie197

3 years ago, # |

Did anyone use ternary search for C?

→ Reply

JEE_MAIN_LOOSER

3 years ago, # ^ |

Yeah i saw my friend doing it that way !

→ Reply

Stoiic

3 years ago, # |

What is logic behind B?

→ Reply

3 years ago, # ^ |

Just a bfs problem using reverse edges

→ Reply

Stoiic

3 years ago, # ^ |

← Rev. 2 →

→ Reply

3 years ago, # ^ |

+25

I thought along these lines for a few mins before realizing it is super overkill.

If we multiply by $$$2$$$, it will be divisible by $$$2^{15} = 32768$$$ in at most $$$15$$$ steps.

Also clearly we're trying to clear the lower bits, so adding more $$$1$$$s in-between doesn't exactly make much sense. So we perform some $$$i \leq 15$$$ additions at the start and just find the minimum number of multiplications required to make it $$$\equiv 0 \mod 32768$$$ for a total complexity of at most $$$O(n \log^2 n)$$$

→ Reply

lrvideckis

3 years ago, # ^ |

+11

Is BFS really overkill? your solution requires an extra observation

→ Reply

3 years ago, # ^ |

overkill in terms of implementation

→ Reply

Newtech66

3 years ago, # ^ |

It can be improved to $$$\mathcal{O}(n\log{n})$$$ by using a recurrence like $$$r_a=\min{(cnt_a,1+r_{a+1})}$$$ where $$$cnt_a$$$ is minimum number of multiplications to make $$$a \equiv 0 \pmod{32768}$$$.

→ Reply

devanshmishra111

3 years ago, # ^ |

why can't i use dp here?

→ Reply

3 years ago, # ^ |

you can use dp actually with O(nlogn) : dp[count_operation][current_number]

→ Reply

devanshmishra111

3 years ago, # ^ |

← Rev. 2 →

in what order will u compute?

dp(i, j) -> dp((i + 1) % 2^15, j + 1)

dp(i, j) -> dp((2 * i) % 2^15, j + 1)

the next state of i can either be greater than current i or less than current i

→ Reply

3 years ago, # ^ |

why does it matter when you do recursive dp? It's hard to find the order when you do iterative dp but in case of recursive dp it doesn't matter

→ Reply

devanshmishra111

3 years ago, # ^ |

← Rev. 2 →

i don't think it will work because no order exists... i tried it and got wrong ans

→ Reply

3 years ago, # ^ |

bfs???Seriously??That's not intended solution for sure, there are better solutions

→ Reply

WitchOfTruth

3 years ago, # ^ |

Actually this is definitely one of the intended solutions, look at the constraints

→ Reply

ExpertHuMaiAab

3 years ago, # ^ |

I did not get the part when you reversed the edges. Can you please elaborate a bit?

→ Reply

harous

3 years ago, # ^ |

i did use bfs and my solution was hacked could you please explain what went wrong ? 153191941 . after the contest i submitted the same solution and i got accepted 153232889

→ Reply

3 years ago, # ^ |

Just a heads up, the hacking phase is still ongoing, so the current test does not include the hack that hacked your solution, so your "accepted" solution is still going to fail. Your solution does not work because you are repeatedly bfs-ing for each number in the array, which would result in $$$O(32768 * 32768) = O(2 ^ {30})$$$. Instead you should bfs once, just starting from 0 and using the "reverse edges" ((j + 1) % 32768 to j and (2 * j) % 32768 to j), which would ensure an asymptotic behavior of $$$O(32768)$$$

→ Reply

3 years ago, # ^ |

← Rev. 2 →

Hints :

32768 is 2^15
Max Probable Operation : 15

→ Reply

Zealotrahl

3 years ago, # ^ |

Max Probable Operation : 15

why?

→ Reply

3 years ago, # ^ |

because you always can multiply a number : X by 2 — 15 times which is X * 2^15 and X * 2^15 mod 32768(2^15) is obviously 0

→ Reply

Zealotrahl

3 years ago, # ^ |

I'm not a big number theory guy, could you please show more straightforward proof; I can see that it gets rounded back when we multiply by 2 x = 17000 1232 = (17000*2)%32768 2464 = (1232*2)%32768 etc

I don't believe that there will be a factor 2^15;

→ Reply

uvuv

3 years ago, # ^ |

You can represent any number as sum of power of 2: Let's take 2^14 + 2^12 + 2^1 And when we do second operation: (2*(2^14 + 2^12 + 2^1)) % 2^15 = ((2^15 + 2^13 + 2^2))%2^15 = ((2^13 + 2^2))%2^15 And this way we can get 0 after at most 15 operations, because the minimum element can be 2^0.

→ Reply

johnLate

3 years ago, # ^ |

Do you notice something here?

1000000000000000 32768

1000000000000000 32768

0100001001101000 17000
0000010011010000  1232
0000100110100000  2464
0001001101000000  4928
0010011010000000  9856
0100110100000000 19712
0001101000000000  6656
0011010000000000 13312
0110100000000000 26624
0101000000000000 20480
0010000000000000  8192
0100000000000000 16384

→ Reply

Zealotrahl

3 years ago, # ^ |

Wow, great explanation thanks

→ Reply

sayemsub15

3 years ago, # ^ |

← Rev. 2 →

We can put the number of operations needed to make each number $$$i$$$, $$$1\text{ to }32768$$$ by using the second operation, $$$(2\times i)\text{ mod }32768$$$, in an array, $$$ans[\text{ }]$$$ . Then calculate if there is any number $$$j$$$ such that $$$j-i$$$ $$$+ans[j] $$$ $$$<$$$ $$$ans[i]$$$.If there is then print $$$\text{MIN}(j-i + ans[j],\text{ 32768}-i)$$$ otherwise $$$\text{MIN}(ans[i],\text{ 32768}-i)$$$.

→ Reply

arutsudar

3 years ago, # |

For Problem C, can someone help me understand how the below test case answer is 9 days ?

7
1 1 1 1 1 1 2

I am getting 11, as all the trees with height 1 can be watered on every odd day (Days: 1,3,5,7,9,11).

Not sure what I am missing :(

→ Reply

3 years ago, # ^ |

Try to make the height of all trees be 3

→ Reply

robostac

3 years ago, # ^ |

Water the tree with height 2 on day 1 so you can do something on the even days.

→ Reply

helios_

3 years ago, # ^ |

← Rev. 2 →

+13

On day 1 , water the tree of height 2 , so new array becomes => [ 1 , 1 , 1 , 1 , 1 , 1 , 3] ,On day 2 , water the tree of height 1 , so new array becomes => [ 3 , 1 , 1 , 1 , 1 , 1 , 3] ,On day 3 , water the tree of height 1 , so new array becomes => [ 3 , 2 , 1 , 1 , 1 , 1 , 3] ,On day 4 , water the tree of height 1 , so new array becomes => [ 3 , 2 , 3 , 1 , 1 , 1 , 3] ,On day 5 , water the tree of height 2 , so new array becomes => [ 3 , 3 , 3 , 1 , 1 , 1 , 3] ,On day 6 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 1 , 1 , 3] ,On day 7 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 2 , 1 , 3] ,On day 8 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 2 , 3 , 3] ,On day 9 , water the tree of height 2 , so new array becomes => [ 3 , 3 , 3 , 3 , 3 , 3 , 3]

→ Reply

dvaravind

3 years ago, # ^ |

Someone please say how to solve 3rd case in 1st test case in 16 days as well.

→ Reply

arutsudar

3 years ago, # ^ |

dvaravind 3rd case in 1st test case:

7
2 5 4 8 3 7 4

Same thing in sorted 2 3 4 4 5 7 8

Days:

2 3 4 4 5 7 8 — Day 0
2 3 4 4 5 8 8 — Day 1
2 3 4 4 7 8 8 — Day 2
2 3 4 4 8 8 8 — Day 3
2 3 4 6 8 8 8 — Day 4
2 4 4 6 8 8 8 — Day 5
2 6 4 6 8 8 8 — Day 6
2 7 4 6 8 8 8 — Day 7
4 7 4 6 8 8 8 — Day 8
4 8 4 6 8 8 8 — Day 9
6 8 4 6 8 8 8 — Day 10
7 8 4 6 8 8 8 — Day 11
7 8 6 6 8 8 8 — Day 12
8 8 6 6 8 8 8 — Day 13
8 8 8 6 8 8 8 — Day 14
8 8 8 6 8 8 8 — Day 15 (Skip)
8 8 8 8 8 8 8 — Day 16

→ Reply

dvaravind

3 years ago, # ^ |

Thank you! I was wondering I skipped only one day and made all 8. But I skipped even day and you skipped odd day. This is where I went wrong

→ Reply

arutsudar

3 years ago, # ^ |

Thank you for your replies Bungmint, robostac, helios_

→ Reply

JEE_MAIN_LOOSER

3 years ago, # ^ |

← Rev. 2 →

They didn't say we always have to make everything equal to max element of array. Just extra check for max_element + 1 would have passed all testcase . I got this intution by this example which i created during contest Hope it help you.

Testcase Example — 1 1 1 1 1 1 1 1 1 2 (Instead making everything 2 make everything 3) Making everything 2 will cost 17 days while making 3 will cost 13 days . I was so happy when i found it during contest and got Ac.

→ Reply

Theo830

3 years ago, # |

Problem F is an easier version of Doubletrouble from JBOI 2018.

→ Reply

AmiteshMagar

3 years ago, # |

I don’t know why I’m getting a TLE. I asked me friends and they have kind of a similar implementation and theirs has passed. Could someone please check my solution. Thank you. 153209572

→ Reply

666EGOR777

3 years ago, # ^ |

memset is o(n) and you do it t times

→ Reply

AmiteshMagar

3 years ago, # ^ |

OHHHH!! Thanks a lot, I did not see it.

Man!! :(

→ Reply

DoubleHelixa

3 years ago, # |

E is quite similar to 811E...

→ Reply

Yahia_Emara

3 years ago, # ^ |

It is easier than it

→ Reply

variety-jones

3 years ago, # |

+13

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

I've also added 2 new features: Near real-time log streaming and Compressed Parameter editing without using tables.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

→ Reply

onlyerror

3 years ago, # ^ |

I did not find a counterexample for my submission. My submission id 153253105 ticket 4346

→ Reply

variety-jones

3 years ago, # ^ |

Failing Testcase: Ticket 4370

If you fail to find a counter example, set $$$t\_low = t\_high = \infty$$$ so that your code is evaluated on larger number of testcases per input.

→ Reply

onlyerror

3 years ago, # ^ |

thanks

→ Reply

Yahia_Emara

3 years ago, # |

WOW, WHAT A CONTEST, every problem almost destroyed my sanity in a different manner, but I managed to solve them all (ABCD), but to get Expert performance again....

→ Reply

Newtech66

3 years ago, # |

+36

I have a solution for E that works in $$$\mathcal{O}(n \cdot \alpha (n) + q)$$$.

Solution

Implementation: 153223011

→ Reply

pink_roses

3 years ago, # ^ |

I have linear solution

→ Reply

Bliznetc

3 years ago, # ^ |

it seems to me that you have lower_bound in your code. Time complexity of std::lower_bound() is O(log(SIZE)). So your solution isn't linear

→ Reply

pink_roses

3 years ago, # ^ |

Yeah that part can be changed to be linear, it just looks to closest 101 to the left and to the right, which can be looked in o(1) with preprocessing

→ Reply

pink_roses

3 years ago, # ^ |

I also precount components, and represent them as intervals with leftmost and rightmost cells.

Then during query i give answer of these interval counts. But understand that some component can fall apart (1 or 2 of them at the borders). It happens when 101 is at the border and these ones are connected using outer cells from outside (l, r). I consider these cases with some hard coded logic, that looks into leftmost and rightmost 101s

→ Reply

gnudgnaoh

3 years ago, # ^ |

great solution :3

→ Reply

Arun_bro1

3 years ago, # |

Any hint for C , I was able to thought that we will make max or max+1 height. but what after.

→ Reply

cosenza

3 years ago, # ^ |

Just that will suffice. The rest is figuring out the best way to water the plants (how to properly distribute the 1's and 2's)

→ Reply

Arun_bro1

3 years ago, # ^ |

Any hint regarding how to distribute them

→ Reply

cosenza

3 years ago, # ^ |

← Rev. 2 →

If you have too many 2's, then you can split them up into two 1's, however, the opposite isn't true, as when you first count how many 1's are needed, they indicate the parity of the numbers (i.e. how many odds there are, and you can't distribute the addition of 2 to two separate numbers).

How to count the 1's and 2's: if the number is odd, then you can increment the amount of 1's by one, then you increment the amount of 2's by (number / 2). Then you need to find the best result using what was said in the previous paragraph.

→ Reply

3 years ago, # |

I just realized my algorithm for B isn't correct, how did you all solve B?

→ Reply

ExpertHuMaiAab

3 years ago, # ^ |

I upsolved it in the following way. There will be a max of 15 operations because applying the second operation 15 times will make the given number a multiple of 2 ^ 15. Also, all the manageable addition operations should be done initially. The second operation will shift the bitmask of the given number and doing the first operation on the shifted bitmask will take more cost than it is taking while doing those operations initially. Brute force over the initial addition operations up to 15 and then brute force over the second type of operations 15 times and then add whatever is needed to reach the end i.e 2 ^ 15.

→ Reply

JellyBoi

3 years ago, # |

Can someone try hacking my submission? It seems like a buggy implementation of what I was attempting, which was this. (Negative numbers show up when there aren't parity differences, but they somehow cancel out) Thanks!

→ Reply

silverfish

3 years ago, # |

Screencast + explanations :))

→ Reply

3 years ago, # ^ |

Nice!

→ Reply

Zuleen_2061

3 years ago, # |

Couldn't solve the A problem on this one. felt I was getting ever closer to the solution with every submission but reached a dead-end at last. maan!! being unable to solve A, really does a lot of damage to your confidence...

→ Reply

epsilon_573

3 years ago, # |

Is there any mathematical proof for C that only max(h), max(h)+1 are the possible candidates?

→ Reply