Hello Codeforces,

Manthan, Codefest 17 will take place on Sunday 24th September, 2017 20:05 IST with a duration of 2.5 hours (tentative). The round is rated for both Div1 and Div2 participants and consists of 7 problems.

The Department of Computer Science and Engineering is conducting Codefest from 22nd-24th September. Manthan (मंथन in Hindi, meaning Brainstorming), the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.

The round is prepared by bharat.khanna.cse14, ayush24 and divyam.

We express our heartiest thanks to KAN and gritukan for their help in preparing the contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!

**Prizes:**

Overall 1st place: **INR 25,000** Overall 2nd place: **INR 18,000** Overall 3rd place: **INR 12,000**

1st place in India: **INR 10,000**

1st place in IIT(BHU) Varanasi: **INR 4,000** 1st place in freshman year, IIT(BHU) Varanasi: **INR 1,000**

About Codefest: Codefest is the annual coding festival of the Department of Computer Science and Engineering, IIT (BHU) Varanasi, which is held online and is open to participation by all! Register on the Codefest website now! Total prizes worth **₹400,000/-** up for grabs with events covering domains from Math, Machine Learning, Natural Language Processing and Capture The Flag style competitions. Go to the Codefest website to find out more!

**UPD1: The scoring distribution is 500-1000-1500-2000-2500-3000-3500**

**UPD2: System testing has been completed. Following are the winners of the contest:**

**1. anta**

**3. tourist**

**4. Shik**

**5. LHiC**

**Best in India:**

**UPD: The editorial for the first 4 problems has been posted. We will update the editorial of the rest 3 problems soon!**

7 problems in 2 hours?!

UPD:Contest extended.Maybe it's like Div 2A, Div 2B, Div 2C/1A, Div 2D/1B, Div 2E/1C, Div 1D and Div 1 E?

I think they should extend the contest a bit. 2 hours and 30 minutes would be better I think.

Why so many downvotes? I just said my opinion!

Well the users are about to be crazy.

Codeforces users' attitude to comments :

Useful: Ok, upvote for him, it's nice to me.

Useless:

DOWNVOTE!_(It's not harmful to me and not useful,So why upvote?)_ignore these shit tards my friend.

1

this is the best comment in the whole thread. Why are people downvoting it gvaibhav21?

This contest will consist of lots of mathematical problems. This is speciality of Indian contests. Brush up your maths skills to perform well. :)

YEEEEEEEEEEEEEESSSSSSSSSS!!!

What a handle!!

Biri keno? Gorib naki

Ha bhai. :'(

Hey nigga naga :|

Codefest'17 is excited to present a mathematical programming contest — Mathmania. It will bring a delectable collection of problems which will be an absolute delight for all the mathematics geeks. Cash prizes worth INR 50,000.

Thats nice to hear, because Maths is good for health.

It's bad for the health of my rating though

Yeah same here brother, I have been trying since a year to reach that dark blue area of expert.

because Maths is good for health.You look healthy,I think.(just a joke

Can people currently not enrolled in college participate and compete for prizes? :P Just asking for clarification as the post doesn't put any restrictions!

Anyone can participate and win the overall 1st,2nd and 3rd prizes. Same is true with the best in India prize.

Where can I find the tasks of past years of machine learning and cyber security contests?

These are the links for the previous year's machine learning and CTF contests.

Also, this year's CTF event has already started and can be found here.

This year's machine learning and NLP events will also start soon.

it seems last year's machine learning problems are not available, also registering for CTF is closed

Last year's Machine Learning problems are only visible to registrants of the contest. I think it is some error on Hackerearth's side. Registrations for CTF are open again. You will be able to register now.

it seems registration for CTF is not working, sign up button is not responding in particular.

I did some investigation and it seems the POST request initiated by ajax technique when I press sign up is getting error 500

If name field gets red after sugn up button, just try to login. it worked for me Even tho I never got "successful registration" or email of any sort.

Is it rated?

It is hard to belive that 7 problems for 2 hours... Ok. We will do this. :D

Manthan, Codefest 17 will take place on Sunday 24th September, 2017 08:05 IST with a duration of 2.5 hours (tentative).Hope it'll be a nice round, and no math and geometry.Wish everyone high rating.

And it must be XD.

regular trainings will improove your skill, just try your best

well every one cant have high rating ...

Well..... Didn't the announcements always wish every one high rating?

Maybe I said something wrong o(╥﹏╥)o.

thats just an impossible thing :) only happens if every one gets the exact same score which is impossible

I won't post any comment taking about the future contest.Every time I post such comments I got TONS OF DOWNVOTE!!!!!!!When I saw IIT BHU's event, I was expecting praran26 as one of the problem-setters.

praran26 Fandom!!

contest prepared by IITians.

Is this contest rated?

Sometimes we should enjoy the process of the game rather than care about the rating...

Some people enjoy contests because of the learning opportunity, some want to be the best in the long-term ranking, some compete just for fun. I don't see why anyone //should// anything :P

That said, Ctrl+F "rated".

My First Rated Contest.

All the best to Indian Guys. Your Prime Minister is very aggressive. Namo Namo !

The time in the link text is incorrect it should be 20:05 IST, not 08:05 IST.

Thanks! I have updated it.

The university is next to my home and currently facing students protest for a girl's molestation , i hope they don't do in the contest :D

.

Sorry!!!

gl hf

The contest duration is 2.5hrs but the banner says 8:05 pm — 10:05 pm. It should be 8:05 pm — 10:35 pm.

Where will this contest be held?

On the best platform ever — codeforces. :')

Ah ok — what page will I navigate to to compete? EDIT: Found it

No doubts all IIT guys knows problems...

Even if they did, it won't matter. Cause they won't be able to win. :D

It is 13 minutes before the contest starts and I cannot register. I says "Registration Completed". Shouldn't registration complete 5 minutes before contest?

That means you already registered

LOL I realized that five minutes in when it let me enter submit code tab.

/╲/( ͡⎚ ͜U ͡⎚)/\

Scoring?

Is it rated ?

Your comment is rated.

I know that all of the problems are about religion

Is it really Div1 + Div2? Seems like just Div1 xD

In B, Did you applied DP ?

It smells like DP.

No need for dp.

You need to try all

`a[i]`

as a coefficient forqvalue. Once you have chosena[i] *qyou need to take the best`a[left]`

forpvalue and take the best`a[right]`

forrvalue.This is all I did. Find maxes for each

and return the final sum. One test kept failing. Did we have to return sum%(10^9+7) or something?

No. p<=q<=r. So You Should keep in mind that if q != p then you can't use r if r <= p.

Doing that won't ensure that you chose

`i <= j <= k`

when building sum`a[i] * p + a[j] * q + a[k] * r`

. One of the right solutions (I don't know if there are more) is Pixar's above.missed this. so naive.

me too lol

that's why test case three didn't work i think

Precomputing the best

`a[left]`

and`a[right]`

is DP!Is it dp?

Yes you can call it dp, since to calculate the sum upto index 'n' you have used the sum upto index 'n-1' which in turn uses sum upto 'n-2' and so on. This is only what defines dp..

In some sense yes. But even if you say no. I'm sure that you don't compute the best

`a[left]`

with a for loop for each`a[i]`

. This will get you TLE. I cannot see your solution yet, but I'm sure you precomputed all best`a[left]`

and`a[right]`

values. And that is DP.What about this one?

I think prefix sums are a form of dp.

Of course, this is DP. DP is a recursion + memoization. The recursion here is

`sum(k) = k + sum(k-1)`

and the memorization happens when you compute all values and store them in an array.Ok.

I always thought that it is necessary that we have exponential number of states in the original problem.

i think you meant memoization

but i shouldnt really be talking cuz i suck at dp

Yes, you are correct. Although memoization and memorization bascially mean the same thing. memoization is just the computer science term for memorization.

Hello pixar,

I have looked at your solution but I can see that you are considering all possibilities based on whether p,q and r are either positive or negative? Am I correct?

Yes, you are correct. That is the first solution that came to my mind. After I have submitted solution I realized how it could be simplified.

Am I the only one seeing codeforces like only the left half of it and right side is blank? Edit: sorry I had clicked on mobile version by mistake

shit > Problem D

Waiting for problem B massacre during system testing :)

How To Pass That Case In B With C++ :- 1 -1000000000 -1000000000 -1000000000 1000000000

Please ask these things after the contest

Sorry

why don't you use long long ?

No. long long is out of range as the result will be -3000000000000000000

long long can handle numbers from -9223372036854775807 to 9223372036854775807.

the 1st rule of the fight club — nobody should know about fight club

it is -922337203685477580

8, not7.After the contest ends, can someone tell me how to solve that C? (btw, rip rating)

My solution:

We can distinguish three types of parents for each node:

1. A parent which is high security, which means this node has to have a type that is smaller than k

2. A parent which is not high security, but has a type 1...k-1, so this node could be high security, or have a type from 1...k-1 or from k+1...m

3. A parent which is not high security, but has a type k+1...m, so this node can not be high security, but it can have a type from 1...k-1 and k+1...m

So you can specify a dynamic programming state as node id, parent type, number of high security nodes in subtree, which leaves a complexity of O(N*3*x)=O(Nx) which is small enough.

I didn't manage to implement it during contest successfully, but I'm pretty sure it's correct :/

I came up the above you mentioned in about 15 minutes, but still can't solve it during contest:(

If you know the subtree for this vertex has exactly i high security nodes, how can you know how many high security nodes come from each child?

You can start of with the first child and try to give it j (ranging from 0 to i) high security nodes, and then there will be i-j nodes left for the other children. So here you can keep another dynamic programming state with properties node id (of the child), number of high security nodes left for the remaining children (so i-j) and type of parent. This will take an additional O(4*i*N)=O(Nx), so it should still be OK.

Basically just try out every number for each child and use dynamic programming to avoid TLE.

Can someone tell me after contest what may be wrong with solutions for D in case 9 ? Is there any special condition that you can figure out from the problem statement that is not so obvious? Thanks

At first I thought B was too easy and submitted it 2 times..But then i realized they said i<=j<=k and I stopped...out of 7 problems they cant afford to have two easy problem for newbies like me... Why so cruel!!!!

.

The contest is still running.

In last 2 minutes hardly anyone will benefit from this comment.

Doesn't mean you should be discussing problems and solutions before the contest has finished.

shhhh.... (time is running)

But i try to solve it greedy why is this wrong ? https://pastebin.com/AbG3BwLX

You're missing i <= j <= k

Xd": ok that's dp , i'll hang a rope and suicide

No No. Don't do that !! There is lot more contests to come. This is not the last contest of CodeForces. And also DP problems will come too.

thanks

Did we have to print answer modulo 1^9+7 or something for Problem B? My submission kept failing.

no,use long long int

Wow, in D, type 1 of relationship in statement corresponds to type 0 in input. Nice.

also the structure is not a tree but a forest and "...An object is considered to be neither a part of itself nor a special case of itself". That caused me 2 WAs :(

How to solve E?

How to solve C?

Hack for B?

Overflow:

I hacked with this 1 1000000000 1000000000 1000000000 -1000000000

min or max value of result -3e18 or 3e18 wtf

3 -2 3 -2 1 2 1

Answer: 2

Will dp[len][mask][base] for smaller length, and fixing the first digit that differs work in E?

I approached just like yours(with some hardcoded precomputations) but it was too slow.

the same.

TC4 for C? Does standard tree dp not work?

I think I spent around 45 minutes for understand D task, and maybe I didn't understand it correct :D

Yes, "object", "special case", "part" all these terms are very unintuitive and it was very difficult to reason anything about this. I tried for 5 minutes and for the sake of my sanity I decided to let go this problem even if it later turns out to be very easy :P

Wow, problem D was so beatiful, understanding complicated statement and dealing with stupid corner cases (forest + in query of type 2 if v is ancestor of u then NO), such fun

ah, it can be forest. Beautiful. Wonderful. So I guess that's why I got WA 9.

same

How is it possible to get "in query of type 2 if v is ancestor of u then NO" from the statement? I don't think it follows from "An object is considered to be neither a part of itself nor a special case of itself." sentence. Why a special case of object is object? It looks more like isinstance vs type in python :)

This is clear (but not easy to observe), you simply have no rule to infer that B is a part of A if A is a special case of B.

the best part of the contest were the problem statements. any potterhead there?

Am I right in thinking B, C and E are all DP or DP variants? I got sick of coding C and was still coding E when time ran out, but I'm pretty sure B is a linear DP, C is a DP on trees and E is a recursion which pre-processes cases such as the number of all magic numbers smaller than

b^{ k}so sort-of DP-like?.

It's not that I don't know that. I solved B in about 20 minutes. You were discussing the solution to problem B with another user 4 minutes before the contest was over.

I honestly felt the difficult was A<B<E<D<C. Both E and D are well known problems and E takes less time to code while D is so difficult to understand with so unusual choices for terms and input conditions. In the case of C, maybe I'm approaching it wrong but I couldn't get the problem state in any clearer manner than 4 parameters (2 to specify sub-tree, number of high security, can build high security) with several end conditions.

Actually, your formulation of the

`Problem C`

is almost perfect — it can be solved with`dp[current node][number-of-special-nodes-left][is-neighborhood-of-special][is-neighborhood-of-node-with-whose-number-higher-than-special]`

.After defining the table, you can fill it with knapsack inside recursion.

How did you guys solve the

`Problem E`

?I approached it with DP but it turned out in random testing that dp solution runs slow(about 8 seconds for 10^5 test cases).

If you're at state "I can use every number from now because I guaranteed current number is smaller than R", then you have nothing to do with R so you can just use precalculated values for every base.

Precompute the following values:

`dp[base][length][mask]`

= number of combinations of the digits 0 to base-1. The binary representation of`mask`

determines, which digit should appear odd and which even times.Then you can define a function

`f(base, x)`

, which returns the number of numbers`<= x`

, with each digit appearing an even time. Then the answer is`f(r) - f(l-1)`

.To implement

`f`

:`x`

to base`base`

.`x`

, the answer is`sum(dp[base][length-1][1<<digit] for 1 <= digit < base)`

.`x`

, you need to iterate over the digits of`x`

, keep the mask and build similar sums.I tried just like that(even for the precomputation parts!) but it ran 8sec on my computer given this dataset(generator):

I think you made some mistake somewhere. The precomputation part takes no time at all on my laptop. And computing

`f(base, x)`

has runtime`log(x)`

. So this should be fast enough for`n = 10^5`

. Pretests took 249ms.edit: accepted with 421ms.

Thanks, I found the BUG! it was frequent

`memset`

. I also made it work by fine-tuning`memset`

calls(sadly, though the contest is over).How did you submit? System is not letting me submit

I didn't but I just tested with my generator(see above).

How to Solve B?

Yes, it is also interesting for me (

Fix the position of

`q`

. Then`p`

matches with`max(input[1..pos_q])`

and`r`

matches with`max(input[pos_q...n])`

. Both`max`

es can be calculated inO(1) thanks to easy precomputations.i spent almost one and half hours but couldn't and after seeing this i realize that i know nothing (:

great solution!

I figure this is much much simpler than DP:

This is, my boy, called DP solution.

Btw, one should take care and set INF to at least 3e18, not to 1e18 as I did.

Hello, I find it quite hard to understand this solution and how to come up with it. I see everyone mentioning DP, but I have no knowledge about it, could you give me some source for researching this type of algorithms?

Google "Dynamic programming"

can you please explain how it works correctly?

So first we want to find the best if we just choose p, which is bestp. We can also choose to use the current one for q, which is bestpq, and it builds off of everything before us (stored in bestp) so we can maintain if it is the best over time. We do the same thing for bestpqr which is our answer.

D is just LCA and recording the relations between the query nodes and LCA right? I kept getting WA on test 5, found bug, then got compile error in the last 5 second... (anyone know if that's the right idea though?)

Also, how to solve C + E?

You can solve C with next DP states DP[ root of subtree] [ amount of highest elements] [ value of current element ( smaller than k, equal to k, bigger than k ].

For E I think it is also some easy DP, I think it is called DP on Digts — but I didn't try to write code :)

Can you elaborate how we choose the amount of highest elements for the child? I got tripped up there.

you can just fix the number of special elements in subtree of children = x, and number of special elements we already had before in other subtrees of node = y, update states with x + y

You can run another DP, something like amount of ways to choose

ihighest elements in subtrees of first j childs. And with third dimension in previous post (value of current element), you exactly know what values can be in children ( I think if value of current node equal to k than children must have that state smaller than k, it value of current node smaller than k, than children can have any value, and if it is bigger than k, children must be smaller than k or bigger not equal).Reducing to graph reachability is wrong in D?

Btw, is E really easier than D. For D at least I still have some idea, but for E my mind is completely draw a blank.

E is just well-known DP on digits.

But with large

b, the naive dp on digit will work inO(q* 2^{ b}*log_{ b}a), which is not fast enough. So I think there must be some other observation here.Just precalc dp[B][l][mask] = number of numbers in base B, with len l that have mask of digits mask. Now you can answer fast

Precompute first so you can remove 2

^{ b}from the complexityI don't have 2

^{ b}factor even in preprocessing. I just keep number of digits with odd number of occurences (and I preprocess it).You can do it for each base

At least, E's statement is much easier to understand than D's.

In D : v is not a special case of v if u is a special case of v , v is not a special case of u

just thought about these two in the last 5 minutes where there was no time :(

Hack Case for B ?

For example if somebody set the final answer as 0 then update it in O(n) process then when there have some cases like

4 12 14 16

-1000000000 -1000000000 -1000000000 -1000000000

then he will output 0 instead of correct answer

In problem d we have two rooted forests.

forest 1 and forest 2.

For queries of type 1 just check if vertex 1 is ancestor of vertex 2 in the forest (using the dfs in and out tree).

For queries of type 2 I think the following works: For each vertex let let F(v) be the root of its component in forest 1. Add all edges that v has in forest 2 to F(v).

now do the dfs in the modified graph and check:

vertex 2 is son of F(v1)

vertex 2 is equal to F(v1) and there is a loop at F(v1)

If none of these happens print No.

I forgot to check the loop thing, I think thats why I failed pretest.

How did you solve C?

let Rs[x][i] be the number of ways to color the subtree of vertex x such that there are i max security vaults and the node x has a security less than k.

Let Ry[x][i] be the same but such that node x has max security and let Tb[x][i] be the same but such that node x has security larger than k.

You can then obtain the values of R[x][i] from the values of R[y][i] such that y is a son of x.

So it is like a dynamic programming on the tree.

Best Problems i ever had...

Am I the only one who skipped i<=j<=k condition in B ??? So stupid of me :(

Me too.RIP rating

i realised it after reading ur commment

I solved E as

`even number of times`

means`equal number of times`

and realized it's wrong while testing the samples :(I think if it was

`each of the digits from 0 to b - 1 appears even number of times`

instead of`all the digits from 0 to b - 1 appear even number of times`

, it would've been less confusing.http://codeforces.com/contest/855/submission/30675269

What's the hack for b ?

Try this one 1 -430770061 -822021323 -993560291 674829238 ans is -1515903789120273650

how to solve problem E?

Shit! No large pretest for E. "calc(int b, int l)" still pass pretest!

The time limit for problem C seems very strict to me. I had to somehow squeeze my solution by making stupid optimizations and still think it will get TLEd on main tests.

Can anyone please explain the solution idea for problem C and D? Thanks in advance. During the contest time I thought that D can be solved using LCA and some query on it. But I am not sure.

The solution for D is indeed LCA. Let's say each edge is either type 'a' or type 'b' (because the problem changes the notation mid-problem anyway).

One of the queries is asking if u is an ancestor of v & if the path between the two is composed only of type 'a'.

The other query is to find the LCA of u and v which we denote 'p'. If p exists & the path from u to p is only of type 'a' & the path from v to p is only of type 'b'. (I might have mixed up the symbols)

Along with the parent sparse table and height we use for LCA, we also use a boolean sparse table with the recursion

`reachA[x][d] = reachA[x][d-1]&&reachA[parent[x][d-1]][d-1]`

or similar to see if the path is with only type 'a' or type 'b'.UPD: Ok, my D failed. Maybe you don't want to listen to me about it :D

Problem D:You were right. Letsc[i] be the uppermost (the one with lowest level) node which can be reached fromiby following only special case edges andpart[i] be the uppermost node which can be reached fromiby following only part edges. Calculating these two values is a trivial DP/DFS. Now type 1 query simply asks ifUis an ancestor ofVandsc[V] is ancestor ofU. Type 2 query asks ifUandVare in the same tree (if so, let's sayLis their LCA) and bothsc[U] andpart[V] are ancestors ofL.Problem C:Okay, I am pretty sure I have overkilled this problem. Anyway, there are three types of labels — those less thanK, those equal toKand those greater thanK. Labels from the same type are indistinguishable. I usedp1[node][typeOfParent][numberOfHighlySecureVerticesInTheSubtreeOfNode].Now, there might be an easier way to calculate the state which I don't know so what I do in such cases is use a second dp,

dp2[node][currentChildOfNode][typeOfParent][numberOfHighlySecureVerticesInTheSubtreeOfNode] which works by looping overnode's children and assigning some number of highly-secured vertices for each of their subtrees.So

dp2[node][idx][type][cnt] is equal to the sum ofdp1[v[node][idx]][type][i] *dp2[node][idx+ 1][type][cnt-i] forifrom 0 tocnt.v[node][idx] is theidx-thchild ofnode.~~The value of~~To get the value ofdp1[node][type][cnt] is simplydp2[node][0][type][cnt].dp1[node][type][cnt], we will first need to choose the type ofnode. After that, we can easily obtain its value fromdp2[node][0][type][cnt] ordp2[node][0][type][cnt- 1], depending on which type we have chosen.Note that in the second dp the number of pairs [

node][currentChildOfNode] isO(N) — it's just the number of edges.For fixed i and j, you can combine your dp1[i][j][k] into coefficients of a polynomial, of degree x. Then dp[i][j] is going to be a product of the corresponding polynomials of the children of i. (You have to fiddle around with exactly which polynomials to multiply — basically translate the rules about neighbors of highly-secure vertices).

Triggered.

This takes effort.

Very weird statement. Nice problem, but a better care with the statement would have made a great difference.

Could anybody please explain me why my solution to B TLEd on test 66?

Link to submission

UPD: Nevermind, I initialized my dp array with -1 while -1 is a possible answer. :(

same thing happened with me..

System test is over, should we be able to submit or is there bug?

edit: also cannot view other people submissions

GOOD for fast system testing :)

CF Format hit me hard today. Made the silliest of bugs on B, didn't get hacked throughout on it, solved a much more harder C, and now I have to deal with ending below some people who got many hacks.

So much related to luck is CF format, isin't it ?

Only if I could change a single character on my B and resubmit.

Not able to submit even after tests ? Is there some sort of bug ?

Patience is the key to success

2nd problem was good :)

indeed it was :P

What is the solution for this test case for problem D?

NO

YES

NO

YES

When can I submit??

enable upsolving?

For B, what is problem with this solution If p,q,r is negative, multiply it by smallest ai. Else, multiply it with biggest ai.

Sum those 3 and print.

You have to maintain order of A[i], A[j], A[k] such that i <= j <= k. I think you are sorting your array . This was not allowed

1 <= i <= j <= k <= N.If p is positive and q is negative.Then, that condition(i<=j<=k) won't be satisfied in your algorithm.

Lol. Thanks, I totally forgot that order i,j,k matters ( i is for p and so on..)

For test case 3 p = -1 q = -1 r = 10 A = {1 1 0} Answer = 8

someone please tell me how to solve problem B. If u can give correctness of ur solution will be very helpful

Let

f[i] =a[i] *pandg[i] =a[i] *r. Now letpref[i] =min(f[1], ...,f[i]) andsuf[i] =max(g[i], ...,g[n]). The answer is obviouslypref[i] +a[i] *q+suf[i] for somei.Thx :) clear now

Traverse the array, find the maximum value of p*A[i] for each prefix i ie., Prefix_A[i] = max(prefix_A[i-1],p*A[i]).This can be done in O(N).Now,find the maximum value of p*A[i]+q*B[j] for each prefix j ie., Prefix_B[j] = max(Prefix_B[j-1],B[j]+Prefix_A[j]) — O(N).At last find the maximum value for each prefix k of p*A[i]+q*A[j]+r*A[k] using this Prefix_B array and take the maximum of them ie., Ans = max( C[k] + Prefix_B[k] , Ans ).

Ratings are updated without deleting cheaters now. They will be removed and the ratings will be recalculated, they may slightly change.

Sir, When will you enable upsolving?

Why isn't other's solutions accessible?

Have they been recalculated yet?

The code of these two accounts in many games is similar or even the same: 770780079 pb0207

It seems only 770780079 had his code skipped, shouldn't pb0207 get skipped as well? Is this a flaw of anti-cheat program?

Perhaps this is a flaw in the anti-cheating software, but it seems that the code submitted early should be counted as AC. Because after locking the code, you can view the code of others.

And for example, replace the variable name, add useless function, add useless comments, add a black line. Will make anti-cheating procedures can not be detected.Their code is too similar, and I also participated in those rounds, I do not think this coincidence caused by the coding habits .

854C:77,pb

861C:77,pb

862D:77,pb

862C:77,pb

It should be that both users are disqualified — they shared code, and the "alternate account to look at solutions after lock" is clearly not what is happening. It is definitely flaw of the system. By the way, you are great detective.

what is pretest 4 of problem C??

How to solve problem B. Good problem in my opinion.

What is the test 75 of problem B. Got Wrong answer on test 75 [main tests] → 30680748 -_-

Literally my worst round ever.

Unfortunately, I set the minimum answer to - 10and end up getting hacked.^{18}incorrectly handles the statement "An object is considered to be neither a part of itself nor a special case of itself."I did not properly handle the case wherer= 10^{18}.--> rating gain from MemSQL Round 1 completely erased :D

http://codeforces.com/contest/855/submission/30682143 http://codeforces.com/contest/855/submission/30686094 — what a "tricky" solutions to F (of people from 1st and 4th places). Did setters spend at least 5 minutes on tests to this problem?

Look at solution, I see related problem.

The code of Shik without

`#pragma GCC optimize("Ofast,no-stack-protector")`

`#pragma GCC target("avx,tune=native")`

receives TL30.

¯\_(ツ)_/¯

Oh, common. This is SSE optimized solution.

How many setters even know about SSE/AVX? I doubt authors simple solution works >2x of TL.

SSE speed up anta's solution >4x times: 30682143 30690004

Guys, it's 2017, it's time to read something about vectorization. It's more useful on CF than learing suffix tree and other complex useless stuff.

http://codeforces.com/contest/855/submission/30686153

Without any vectorization and

`#pragma`

s.I put these in the headers of some of my previous codes and there's a significant speed up. So there are no extra things I have to worry about? I can just put it in my template and give my poorly-optimized codes a boost?

Can you tell a bit more about what does SSE/AVX do?

Regular instructions (without AVX/SSE) are executed by the processor one at a time, while AVX/SSE instructions use special registers capable of holding more bits than a regular register, for instance, there are processors that support AVX-256, meaning that it provides instructions for executing operations (such as loading, storing, adding...) on 256 bits (8 integers/floats or 4 doubles/longs...) at once. It is basically a form of instruction-level parallelism (SIMD).

You can ask the compiler for trying to compile your code into those special instructions, it will be done when possible, for exemple, if you're dealing with arrays, loops will take bigger steps and execute operations on more than one element at a time, that can cause speedups of 2, 4 or even 8 times. You could also, instead of asking the compiler, use those instructions yourself with high level functions, but the problem is that you would have to know which version of AVX/SSE the target processor supports.

Is there any reason to not include above pragma's in your code by default?

I don't think so. Apparently what made a big difference was:

The compiler already uses SSE (< 4) instructions with the flag O3. And SSE4 has been around for quite some time, so it will probably work for most online judges. I'm not sure if the compiler still uses SSE4 if the processor doesn't support it, my guess is that it ignores the pragma (I could't find an older processor to test it).

Analysing the differences in the assembly between 30682143 and 30690004, there seems to be very little change except for a few instrutions that get the same result in less steps, those new instructions are some of the ones introduced in SSE4. The speedup in that case is 4x (very high) because those faster instructions are in the middle of the two innermost loops! Which means that including the pragmas in every code will probably not make that big of a difference in the execution time.

So what if I have both the sse and avx header? There's no problems to worry about?

Well... There's usually some loss of efficiency when using both SSE and AVX, but apparently GCC takes precautions when that's the case. So I guess that using both pragmas isn't a problem, but I'm not sure about how much it improves the performance, it really depends on the program you're compiling.

That's so sad I haven't read the statement of problem F during the contest. It is very obvious with such limits that it can be solved by O(NQ) =(

Can someone recommend some DP on tree problems like C, where you compute the DP states inside the dfs and stuff like that? Thanks!

Can you or anybody else suggest a tutorial for the same?

Here are some problems from Codeforces that can be solved using a similar approach: Bear and Tree Jumps, Appleman and Tree, Road Improvement, Ostap and Tree.

Thanks!

When will editorial be published?

I was looking at someone's submission and I found this block of code. Can someone explain what the ONLINE_JUDGE flag is?

ONLINE_JUDGE is a flag used by most OJ's, basically that if the flag not set

`#ifndef`

, enter that bloc of code which change the input/output stream to those files.Editorial right after the contest can be the best gift.

What happened to ratings ? :(

Any idea why the rating changes were removed?

They are back already, i believe it is something like people cheating, so they invalidate person's contest and recalculate the ratings, if you observe, some people had ratings increased by 1 or 2

My little question about problem D:

If object i is a special case of object j and object j is a part of object k. So is object i a part of object k?

It's really bad to find out that you got FST on D because you remembered to examine one

morecase.no, this is like if you have i is a monster truck wheel, j is a wheel, k is a car.

So all car will have wheel but that doesn't mean it has monster wheel

Well, you are right. Many thanks.

Can anyone please help me find the reason for WA in test 5 in the B question...Here is the link to my solution...http://codeforces.com/contest/855/submission/30981196