Hello Codeforces!

On Dec/15/2018 17:35 (Moscow time) Educational Codeforces Round 56 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov and me.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Hello Codeforces!

We are excited to announce that the Hello Muscat Programming Bootcamp registration is open! The camp will take place from March 9th to March 15th, 2019, and our early bird discount of 15% is going until December 15th!

This next edition in our Hello Programming Bootcamp will run in parallel with the traditional Moscow ICPC Workshop — both Bootcamps’ contests will be identical, and contestants will be able to see their position in the General Leaderboard. Every day, both camps will be competing simultaneously, 4,000 kilometers from each other!

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | waynetuinfor | 7 | 190 |

2 | nuip | 7 | 226 |

3 | ToTLeS | 7 | 246 |

4 | danya.smelskiy | 7 | 252 |

5 | Batrr | 7 | 272 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | 9646516 | 75:-20 |

2 | interestingLSY | 49:-24 |

3 | niki4smirn | 12:-1 |

4 | katana_handler | 11 |

5 | marismmm | 8 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | sorry_stefdasca_snsdsux | 0:01 |

B | KerimKochekov | 0:02 |

C | Golovanov399 | 0:05 |

D | Golovanov399 | 0:09 |

E | ko_osaga | 0:25 |

F | vintage_Vlad_Makeev | 0:28 |

G | tfg | 0:09 |

**UPD:** Editorial is out

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Clashes with COCI #3

Best plan is participate in AGC29 and after 15 min participate in this round.

Yes, it is

ratedfor Div. 2ikr

vintage_Vlad_Makeev is back

why gritukan decreasing his rating ?

To provide company to people like me xD

Is D bipartite checking?

yes

Pls explain in detail.

check if each connected part graph is biparite, for each part color verticles with i.e. red and black and calculate number of red verticles. Then the result for each part is 2**red + 2**(part.size() — red) [you can put two's either in red verticles or black ones]. Multiply all numbers for final result, put modulo If m =0 , put 3**n % modulo. See my submission

For a long time I thought graph was connected. After knowing that in hurry I used addition principle instead of multiplication :(.

how to solve D ?

If graph contain odd cycle, answer is zero as no valid assignment can exist.

Otherwise, let us find 2-coloring of each connected component in graph. Say, x nodes are colored red while y nodes are colored black. There are exactly pow(2,x)+pow(2,y) ways to color this component. Take product of this for all components.

Reason of pow(2,x)+pow(2,y). You need sum of edges to be odd. So, one of the value on edge is 2 and other value is either 1 or 3. pow(2,x) assume we assign all red colored nodes with either 1 or 3, giving pow(2,x) choices. Same for y.

It can be easily solved with BFS. And I came up with it a long time later, but I couldn't solve it because of Memory Limit Exceed.

It took me 4 wrong tries to actually realize that author has

notmentioned that Graph will beconnectedin Problem D :'(i asked him . he said no !

Graph doesn't have to be connected.

Yes, I know. I actually assumed from the beginning that it will be that was the problem.

For those wondering about high submissions for G, You might find this problem interesting :)

MDIST

Can anyone share their idea for E and F?

let's say p2[x] is position of x in second permutation, then you need to find number of l2 <= p2[i] <= r2 and l <= i <= r. It's easy to solve it with bit and sqrt decomposition.

Wouldn't the complexity be n*root(n)*log(n) as for each block we need to find out how many values are there lying between l1 and r1, Also, if we use merge sort tree, we can reduce the complexity to n*log^2(n) as the problem is effectively calculating the no. of numbers that are between l and r in a particular range.

In problem E you have to divide both permutations to blocks of length sqrt(n) and than make some calculations.

My idea in E was creating sqrt(n) segment trees, so each of them contains a number of elements in the segment in the array b, that exist in according sqrt-bucket of the array a (t[s][l..r] — number of elements that exist both in in segment a[s*sqrt(n)...(s+1)*sqrt(n)] and b[l...r]). So it should have been some sort of sqrt-decomposition on segment trees.

In the problem MDIST for 2-dim , we have to use 4 segment trees. But since in G there are more than 2 dimensions we have to use 2^k segment trees where k is dimension of the point. Is there any other way to do this problem?

You can optimize slightly by making only 2 ^ (k — 1) segment trees.

with k — 1 https://codeforces.com/contest/1093/submission/47106278

with k https://codeforces.com/contest/1093/submission/47106236

I got a couple of wrong answers on D because I had mod = 1e9+7 saved in my template and forgot to change it to 998244353, and when I finally realized the mistake I corrected it in the last 10 mins. For those who say what's the use of setting mod to such a weird value its for people like me :-p

How to solve C? I made a great effort to solve it by using greedy algorithm only to get a wrong answer on #9.

Yours approach looks correct.

IssueYou are reading int instead of long long int

`scanf("%d",ori+i);`

Yes,you are right. Thank you! Maybe last night I was too tired to stay calm. As a result, I dropped to green :(

It's how you approached it.

I did like this: split array

ainto halves, start filling from the middle ofa(i.e. from right to left of arrayb).Denote the element

b[n/ 2] asx, the two middle elements ofawill bexdiv2 andx-xdiv2 respectively.For the next elements, let's denote the ones we need to fill in the left half and the right half as

LandRrespectively. Also, we haveMinLas the minimum of filled numbers in the left half,MaxRas the maximum of filled numbers in the right.Obviously

L≤MinLandMaxR≤R. From there, you can easily split the element frombinto two most optimal halves that satisfies both inequalities above.I did the same mistake :( So, now I have made a macro with

`int`

as`long long`

.I liked D. So, for any edge (u, v) exactly one of the nodes will have value 2.

If the graph has odd length cycle, then its impossible. Otherwise, simply do a black-white coloring of the graph. Now let # of black nodes be B.

Then in one case you can write 2 in B nodes, and the rest N-B nodes will have 2 options (1,3). In second case you can write 2 in N-B nodes, and the rest B nodes will have 2 options (1,3).

Ans = 2^B + 2^(N-B)

Code: https://ideone.com/2YmsN5

Damn it!! I know understood how people solved this question in around 5 minutes. Nice one!

can u help my with my submission. I' getting TLE for test13

Technically i think this is incomplete, it never says that the graph is connected. So use this solution for every connected component, and then multiply the solution of each one.

Correct. I added that in the comments in my code. I was just highlighting the idea behind problem.

Why this is giving TLE for a trivial case although I've implemented exactly this approach. code

UPD: removed`memset()`

and it ACed :)Are there faster solutions than Nlog^2N in E and Q*(2^K)*logN in G? Got TLE on both.

I see AC codes having a BIT of ordered_set which also runs in O(N.log^2N).

I coded a solution with segment trees in contest , it didnt worked for me. But It worked when i changed to BIT. Probably constant factor in segment tree increases its runtime

See https://codeforces.com/blog/entry/63807?#comment-476888 See if the 2 ^ (k — 1) approach works for you.

Problem D is pretty good ^^

https://codeforces.com/contest/1093/submission/47073053

why did this time out?

`q.erase()`

runs in O(n) time. Use`queue<int>`

instead of`vector`

I am erasing only the 1st entry, that is constant time

I guess, erasing the 1st entry in a vector is O(N)

Damn you are right, queue gave AC :(

For E, I couldn't pass a segtree of ordered_set in 6s. Is there any other better solution? Or it was just intended that we use BIT instead of segtree.

Same here. After writing all that and getting TLE:

I was doing with the same approach but could not complete coding. I think i would also have got the same verdict. :-p

solve problem in offline: ordered_set -> BIT

Can you share the idea for offline approach?

You can pass all tests with naive solution if you want in 5 seconds

Why do you use

`alignas`

in your code? This is the first time that I'm seeing this.With

`alignas(32)`

pointer to array beginning will by dividing by 32-byte, or 256-bits. It allows GCC to use assembler command`vpmaskmovd`

with AVX2 extension. You can read about`vpmaskmovd (_mm256_maskload_epi32)`

this. So it needed only for fast loading to 256-bit cpu registers from memory.This is super interesting (and impressive). I have some followups:

So I assume that it always makes sense to use

`alignas(32)`

before every array declaration? (One side question, it doesn't help to add that before a`vector<int>`

declaration does it?)Do you know any other (hardware) tricks like this?

In case with vector you need to write own class aligned allocator and put it in vector template parameter.

No, I know only about alignment. C++ has operator alignof(type) like sizeof(type).

It's kind of unfair that the problem setters kept TL so tight that this is happening.

Do you mean a merge sort tree?

Am i wrong or O(m * log^2) solution should get TL.

has anyone done E with Bitset ? I got TLE at testcase 13

Almost similar to Problem G

What will be the Rating of problem D?

Why did this get TLE?

Never mind, just got accepted. Never thought memset would pose a problem though.

Same problem tle due to memset. Would never use it again ;)

I think memset is still quite important sometimes. Just need to evaluate better next time!

memset() time complexity in your code is O(MAXN) and you do it every test cases giving total time complexity O(T * MAXN) with T = 3*10^5 and N = 1 for every cases, the code will definitely TLE.

Thanks but I already figured it out before getting accepted lol

Check my submissions if you are looking for challenging hacks. You have to complete 4 funny tasks. Good luck :)

Actually your C is not hackable since the corresponding

`rand()`

sequence does not correspond to a valid input sequence (since you should be able to form some sequencea_{1}, ...,a_{n}out of it per the problem statement).The random sequence b is increasing therefore it is possible to make sequence a.

That is not a sufficient condition. What is a sequence corresponding to

`n=4`

,`b = [2, 100]`

?Here is the random sequence for your code. Validator doesn't accept it.

You are right. I should have made decreasing array. Sorry for it. I uploaded the correct code. 47077025 Thanks for noticing and congratulation for the hack. If anyone else wants to hack: 47077601

I'm quite confident your C is impossible to hack because it must be possible to recover the array from the input, but having your array as input doesn't correspond to any array from the task.

I had the same sqrt(N) blocks idea for E but ended up with memory limit exceeded. Did I derp too hard or was there something I'm missing? I had a 450 x 200005 int matrix at most

What's the hack for problem D?

If someone is clearing the whole array of size 300000 for every test, then it'll TLE out.

No that's not a hack test, as it appears in the pretests (Test: #21)

My bad, I missed a '0' for

`t`

. It should be`300000`

. Test #21 is shy of one '0'.My accepted solution for problem E in

`O(n * m)`

time works`5225 ms`

.Can anybody hack it? Maybe halyavin?

My O(n*sqrt(n)) solution for E got TLE,and O(n*logn^2) one accepted but slower than yours. How amazing!Maybe you are too strong!

My solution didn't get TLE (currently xd) . How are you solving in

O(Nlog^{2}N) ?Your idea is so nice! Why didn't I find it during the contest! Thanks a lot.

Because the problem is offline，you can use Divide and Conquer and Binary Indexed Tree（or Segment tree）to solve it. https://codeforces.com/contest/1093/submission/47076127

In my solution I used information from A Guide to Auto-vectorization with Intel® C++ Compilers. You can try to read and apply in solutions If want picture

I made a input file to hack your solution but Codeforces don't support such a big file. Here's the link on Dropbox: https://www.dropbox.com/s/rg3bp6crc05h94p/in.txt?dl=0 There isn't any swaps and all the queries ask you about two whole sequences.

Sorry, there is such a test case and you pass it.

Can anyone tell me, why i am getting compilation timeout???submission

Solution for F?

halyavin is coming!!!

I've just started using CodeForces and this was my first contest (and I got 2 accepted solutions). Can someone tell me:

why I still dont have a rating ? Will my profile be updated later (after few hours) ?

There is hacking phase after Educational rounds which lasts for 12 hours then the system testing will begin, it takes around an hour. after all of this your rating will be changed.

Wasn't System Testing done before the Hacking Phase? If System Testing has not started, the competition status will be displayed as 'Pending System Testing'. However, the current state of the competition is marked 'Finished'.

No, it was the judging of the late solutions that were submitted on the last seconds.

after the hacking phase, all of the solutions will be rejudged with the complete testset not only the pretests (this is the system testing).

I See.

Thanks @Khaled_Mohamed !

47050528 hey, this is the fisrt time i am competing. Can anyone explain me whats wrong with this code for first problem.

You were doing a wrong greedy.

Since the constraints are pretty small, you can just brute force the answer: an answer

iwill be considered correct if 2i≤x≤ 7i.When input is

n = 29, your code doesn't give any output!After this step:

'x' becomes equal to '1' and it can never become '0' in below mentioned conditions from your code:So it doesn't print the output at this step:

PS: Think easy :)I've seen this code from other users, but I haven't thought of hacking. :(

47059050 Can you please check this submission also. Thanks for explaining!

'rolls'is uninitialised! Change it torolls= 0;thanks man. It got accepted.

Can anyone please tell what is wrong in this solution for the problem D code

`y`

in power function should be from type`long long`

not`long`

.got it accepted. Thank you

Can anyone explain the solution for problem C? I can't understand why we r taking a max of b[i] and b-a[n-i].

a[i]=max(a[i-1],b[i]-a[n-i]) would ensure that a[i]>=a[i-1] which means that sequence is increasing and also a[i]>=b[i]-a[n-i] which means a[n-i]>=a[n-i-1].

Got it. Thanks for explaining.

Can someone please point out why do I hit a time-limit-exceeded on test 2 with this submission?

https://codeforces.com/contest/1093/submission/47082541

Graph doesn't have to be connected. Here is example: n = 3 * 10^5, m = 0 Then this part:

Spoilerwill take n^2 time. Another bug in your code is in this line:

black and red can be bigger than 64. Better option is to just count every 2^k % MOD at the start of your program:

How to solve E?

My way to solve this problem (not very efficient, but it passed):

Represent each number as a point , then the problem will become count the number of points in the rectangle with two opposite vertices (

l_{a},l_{b}) and (r_{a},r_{b}). You can easily solve this problem with compressed 2D BIT.Hi! I did really enjoy solving these problems, thank you to all the authors! Can please someone explain, what does C# dislike in test 10 of D so much, that it gives memory access error? 47082830 I understand, that the best solution is to never use C# for contests, but anyway

Can anyone explain solution to E with ordered statistics set? I saw few codes that get AC but I don't understand them all. And what does this magic loop:

This loop is used in BIT, I guess.

i & -i gets the least significant bit out. This is good read.

Can anyone figure out why my program will get many negative outputs in problem D? 47086094

a *= a % c means a = a * (a%c), which is not a = (a*a)%c, so it will overflow.

I spent ages debugging this issue. From now on I have decided not to use shorthand [+-*/]= operator in C++ in such cases ....

i missed this -_________-

anyone solved D with DP ??

But why?

because i doesn't know the coloring in graphs

It's pretty straightforward. You can use graph traversing algorithms of your preference (BFS or DFS) and just change used[] array to color[] array. You only need two colors for this problem. Then assign all children with a different color of its parent. Also, check that no neighbours have the same color (it is only possible if you have a cycle of an odd length).

As for DP, I have no idea how such a solution would look like, but it probably would be an overhead.

okay this may be straight-forward but what if i take a look as every edge has two vertices and if they are not colored yet i will color each of them with diff colors and my state will be the edge and the color of the 2 vertices so 3D array 0 if not colored 1 if odd ,2 if even but to consideration that you can color 2 times the odd vertices. I know it is much harder this way but i like the way to transform graph to dp. here is my solution http://codeforces.com/contest/1093/submission/47076428

I am right saying this, when it comes to graph DP can be applied only on DAG, am i not ?

i think yes

Will there be an editorial?

How would we do problem E? I am getting TLE with my approach in test case 10

Can anyone help me with my code for D. I'm getting TLE for test13 My Submission

I think the issue is in using cin/cout with scanf/printf.

Guys in my neighbourhood always warned me to not to mix those.

Yeah, they are right.

Declaring vector for graphs and color inside main function instead of globally doesn't seems to be a wise decision.

Here you go Submission

thanks Aparichit_Vyavasthapak

please release the editorial of this contest??

The idea behind E's solution is good. You have to choose such a block size such that n*(block_size+log(n)*n/block_size) is minimised. It is not necessary that optimal block_size is root(n),

PS: E passes with block_size = 3000.

I am pretty sure that problem F is the exact same problem as 204D - Little Elephant and Retro Strings. but instead of using only 2 values he uses k.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Does anyone know when the editorial will be released ?

Can anyone tell me what am I doing wrong in part D.

link : https://codeforces.com/contest/1093/submission/47249694