### zloyplace35's blog

By zloyplace35, 6 years ago, translation,

Hello everybody!

Codeforces Round #368 (Div.2) takes place on August 20th. As usual Div.1 participants can join out of competition.

I am the author of all problems.

I want to thank danilka.pro and GlebsHP for helping me prepare this contest, vovuh for testing it, Roms for statement reading and MikeMirzayanov for platforms of Codeforces and Polygon.

I advise you read all problems, hope, you will enjoy them :)

Good luck and have fun!

UPD1: 500-1000-1500-2000-2500

UPD2: tutorial

• +315

 » 6 years ago, # |   -45 It seems interesting:)
• »
»
6 years ago, # ^ |
-29
##### 竜がこの水物なトピ主を喰らう!
•  » » » 6 years ago, # ^ |   -9 no one will understand what "half-zhang" is unless he is a Chinese...
 » 6 years ago, # |   +17 There's a slight typo in the post. It should be round 368 instead of 365.
 » 6 years ago, # | ← Rev. 2 →   -28 i wish good end for every one.
 » 6 years ago, # |   +115 It's your first round, first rounds are always amazing. As a Div. 2 contestant, I want to thank you for preparing the contest for us.And since it's a Div. 2 contest and there will be a lot of competitors from both divisions, I want to kindly ask the Codeforces team to make sure we will have an acceptable queue and a responsive Codeforces. Thank you.
 » 6 years ago, # |   -24 And the points will be 500-1000-1500-2000-2500 as usual. I guess B-)
 » 6 years ago, # |   -17 It will be tough and tricky I guess. Long break and again regular round, Thanks codeforces. Wish you all have a great jump..:)
•  » » 6 years ago, # ^ |   0 I think it was because of IOI, codeforces doesn't want IOIers to miss the rounds.
 » 6 years ago, # |   -27 vovuh for testing....I think problems will be on Pokemon Go! and we'll have to try to catch Pinsir, seems bit interesting.
 » 6 years ago, # |   -20 Learn to profit from your losses.
 » 6 years ago, # | ← Rev. 2 →   -29 If you are doing your best,you will not have to worry about failure.
•  » » 6 years ago, # ^ |   -85 傻逼真多
 » 6 years ago, # | ← Rev. 2 →   +16 Make sure that server will not lag today.I got the result of my submission after 15 minutes in previous contest.This is happening since last 3 contests.
•  » » 6 years ago, # ^ |   0 Yeah, and I am going to lose my shit if this ended up as one of them as this is the first early contest in months...
•  » » 6 years ago, # ^ |   +5 6500+ registrants already, I'm getting feeling of long queue again !!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +8 The server has handled even more participants before, so don't worry, just concentrate.
 » 6 years ago, # |   -6 _**PERFECT TIMINGS FOR ROUND #368 :D **_
 » 6 years ago, # |   -37 Where on earth is the world full of the flowers If it really existed, I must go I would love to climb the highest mountain no matter what the cliffs areTo live better and love deeply no matter what it takes I do right by myself rather than to seek other's satisfaction I never choose to give up my dream even in my darkest daysMaybe I am not the talent but I have the pure dream I will spent my whole life proving it Maybe I am not the hand of the diligent but I would keep exploring to stake my youth without any regretsTo run forward against the cold shoulders and the jeering crowds if we didn't go through all kinds of hardships and difficulties, how can we feel this wonderful life The destiny can't let us down on my knees even we have paid in blood embraceTo keep running with the pride of childlike simplicity if we didn't persist to the end, how can we see the glory of the life Better to light up a life than accept a life we don't want One day it will be rebornThe charming future always says hello to me even suffering is my only companion, I will keep moving I wanna sail on the bluest ocean no matter whether I will come back or notI am lonely when I will fail that's the sign of the coward As long as I am alive, please clench our fists before the daybreak we are even more brave to wait for the most dazzling moments during the sunriseTo run forward against the cold shoulders and the jeering crowds if we didn't go through all kinds of hardships and difficulties, how can we feel this wonderful life The destiny can't let us down on my knees even we have paid in blood embraceTo keep running with the pride of the people if we didn't persist to the end, how can we see the glory of the life Better to light up a life than accept a life we don't want Don't compromise until we get older for the goodness of our hearts.
•  » » 6 years ago, # ^ |   +3 I think you've got the wrong post...but your words are really nice:)
 » 6 years ago, # | ← Rev. 2 →   -131 if(contestIsBy("amd")) scoring = "500 , 1500 , 2000 , 2500 , 3000" solved = "2000 , 800 , 20 , 1 , — " else scoring = solved = usual 
•  » » 6 years ago, # ^ | ← Rev. 2 →   +98 I'm sorry but let me tell you what it looks like to me.amd makes contests for everyone. But a contest has hard problems so you decide to shit over his work. And it's not even in the thread for that contest, but you feel the need to do this in a totally unrelated thread (probably just to get some cheap contribution?)Am I wrong? Because to me it just seems entitled, disrespecful and inconsiderate, especially after this.
•  » » » 6 years ago, # ^ |   -52 come on! I was just taking a break with commenting under this post! contribution ?!?! let it be -1000 or +1000 ... who cares ?! and about amd ... I just joked ... I know amd's contest aren't bad or useless ... the are pro
•  » » 6 years ago, # ^ |   0 You assign scoring and solved to strings which is not very useful, but let's skip it for now.The most confusing part in your code is that you assign usual variable both to scoring and solved, but they have entirely opposite meanings: this way the hardest problem would be solved by the most people and visa versa.The proper way would be: scoring = usual_scoring; solved = usual_solved; 
 » 6 years ago, # |   0 Must be an interesting contest, 7000+ participants. Good luck for ya all.
 » 6 years ago, # |   +2 Where is scoring distribution?
 » 6 years ago, # |   +15 7k+ participants. I hope the queue wait time for a submission is low.
 » 6 years ago, # |   0 coders are increase day by day.
 » 6 years ago, # |   0 i think it will be a nice contest , i wish high ratings for all :D
 » 6 years ago, # |   0 I really like round. Thanks for nice contest :)
 » 6 years ago, # |   0 Can anyone tell me how to do C in a time shorter than O(n^2). That was the best I could come up with.
•  » » 6 years ago, # ^ |   +11 If n <=2 ans = -1if n is odd ans will be (n*n-1)/2 and (n*n+1)/2 if n is even ans will be (n/2*n/2-1) and (n/2*n/2+1)
•  » » » 6 years ago, # ^ |   -14 Interesting. Thanks for the help!
•  » » » 6 years ago, # ^ |   +3 I didn't realize odd can be handled so easily!! I factorized and all that.
•  » » » 6 years ago, # ^ |   0 how do coders come up with formulas like these? do they need to have a previous deep knowledge in mathematics/geometry or do they just notice the relation between the 3 sides using examples of right triangles ? or is it something else ?
•  » » » » 6 years ago, # ^ |   +5 No, no, no. It's much more simple. They just google it. Here is justification for that behavior Click.
•  » » » 6 years ago, # ^ |   0 I had thought about the even one but couldnt come up with the solution for the odd cases. Thanks :)
•  » » 6 years ago, # ^ |   +7 You can use (n+1)^2-n^2 = 2n+1.N is odd -> use that formula with N*N.(N*N is also odd) N is divided by 4 -> use 3,4,5 Else -> divide N by 2 and use the formula
•  » » » 6 years ago, # ^ |   0 There are some interesting methods for this problem. Thanks for the help!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 a = n^2 — m^2, b = 2*n*m, c = n^2 + m^2m < nAssume that the side is one of a,b,cand validate it.for Example iterate until 1e5 to check the m and check if the given side is divisible by 2 * n and that L / (2 * n) < nFor validating the other two values, you can use binary search to find the sqrt ofn^2 — c, and b — n^2 Also you'll iterate only till 1e5 because the maximum length is 10^9 so you can iterate till the sqrt of 10^9 So the total complexity is O(sqrt(N) * Log(N))
•  » » » 6 years ago, # ^ |   0 Thanks! I should've realized the max I could go was the square root of 10^9. This makes a lot of sense, thanks again.
•  » » 6 years ago, # ^ |   +1 I used binary search and used the traditional 3SUM interview question to solve it in nlognwhere n is the number of perfect squares less than 10^9
•  » » » 6 years ago, # ^ |   0 lol forgot to consider the case of n = 2
•  » » 6 years ago, # ^ |   +18 every pythagorean triplet can be expressed in the form of a^2 + b^2 = c^2 where a = m^2 — n^2 b = 2mn c = m^2 + n^2 Refer this if x is even, it can be substituted in b = x = 2mn thus x/2*1 = mn m = x/2, n=1 deriving a and c from this as : a = (x/2)^2 — 1, c = (x/2)^2 + 1 if x is odd, it can be substituted in a = x = m^2 — n^2 = (m+n)*(m-n) 1.x = (m-n)*(m+n) m-n = 1, m+n = x m = (x+1)/2, n = (x-1)/2 deriving b and c from this as : b = (x^2-1)/2, c = (x^2+1)/2 PS : Look for the corner case when x < 3 :)
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 use the property of Pythagorian triplets : if n is odd then : b=(n*n-1)/2 and c=(n*n+1)/2 else: b=(n*n)/4-1 and c=(n*n)/4+1for checking "-1" condition just check the divisibility by 2 in first case and by 4 in second case. and check if any of b or c is 0 then print "-1". Time Complexity : O(1)
 » 6 years ago, # |   +1 First contest for me here! I struggled to see where I was going wrong in B — I'll read the editorial ASAP.
 » 6 years ago, # |   0 Nice problem set, I suspected that the problem set was too hard when I came up with complicated versions of solutions when I solved it, until I locked my problem and viewed others' solution went like "Oh... crap. Now my solution seems a risk of implementation."I wonder if problem E has anything to do with sqrt decomposition, wondered why was the ask query is limited to 2000... Looking forward to see the solution in the editorial as I spent my time on clunky solutions and had no time for it! =D
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Problem E can be solved by 2-Dimension Segment tree.(Which Calcualtes the sum)Because the "Ask" Query is only 2000, You can precalculate the number of lightbulb which is included in this query for each garland. Update the i-st garland. — O(garland_size) * log(NM) Calculate the sum of the lightbulb which is included in query. — O(logNM)*2000 Repeat for All i(1<=i<=k) It is O(Sum of Garland_size + 2000*k)*log(NM)=2000*2000*log(2000)
•  » » » 6 years ago, # ^ |   0 And for the "Switch" query, you can just make an check array. Just switch true and false of the check array. — O(q)The "Ask" Query will calculate the sum of check[i]*Number_Of_LightBulb[i][query_num]. — O(k)The final complexity is O((n*m+2000k)*log(NM)+q)
•  » » » » 6 years ago, # ^ |   0 Thanks for the writing, I understood most of it besides one thing: Why the 2D-segment tree, isn't it enough to compute each garland individually? I suppose 2D segment tree can't speed up the process as different parts of the garlands are inside of the ask range.
•  » » » » » 6 years ago, # ^ |   +1 Without the 2D-Segment tree, We have to do the Loop which Update the i-st garland — O(garland_size) Calculate the sum of the lightbulb which is included in query — O(garland_size*2000) It is O(Sum of Garland_size * 2000).Because of part 2 has an bad complexity, we have to use 2D-segment tree.
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I just implemented a Quadtree to solve it, and I got smashed my MLE. I am not familiar with implementing both 2D segment tree and quadtree, could you please kindly help point out my mistake? (Maybe I should use an array instead a bunch of pointers?)Thanks in advance. =DUPD: Nvm, fixed it. =P
•  » » 6 years ago, # ^ |   0 I have found another solution for Task E. For every ASK query : - split each garland in continuous subarrays which are included in the query rectangle and sum up the values of those bulbs. - one split can be generated only when the garland 'jump' an edge of the rectangle (maximul 4 * N)The final complexity is O(n^2 * log(n)) 19998646
 » 6 years ago, # | ← Rev. 2 →   +6 So many people solved C... Was it really that easy or you just write the bruteforce out of despair like me? for (ll b = 1; b <= 1000000000; b++) { ll sum = a * a + b * b; if (isSquare(sum)) { ll c = getSquareRoot(sum); cout << b << " " << c << endl; return 0; } } 
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 It's solution is googleable.
•  » » » 6 years ago, # ^ |   0 System testing will tell..
•  » » » 6 years ago, # ^ |   -6 Ok. So, at least, I didn't cheat =)
•  » » » » 6 years ago, # ^ |   +28 Using prewritten codes or resources that are published before contest is not considered as cheating.
•  » » » » » 6 years ago, # ^ |   -25 Why do you want to make me upset?
•  » » » » » » 6 years ago, # ^ |   +10 Why do you want to make me upset?)
•  » » » » 6 years ago, # ^ |   +20 If the solution is googleable it just means the problem is unoriginal, nothing more.
•  » » » » » 6 years ago, # ^ |   0 yeah! the problem setter should be upset LOL :P
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 It took me a long time to figure out the equation version. The last two sample cases are really suspicious, that made me realized you could always let X=(a+b)*(a-b).For n%2 you could also find an equation, pick up your pen and you will be surprised. =D
•  » » 6 years ago, # ^ |   0 Maybe there's a math formula.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +18 Every pythagorean triple (a, b, c) can be written as:a = m^2 — n^2b = 2mnc = m^2 + n^2for some integers m and n.From here, it's only a matter of finding a combination of integers m and n that will satisfy one of the three equations and then just substituting to find the other 2 sides.For example if the given side is even, it can always be substituted in the b equation where m = 1, and n = b/2. And if the given side is odd, it can be substituted in the a equation: a = (m^2 — n^2) = (m-n)(m+n) ==> 1*a = (m-n) * (m+n) ==> m-n = 1 and m+n = a.
•  » » » 6 years ago, # ^ |   +6 A minor thing: not every tuple of positive integers (a,b,c) such that a^2 + b^2 = c^2 can be expressed according to those formulas. Example: 9, 12, 15. (https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple)It is true that every primitive Pythagorean triple (one in which the sides don't have a common factor) can be written with those formulas for some m & n. Some non-primitive triples can be written that way too.
 » 6 years ago, # |   +7 Is the intended complexity for E O(ASK_Q * K * log^2(N)) or there is a better solution?
•  » » 6 years ago, # ^ |   0 Can you please explain your approach? I couldn't come up with anything other than sqrt decomposition. :\
•  » » » 6 years ago, # ^ |   +4 Let's make a list for each garland the i-th list contains the ASK queries that the i-th garland was on during them. Now for each garland let's enumerate through its cells and add the value of the cell to a 2D BIT. And then for each ASK query this garland was on during, let's update its answer by the sum of the rect it represents. After updating all the queries we undo the added value of the cells.
 » 6 years ago, # |   0 the second question was too interesting, at least for us newbies, some would pick up the hard implementation approach while there's a simpler solution also..
 » 6 years ago, # |   -14 Saw a O(n*m*q) solution for problem D, writes a generator at the last moment to hack it.The contests ended and I was left with no time but to hit myself hard with a facepalm.http://codeforces.com/contest/707/hacks/249193/testGOD DANG IT I WROTE "cout<
 » 6 years ago, # | ← Rev. 2 →   0 Wasted so much time on B(didn't notice that you can't set up a bakery on a storage city) that I had no time for C, but what is the approach for C, do I have to use these?a = k * (m^2 — n^2)b = k * 2mnc = k * (m^2 + n^2)
•  » » 6 years ago, # ^ |   0 The editorial should be published shortly...
•  » » » 6 years ago, # ^ |   +1 Not yet published :(
 » 6 years ago, # |   +5 How to solve D? I encountered persistent data structure for the first time in my life...
•  » » 6 years ago, # ^ |   0 Offline
•  » » 6 years ago, # ^ |   +4 Yeah, offline. I have built tree of requests and walked over it using DFS
•  » » » 6 years ago, # ^ |   0 Iam keeping a counter that counts changes, and therefore, I know the answer instantly after each update.
•  » » » 6 years ago, # ^ |   0 Huh, I did the same but recursively, which TLE-d. I guess function overhead was too much.
•  » » » » 6 years ago, # ^ |   0 Never mind, yours is recursive too.Oh, the way you handled the third case is pretty neat — I didn't do that.
•  » » 6 years ago, # ^ |   0 I also interested in idea of solution of D.
•  » » 6 years ago, # ^ | ← Rev. 5 →   +6 You can do the operations 1, 2, 3 and their reverses in O(1) and keep track of the total count and the count of the specific shelf.For operation 4 I made a list of adjacency for each operation, then after processing this position I would process all adjacent positions and revert the operation after all adjacency positions are processed.For example, for the testcase:3 3 51 1 13 14 04 13 1Then:adj[0] = [1, 3]adj[1] = [2, 4]adj[2] = []adj[3] = []adj[4] = [5]adj[5] = []You should process the queries offline. Position 0 is initial state.The code.Passed systests! Unfortunately I didn't solve C and submitted D at the very end and it wasn't worth much. Anyway, it was an interesting problem to solve.
•  » » » 6 years ago, # ^ |   0 Hi. What does adj[i] represent for? What value it stores? Thank you. ;-)
•  » » » » 6 years ago, # ^ |   0 You have q queries to process, they are numbered from 1 to n, and query 0 is the initial state, when no query was processed. You should store them, calculate and then print the results.adj[i] is a vector which stores all queries that should be processed right after query i.In the testcase I used you see that query nº 4 (4 1) restores the state right after query nº 1 (1 1 1). That means that query nº 4 should be processed right after query nº 1, so adj[1] contains 4.Notice that operation 4 doesn't act on the shelfs so processing it is simply saving the current count of books.Since all operations done in the shelfs are invertible, and done in O(1), you can process the queries in a DFS manner without spending much time restoring the state of the shelfs.
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 My solution is probably not the intended one, so it may TLE but this is the best I have came up with during the contest.Keep a vector for each position, for each of the queries...4) I will start with the fourth one, keep the call time and the reset time. Reset the counter back to the state by tracking the outputs. Time complexity O(1)1 & 2) Binary search the lower bound of 4th query call time and the upper bound reset time(Both initially zero), check the size of the operations made outside of the range. Check parity to see if the shelf is filled/not, push back the current time if update is needed. Time complexity. O(logN)3) Foreach column do the same thing as 1&2. Time complexity O(MlogN)Worst case scenario O(M * q * log N), that should be 3e8 operations, and I have faith in the CF server could handle 1e9 operations/s... Hopefully :PUPD: System test case 15 got me, surprisingly by wrong answer not by TLE...
•  » » 6 years ago, # ^ |   0 D can be solved by implement persistent segment tree directly and answer query online.I used one segment tree of size n and n trees of size m.The first tree store roots of the n rows, flip state　and how many 1s in each row.Tree of each row store value of each position.The complexity is O(qlogn) in time and O(qlogn) in memory. My Code
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 I like your approach. I solved it directly with a persistent data structure :PI represented the state as vector*>, and I'd just need to create 1 new shelf per query. This passed in 0.5 seconds, but was about 100MB less than the Memory Limit, so it might have MLE'd under certain conditions.Check out my code
 » 6 years ago, # | ← Rev. 2 →   +18 Problem c is trivial with euclids formula.triples are of form (j * j - i * i, 2 * i * j, j * j + i * i) with j > i. If n is not 1 or 2 you can always do it:If n is odd make the first term n by taking i = n / 2, j = n / 2 + 1 (so we print 2 * i * j and j * j + i * i);if n is even make the second term n by taking i = 1, j = n / 2 (so we print j * j - i * i, j * j + i * i)I think this problem made it too tempting to goo into wikipedia and search "pythagorean triple"
 » 6 years ago, # | ← Rev. 2 →   +51 20000000 th submission I can't belive , 20000000!!!
•  » » 6 years ago, # ^ |   +1 It should have been AC!
 » 6 years ago, # |   +4 Surprised so many people solved C..
•  » » 6 years ago, # ^ |   +6 We have access to google, and we ran the search "Pythagorean triplets".Sadly, I'll fail systests thanks to n=2
•  » » » 6 years ago, # ^ |   0 What a sad story. I would have ended in the same spot if there wasn't a sample for n=1.
•  » » » » 6 years ago, # ^ |   0 I checked both 1 and 3, but n=even was very trivial compared to my n=odd logic(I didn't realize that was trivial too) and ended up neglecting 2. Yes its very sad. I was hoping rating rise, now, expecting fall.
•  » » » 6 years ago, # ^ |   0 I didn't consider n=2, luckily someone hacked me and I found the bug.
 » 6 years ago, # |   0 Is there anyone who kept on getting WA for pretest 4 in D ? Here is my code 20003997
•  » » 6 years ago, # ^ |   0 Oh, you have the same solution with mine. Take a look on it, my code have passed pretests
•  » » » 6 years ago, # ^ |   0 I found the mistake ..while doing DFS I thought that while going back from some edge remove is inverse of add ..but this is not true unfortunately..
 » 6 years ago, # |   +70 I was trying to hack someone's code for E (Garlands) with the largest possible test case (about 92MB) using a generator, but then I got a verdict saying "Generator crashed"--my generator got a TLE instead.
 » 6 years ago, # |   +3 I need more 3 minutes ,so that I can solved problem D. It's a sad story.
•  » » 6 years ago, # ^ |   +7 I missed submitting Dijkstra for B by 10-20 seconds.. Yeah I know it has a better solution but couldn't come up with it.
•  » » » 6 years ago, # ^ |   0 How exactly would djikstra help here . Wouldn't fit in the time limit i guess .
•  » » » » 6 years ago, # ^ |   0 Just insert into set all k storages with distance 0, then run Dijkstra.
•  » » » » » 6 years ago, # ^ |   +3 Overkill
•  » » » » » » 6 years ago, # ^ |   0 What is the more efficient solution then?
•  » » » » » » » 6 years ago, # ^ |   +11 Answer is one edge.
•  » » » » » » » 6 years ago, # ^ |   +3 Since we have only positive edge weights, it is enough to check the direct neighbor nodes of all cities with storage. Adding more hops to the route will just give a worse answer
•  » » » » 6 years ago, # ^ |   0 Well mine version passed the system test. Guess the time limit wasn't that tight.http://codeforces.com/contest/707/submission/19986208
•  » » » 6 years ago, # ^ | ← Rev. 4 →   0 You just need to look at the k cities with storage.For each city with storage you analyse all the adjacent cities. If the adjacent city does not contain a storage, then you can create a backery there.As you move along these k cities, you track the minimum distance between the city with storage and adjacent cities without storage. There is no need to go deeper.
•  » » » 6 years ago, # ^ |   0 I am not sure that Dijkstra will pass
 » 6 years ago, # |   +8 The solution of problem C can be easily found on many websites, while it's much harder to figure out the solution by oneself in a short period of time. Anyway, great contest, no lags :)
•  » » 6 years ago, # ^ |   +3 I can't find it, any links? thanks!
•  » » » 6 years ago, # ^ |   +3
•  » » 6 years ago, # ^ | ← Rev. 3 →   +3 @JeffreyHo ... I figured out a solution myself which is why I guess it is quite a unique one.I stored the factors of n in a vector. Since we have n*n to deal with, I basically decomposed n*n into all possible combinations of any two of n's factors p,q such that p*q = n*nnow, a*a +n*n = c*c => n*n = (c-a)*(c+a) = p*qNow assume min(p,q) = c-a and max(p,q) = c+a. Now just check if equation is satisfied. My codeWhat I still can't figure out in my own code is ... how hypotenuse cases are handled. My code seems to prove that if a*a + b*b = c*c then there exists x*x + c*c = y*y, OR x*x + a*a + b*b = y*y ... Does this always hold true or is there a counter case. A proof from someone would be really helpful.
•  » » » 6 years ago, # ^ |   +4 My code always produced answers in which the input was not the hypothenuse. Indeed, if it is possible to get an answer, then there is an answer in which the input is not an hypothenuse, because if the input is a power of 2, 2^n, a possible answer is 2^(n-2)*3, 2^(n-2)*5, and if it is not, let the input n=r*k, where k%2=1, and k>=3. Then a possible answer is 2*(k/2)*(k/2-1)*r,r*((k/2+1)^2-(k/2)^2). So your code has no problem if it doesn't consider the case of hypothenuse
 » 6 years ago, # |   0 can O(m*q) solution pass D?
•  » » 6 years ago, # ^ |   +3 You can keep a counter that keeps track of change of number of books, so you won't have to iterate over the shelves.
•  » » » 6 years ago, # ^ |   0 You are right.I didn't think of that point and I submit a solution just to check if it will TLE.But now I find I m too simple because there is no big test in pretest...
 » 6 years ago, # |   0 Can anyone tell me how to hack?
•  » » 6 years ago, # ^ |   +12 1) Lock your solution. (After you passed its' pretest, of course)2) Go to the room section.3) Select anyone's solution of the locked question.4a) Input your test case manually like you usually do in local, this is recommended for simple logic flaws.4b) Input your test case by a generator(by your program), this is recommended for pulling of a TLE.
•  » » » 6 years ago, # ^ |   0 Thank you,I will try it next time.
 » 6 years ago, # |   0 how to solve D.i could quyery out 1 and 2 or 3 and 4 in O(1) but how to do 1,2,3,4 all in O(1) time
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 Instead of treating each query one at a time first store all the queries. Then create a tree where for node p the parent node is either p-1 if the query is 1, 2, 3 and k[p] if the query is 4. Then instead of processing the query in order perform a DFS on this tree. Then, as you said it takes only O(1) for queries 1, 2, 3 and query 4 is latent in the order in which we process the query. Therefore O(q).I'll add my submission if it passes system tests.
•  » » » 6 years ago, # ^ |   0 could you elaborate your algorithm a bit please .I know dfs .Thanks for replying
•  » » » » 6 years ago, # ^ |   +3 For reference, 20018322For example take the test case, 4 2 7 3 2 2 2 2 3 3 4 0 1 3 1 4 2 1 2 2 In which we can form the tree,  0 / \ 1 4 / \ 2 5 / \ 3 6 \ 7 where instead of the order 0->1->2->...->7, if we perform with the DFS order of 0->1->2->3->2->6->7->6->2->1->0->4->5, all the queries can be treated in O(1) as you have mentioned with O(q) queries.
•  » » » » » 6 years ago, # ^ |   0 Thanks for your explain! ;-)
•  » » » » » 6 years ago, # ^ |   0 What if a node has more than one child.
 » 6 years ago, # |   +10 "being turned on, brings Alesha some pleasure, " ...
 » 6 years ago, # |   +3 A completely wrong program (http://codeforces.com/contest/707/submission/20000102) caused by a misunderstand of the problem (div2D) pass pretest... So weak pretest !!(crying,/(ㄒoㄒ)/)
•  » » 6 years ago, # ^ |   0 pls tell an approach to solve D
•  » » » 6 years ago, # ^ |   +1 Use SegmentTree. Build a tree for operations. Every operation's which type is 1 to 3 father is the version before it. For type 4,it's father is k. Then use dfs. When you go down ,Change it. When return ,Change it back. Record ans when you dfs.Sorry ,My English is not good
•  » » » » 6 years ago, # ^ |   0 thank you your English is good:)
•  » » » » 6 years ago, # ^ |   0 This is not a segment tree, just tree, I guess
•  » » » » » 6 years ago, # ^ |   +3 You must use some data structure to do changes and qureies. My focus is not on SegmentTree. You must have misunderstood what I meant.
 » 6 years ago, # |   +48 a classic problem is not OK for contests! I'm talking about problem C.
•  » » 6 years ago, # ^ |   0 anyway it was a new experience, I'll google your problems in your next contest
•  » » 6 years ago, # ^ |   +7 It is actually a good problem for educational rounds.
•  » » » 6 years ago, # ^ |   +1 That's exactly my thoughts about C.The coordinator could've asked for another C problem and used this one in a future educational round.This one aside the contest had very good problems.
•  » » 6 years ago, # ^ |   0 I got AC without Googleing. Running time was O(n) though, not O(1).
•  » » » 6 years ago, # ^ |   0 Could you explain your approach?
•  » » » » 6 years ago, # ^ |   +5 brute force
 » 6 years ago, # |   0 I have question about third task, maybe someone can invent good solution. Let's suppose n must be a hypotenuse. What is minimal complexity for solving third task then?
•  » » 6 years ago, # ^ |   +4 https://www.quora.com/Trigonometry-mathematics-How-can-I-get-a-Pythagorean-triple-from-a-given-hypotenuse-if-it-existsThe first answer gives a pretty nice solution it may be possible to solve it faster tho.
 » 6 years ago, # | ← Rev. 4 →   +50 Why do the problem — setters include question "C" — div2 where u need to search for formula on google and i am wasting my time thinking of logic , totally useless question that too with a wise score of 1500 pts .One of the Worst Contest I gave till now on Codeforces.Edit : For anyone who didn't want to solve with that formula look at my accepted solution . Your text to link here...
•  » » 6 years ago, # ^ |   +6 Totaly Right.
•  » » » 6 years ago, # ^ |   -9 and because of this , my rating will suffer today , and those who google each and every question for copy pasting answers will enjoy :(
•  » » » » 6 years ago, # ^ |   +3 It's not that hard to find out the equations by yourself... But yeah, still, it takes a pretty long time to come up with it from 0 to 100.
•  » » » » » 6 years ago, # ^ |   -7 Well , I am pretty sure that those 2000 people didn't derive the equations
•  » » » » » » 6 years ago, # ^ |   +3 I mean, the observation itself definitely deserves a Div2C difficulty, but I agree that it solution can be googled made it unfair both in terms of difficulty and the observation time.
•  » » » » » » » 6 years ago, # ^ |   +3 Deriving this is actually kinda easy. I was the first person on Div 2 to solve C, and I pretty much just used a very simple O(1) derived from simple factoring.
•  » » » » » » » » 6 years ago, # ^ |   0 What factoring?
•  » » 6 years ago, # ^ |   0 Those 11 suggestions are very helpful. Thanks buddy :)."Silly mistakes and fate are unavoidable, and I am not sure about the latter" -bydefault
 » 6 years ago, # |   +14 Very Bad Pretests in A & C.
•  » » 6 years ago, # ^ |   0 I guessed it from the "pretest passed" response. it was so quick. :D
•  » » 6 years ago, # ^ |   0 But apparently, the pretests for E are very strong, since only one submission that passed the pretests failed the system test. I'm not sure about hacked submissions, though.
 » 6 years ago, # |   +12 In problem A , I thought that there's no space between characters of each line , and my code passed the pretest ... I know it's my mistake but I think you should use better pretests ...
 » 6 years ago, # |   +43 I guess the complexity of intended solution of pE is O(2000*(n+m)).For each "ASK" query, all garland enter or exit the rectangle range at most O(n+m) times. We can exploit this property and consecutive sum dp to solve this problem.
 » 6 years ago, # |   0 can any one tell me why this failed the test 19984978?
•  » » 6 years ago, # ^ |   0 never mind found the mistake
•  » » » 6 years ago, # ^ |   0 The unseen '\n' is the deadliest.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 what is the mistake? I am same as you and i got WA in 5http://codeforces.com/contest/707/submission/19984724
•  » » » » 6 years ago, # ^ |   0 mine are different my code shows black&white even if there is a coloured pixar but it should show colorful
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I think your problem is than when you read n and m, the first char you read is the '\n' after the two integers. Then, you don't read the last character of the input, and if that character is the only one that is not W,B,G, your answer will be B&W, when it should be color. Use scanf("%d %d ",&m,&n) to skip the '\n' and avoid that mistake.
 » 6 years ago, # | ← Rev. 2 →   +21 c is the worst problem ever you can google it and get the mathematical law
•  » » 6 years ago, # ^ |   +8 Yet you failed at that google-able worst problem ever.
•  » » » 6 years ago, # ^ |   0 i tried to solve it without cheating
•  » » » » 6 years ago, # ^ |   +3 Cheating or no cheating, it's still not the worst problem ever. Though I might agree if you said unoriginal.
•  » » » » » 6 years ago, # ^ |   +4 also it's not it's not a logical or implementation problem if you know the mathematical law you will get Accepted without thinking on the solution
 » 6 years ago, # | ← Rev. 3 →   +12 This contest was for hackers, not for codersDarn I failed B because I set infinity as 10^9, not 10^9 + 1 :(
•  » » 6 years ago, # ^ |   0 i set it to 10^9+1 but now i got TLE on test41why dont problem setters just use hard and extreme test cases for the contest
•  » » » 6 years ago, # ^ |   +1 Because we all need hope.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 your TLE should not be for that . my infinity was 1e15 and get AC, actually it is o(m), for each edge you should check if one head is storage and the other is not and answer is the minimum value of the "OK" edges
»
6 years ago, # |
-33

why my "19990351" is WA?

# include

using std::sort; using std::max; using std::min; using std::cout; using std::stack; using std::cin; using std::endl; using std::swap; using std::pair; using std::vector; using std::set; using std::map; using std::multiset; using std::unique; using std::queue; using std::greater; using std::string; using std::priority_queue; using std::lower_bound;//返回第一个不小于 using std::upper_bound;//返回第一个大于 using std::max_element; using std::min_element; typedef long long LL; const double PI = acos(-1); const LL LINF = 0x3f3f3f3f3f3f3f3fll;//4e18 const int INF = 0x3f3f3f3f;//1e9 const double eps = 1e-8; const int MOD = 1 << 16;

int n, m;

int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) { char ch; scanf("%c ", &ch); if (ch=='C') { cout<<"#Color"<<endl; return 0; } if (ch == 'M') { cout<<"#Color"<<endl; return 0; } if (ch == 'Y') { cout<<"#Color"<<endl; return 0; } } cout<<"#Black&White"<<endl; return 0; }

•  » » 6 years ago, # ^ |   +2 http://codeforces.com/contest/707/submission/19990351You read the '\n' characters so something like this: (分行符號也被讀進去了, just a translation in Chinese don't judge me CF)1 2 B Mwould cause problems as the read input would be '\nB'.
 » 6 years ago, # |   +1 Can someone tell me where is the mistake? http://codeforces.com/contest/707/submission/19983693
•  » » 6 years ago, # ^ |   0 You have 2 nested loops both using the integer i.
•  » » » 6 years ago, # ^ |   0 that's not the mistake because i is redefined in inner loop so outside i is unaffected.
•  » » » 6 years ago, # ^ |   0 That's not the real problem as the nested i doesn't affect the another one. The problem is getline stops at ' ' so only 1 character was read per loop.
•  » » » » 6 years ago, # ^ |   0 I tested in my system, it reads whole line however problem i found is that it's not scanning first row !! can you explain why?
•  » » » » » 6 years ago, # ^ |   0 When you read n and m you are not actually reading the entire line, you need add a cin >> ws; or getline(cin, st); Right after you read n and m.
•  » » » » » » 6 years ago, # ^ |   0 Damn,small detail costed a WA !! thanks anyway!
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 cin.ignore() would also be a great command to learn.
 » 6 years ago, # | ← Rev. 3 →   0 what is wrong in this solution for Ahttp://www.codeforces.com/contest/707/submission/19984174It failed on test case 5Plzz Anyone tellme the mistake
•  » » 6 years ago, # ^ |   0 Same happened with me!!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 Probably because scanf also reads blank spaces as characters.ex: 2 2 G G G YYour code says that it's #Black&White.
•  » » 6 years ago, # ^ |   0 The invisible '\n' character got you.
•  » » 6 years ago, # ^ |   +1 just a guess change scanf("%c",&a); to scanf(" %c",&a);
•  » » » 6 years ago, # ^ |   0 yes it worked
•  » » 6 years ago, # ^ |   0 You're almost reading the char wrongly.scanf("%c",&a) reads also the spaces you should make it scanf(" %c", &a)
•  » » » 6 years ago, # ^ |   0 U r right,Got it
 » 6 years ago, # | ← Rev. 2 →   0 I got score 0 this competition and I DONT KNOW WHAT IS WRONG WITH EVERY SOLUTIONS I PUT IN THE SYSTEM!!!somebody please help me!!!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 for problem B the max cost equals int(1e9) that is large than the initial value of cost you defined cost=987654321;My solution failed also due to a similar mistake. :(I made the the ans = MOD where MOD is a predefined const variable equals int(1e9) + 7; but sadly I changed it to be int(1e9) before and forgot to edit it again. :'(
•  » » 6 years ago, # ^ |   0 a) '\n' character was read in the first line.b) The dummy value was not set high enough, you set it to 9.87e8 but the edge limit was 1e9.d) Let the time complexity aside, this line -> "q=q-(i-c);" is probably a bad idea.
•  » » » 6 years ago, # ^ |   0 thanks!! but I dont still know how to solve d. Isnt the menu 4 in my code supposed to copy the data from the c index part and also print the sum value based on the data from c. However, it seems to take O(q(n*m+m)). This is definitly TLE.
•  » » » » 6 years ago, # ^ |   0 I just got D completed with O(q).http://codeforces.com/contest/707/submission/20009279Somebody has explained this above, what you have to do is build a dfs tree and perform an euler tour. Visit each command one by one and compute the answer, and whenever you leave a node revert everything you have done.
•  » » 6 years ago, # ^ |   0 in B your problem is this line : cost=987654321. The distances are up to 1e9, so your program gives WA in test 2 1 1 1 2 1000000000 1 which I managed to hack with succesfully :)
•  » » 6 years ago, # ^ |   +3 Man, my condolences. As for the solution for B, I think that you have set too small initial value for the cost = 987654321. The max value, that you can get is 109 and your variable is already less than that.The other problem is that your arrays are of size 20000 = 2·104, but the max number of cities is 105 = 100000.
 » 6 years ago, # |   +3 Can we please have a statistic about how many contestants had '\n' and ' ' slayed in problem A. =P
•  » » 6 years ago, # ^ |   +4 Probably most of these:
 » 6 years ago, # |   0 WA on test 85 for problem C.http://codeforces.com/contest/707/submission/20001952I am the unluckiest person in this contest :/
•  » » 6 years ago, # ^ |   0 at least, you won't make the mistake again (;
•  » » 6 years ago, # ^ |   0 btw , what is the mistake. Did u figure out ??
•  » » » 6 years ago, # ^ |   0 Casting double to long long caused my answer for the case to be lesser by 1
 » 6 years ago, # |   -7 I didn't know that pretests are designed as a trap to pass buggy solution like this and make the coder think that (s)he has nailed it, but only to find after the contest that (s)he could not solve the first problem due to an inside-loop-outside-loop silly mistake. It hurts.
 » 6 years ago, # |   -20 Very bad contest. Very bad pretests. :-(
•  » » 6 years ago, # ^ |   +8 In my opinion that makes this contest great — many opportunities for hacking! Be happy, that there are at least some pretests and not just final system testing.
•  » » 6 years ago, # ^ |   +3 pretests for B and C was weak .. I think...
•  » » 6 years ago, # ^ |   0 It has not happened for first time.I got WA once even when pretest passed. so i now have to be pretty sure of the answer even before submitting it. Admit that you(and still i) have wrong habit to hastily solve and submit.
•  » » » 6 years ago, # ^ |   0 All the same, many solutions tumbled on the system testing, and on a completely different tests, not on any one.
 » 6 years ago, # |   +21 System testing stuck on 100% for a long time. :/
 » 6 years ago, # |   +4 I think the pretests are too bad :( but anyway,thanks for preparing this contest and also thanks for Codeforces' good job.
 » 6 years ago, # |   +6 Yes, C was bad, but B and D are really interesting, imho
 » 6 years ago, # |   +3 Can Anyone explain why this solution works he's taking 2*m*n inputs . why no TLE ?http://codeforces.com/contest/707/submission/19985014
•  » » 6 years ago, # ^ |   0 because m, n <=100. So 2*m*n <= 20000. Usually for 1 second, 10^7 operations will pass.
•  » » » 6 years ago, # ^ |   0 u are not getting the question . actually per test u should take a m*n matrix as input but this guy is taking 2*m*n inputs , he's taking extra inputs.
•  » » 6 years ago, # ^ |   +17 When you reach the end of input cin doesn't do anything.Note that when you run your program on your computer with console I/O, when your program reaches a line like cin >> x, the operating system will pause your program and wait for the user to enter a whole line of input. Only after that the program will resume. You can actually enter the end-of-input character on Windows by pressing Ctrl+Z.When the codes are graded on CodeForces, I/O is redirected to/from files or by means of a pipe (not sure), these methods automatically append the end-of-input signal. You can safely put a line like cin >> x at the end of your program for testing purposes.
•  » » » 6 years ago, # ^ |   0 ok got it thnks.
 » 6 years ago, # |   0 Can someone tell where my code got wrong answer in Problem C?.20003730
•  » » 6 years ago, # ^ |   0 If n==2 -> -1, but you have 3 5
•  » » » 6 years ago, # ^ |   0 oh shit, how come i was thinking 2,3,5 is a Pythagoras triplet. Shit man :(
•  » » » 6 years ago, # ^ |   0 Bad thing is that it passed pretest :/
 » 6 years ago, # |   0 B and D and E without tags!
•  » » 6 years ago, # ^ |   +26 Dabagh's rating in all(three) his contests are 1516 :D his diagram is horizintal :D
•  » » » 6 years ago, # ^ |   0 Thats one of the amazing things i ever seen !
 » 6 years ago, # |   0 http://www.codeforces.com/contest/707/submission/19995711 : This submission in GNU C++11 gives compilation error while same code http://www.codeforces.com/contest/707/submission/19996044 in GNU C++ gives accepted.This happened during today's contest Luckily I shifted to GNU C++. Can someone tell why this weird thing happened?
•  » » 6 years ago, # ^ |   0 Not completely sure, but when using C++11, instead of declaring iterators as iterators, you can declare them as autos, and the compiler will automatically assign them the correct type to your variable. This is less error-prone than declaring individual types
•  » » 6 years ago, # ^ |   +4 It's because name hash of your global variable is already used by std::hash in c++11.
•  » » » 6 years ago, # ^ |   0 Thank you :D
 » 6 years ago, # |   +12 I hope next time who set contest try to avoid problems based on mathematical rule only (like C) ,who set contest should know this is online contest and anyone can ask google or Quore or stackoverflow.
 » 6 years ago, # |   +8 I was a little bit suprised when so many people solved problem C. I didnt google it and I found the divisors of n^2 and then since x^2+y^2=z^2 => x^2 = z^2-y^2 => x^2 = (z-y)*(z+y) where x =n, and for any triangle since the equation |z-y|
•  » » 6 years ago, # ^ |   0 but to check the divisors of any number i know that you should iterate till the square root of the number in this case the sqrt of (n^2) will be O(n). n= 1e9 which will not fit the Time ?
•  » » » 6 years ago, # ^ |   0 oh my bad I check divisors of n because no need to find divisors greater than n since z-y cannot be greater than n
 » 6 years ago, # |   0 tfw, could've solved B, but I forget to use Set instead of List. fml.
 » 6 years ago, # |   0 In problem C, Katya wondered if she can specify the length of some side of right triangle and find any Pythagorean triple corresponding to such length? Note that the side which length is specified can be a cathetus as well as hypotenuse. What does it mean ? As far as I understand, the given length can be any side including hypotenuse. But if I see the tests, I couldn't find any test where the given side is hypotenuse. Am I missing something ?
•  » » 6 years ago, # ^ |   0 The easiest way would be to take the given side as the smallest side and work out the lengths of the other two since input is at most 10^9.
•  » » » 6 years ago, # ^ |   0 That's what I came to know at the end.
•  » » 6 years ago, # ^ |   0 Maybe it was just for tricking people that didn't came up with the equation, whose uses brute force to consider one more case and fall into TLE.
 » 6 years ago, # |   0 In Div. 2 A, my code got WA on test 11, while the same code gives the correct output on my system and also on ideoneideonecodeforcesDoes the input have some extra '\n' characters or spaces? :/
 » 6 years ago, # | ← Rev. 4 →   +1 I suppose DFS is a common solution for D. I have absolutely no clue what idea stands behind that.However, I had another idea which is basically coding persistency described in the problem. In exchange I would love some people with a DFS solution to explain their solution in detail.Let's observe what happens with the bookshelf on each step: you at most change one row (inverting books). Thus, a dumb solution would be for each query keep a node which has pointers to N bitsets of length M. Then, whenever you need to modify a bookshelf, just create an identical node to the one on the current step but change one pointer to a new bitset. Going back to older version simply means taking the node from that step. In total, for each query you create a bitset of length M, a node with N pointers. In terms of complexity, it works fine. In terms of memory, it's a bit consuming though: Q * (sizeof(bitset of size M) + N pointers) = Q * (M / 8 + N * 4) = 412 MB which is close to memory limit.Not to risk, a smarter solution is to create two layers: root node has 25 nodes to nodes with 40 pointers to bitsets (25 * 40 = 1000). Now on each query you add one bitset, one node with 40 pointers, and one with 25 pointers, which is about Q * ((40 + 25) * 4 + M / 8) = 38 MB.Now how do you use DFS to solve the problem? Thanks!UPD: Even the dumb solution passes -_-
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 http://codeforces.com/contest/707/submission/20009279Actually you are pretty close to the solution. Instead of keeping the bitset of the current shelf and keep pointers of the state whenever you are asked to go back for it, we can consider it in another way.State 1 -> State 2 -> ...State 1 -> State X(where query 4 1 was called)And here we can perform an dfs, we perform the modifies needed, and revert the actions of "state 2 ... state X-1" to retrieve the state of the shelf. This means instead of requiring O(n*m*q) from rebuilding the whole shelf, or O(q*q) which reverts everything online, you can see that solving it offline only takes O(q).
•  » » » 6 years ago, # ^ |   +5 Put the intended solution aside, I am really surprised that the bitset has managed to exploit the memory limit. That's a new trick I've learnt today. =D
•  » » 6 years ago, # ^ | ← Rev. 3 →   +19 Problem D can be solved by using an offline approach.We will read all queries before answering any of them and, in the reading itself, we will build a tree. The tree can be built in the following way: If the query i has type 4, then it will ask us to return the shelf state to the one of query k; in the graph, it means k is the father of i. If the query ihas type different from 4, then the father of i is i - 1. Now, we have built a graph which the state of a node only depends on the operations done by its ancestors. With this in mind, we can maintain a global "state", which will be the answer for each query while we traverse the tree. Whenever we get to a node in the traversal, we apply the operation of that node to our global "state"; and whenever we leave that node (i.e., its recursion is ending) we deapply (what would be the correct word here?) the operation of the respective node. This way, we have the correct "state" for every node in the tree, since no node will influence the answer of any node that is not its child.If there is something unclear or some silly mistake, feel free to ask/correct.
•  » » » 6 years ago, # ^ |   0 http://codeforces.com/contest/707/submission/20011849Runtime error on test 27I am very confused and debug for a long time.
•  » » » » 6 years ago, # ^ |   0 Node a[N] is incorrect, there are actually q nodes since we are considering each queries as a node.
•  » » » 6 years ago, # ^ |   0 I used the same algo :)
•  » » » 6 years ago, # ^ |   0 I see, it was fairly simple to code up and is much faster and less space-consuming. Thanks!
•  » » 6 years ago, # ^ |   0 I did the same thing during the contest (though I've now also coded the DFS thing that everyone suggested). In case you want to see it, here it is: http://codeforces.com/contest/707/submission/20002884Before I coded it, I considered the memory usage and also tested it to see that it would work out just fine in theory, but to be honest, I was more concerned that the O(m*q) runtime wouldn't be fast enough. I figured with an efficient c++ implementation it could work though... Anyway, it turns out that when I tried the most problematic case for this approach (essentially all of type 1) it ran on my computer in 0.8 seconds so I figured it was good enough. Also, the DFS approach as far as I understand also takes O(m*q) time so it's not like it's that much better.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Oh I see that you can actually change the DFS approach to work in O(q) time. Well I guess I was unfairly helped by the lax memory and time requirements =P.
 » 6 years ago, # |   +1 How harsh that 4 or 8 wasn't a pretest for C. I wrongly assumed n was always the smaller cathetus and passed the pretests
•  » » 6 years ago, # ^ |   0 the pretest in this contest was so bad this contest was hacking contest not for solving problems
 » 6 years ago, # |   +1 What is the DFS approach to problem D ? I was able to come up with an easy online solution using a persistant segment tree, But cant figure out the DFS one. Someone please brief. Also, AC solution using persistant Segtree: http://codeforces.com/contest/707/submission/19996544
•  » » 6 years ago, # ^ |   0 I don't know about DFS, but simply storing the queries in a vector, and queries of 4th type in another vector and sorting this second vector will also work.But the DFS method seems to be common, I'm curious to know a well explained solution too!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 In the dfs approach you try to keep the history of jumps due to query of type 4. We store all the queries first. Using this list of queries we build the graph with query no.(order in which they appear) as vertices and logical sequence of executing the query as edges, the graph is build by traversing the queries: (a). For queries of type 1, 2, 3 you add an edge for the given query no and given query no - 1.(that's the standard order in which you want the queries to be executed one after another) (b). For queries of type 4 you add an edge for the given query and the query point referred by it(I am assuming the graph to be undirected but not necessary).(We do this so that we can evaluate both branches(one due to the normal order of queries and other due to this 4th type of query) while doing the dfs in future). So after building the graph you start the dfs, now for every vertex you visit you apply the query and while leaving you deapply(not a word I know :P) the query to return to the state where you were before entering the branch of the graph so now you can evaluate those jumps without any problems. You store the book count for the corresponding query after applying it, in an array. Traverse the array and print the values. I hope this is quite clear, andHere's link to my submission:http://codeforces.com/contest/707/submission/20014005
•  » » » 6 years ago, # ^ |   0 Great explanation!! But instead of deapplying, we can check the number of children the node has. If children>1, it means there's a query of type 4 for this node. Just store the value computed this far in the tree for those children. This way, we will always evaluate query 4 first, and we don't have to deapply.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 No, I don't think that is possible. Suppose you have linear graph of say size q/2. add one more node as neighbour to every node, i.e every node has two edges except the leaf nodes. Something like this:root|\|\|\....upto q/2So you will have to save the state(I am assuming the raw and naive state i.e state of every shelf and every book in every shelf) of q/2 nodes say you store it in bitsets, then also you will need q/2*n*m bits = 5*10^10 bits = 6.25*10^9 bytes=6.1*10^5 kb = 5960 mega bytes. Unless you have a better way to store the states, this might not work.
•  » » » » » 6 years ago, # ^ |   0 I think my understanding was wrong, but this is what I see :There is one chain, and each node in the chain can have some leaves, which are the 4th query. The last node in the chain can have some 4-queries, or none. If the last node on the chain has one 4-query, then we process it and return. Therefore, apart from checking no. of children a node has, we also have to check for the case that if there's only one child, whether or not that child is a 4-query(only the last node on the original chain has this). If any of the nodes in the main chain is a 4-query, then we won't be able to check the way I proposed. So, we'll have to first make the main chain(all q queries), then separately add the 4-query nodes to the main chain with a flag that indicates that this is not in the main chain.This is actually very cumbersome, and we could've achieved offline by simply sorting a vector of 4-queries and processing the list of input queries upto each element in the 4-query vector. These are two separate vectors.
 » 6 years ago, # |   +4 For CYou know that the difference between squares is odd and there is a pattern.1 4 9 16 25 363 5 7 9 11Where in every odd number comesHence if n is odd n * n can be found between two consecutive squares.if n is even bring it down to the nearest odd.if n is power of 2 then for 2 it is -1else for 4 you know 3 and 5so you know a triplet for every power of 2 as well.Came up with this solution in an hour. Guess should have googled it :P
 » 6 years ago, # |   0 No editorial :'-(
 » 6 years ago, # |   +10 http://codeforces.com/contest/707/submission/19994995In problem E, I used 2d summation table for each garland. I think its worst time/space complexity is O(n^3), but I got AC...
 » 6 years ago, # |   +5 some one tell me how to derive a formula for C ?
•  » » 6 years ago, # ^ |   +7 Good day to you,the "things" in C are Pythagorean Triples — you can find a nice article here.Hope it helpsHave nice day! :)
•  » » » 6 years ago, # ^ |   0 thank you man
 » 6 years ago, # |   0 http://www.codeforces.com/contest/707/submission/20012886 That case 53 for which it is showing wrong answer is actually correct..I have calculated it with calculator,,Can someone tell me why it is showing Wrong answer?
•  » » 6 years ago, # ^ |   +1 You may have mistaken the answer for what your program output. Your output is definitely not a Pythagorean triplet.
•  » » » 6 years ago, # ^ |   0 sorry for hacking you man, I hope you read the problems completely for now on
•  » » » » 6 years ago, # ^ |   0 I honestly appreciate it. I was able to fix it afterwards. In fact every question I solved this past contest was judged correct but failed system tests or were hacked. I'll definitely be thinking a little harder next time!
•  » » 6 years ago, # ^ |   0 (96466018,96466082,111120) is a Pythagorean triple,not (96466018,96466082,111117):)
•  » » 6 years ago, # ^ |   0 the value of the phythagorean triplet in your output is (96466081.996544324252684266295429) you have to sure that the values are correct before output it
 » 6 years ago, # | ← Rev. 2 →   +3 i think my solution for prob C is quite simplewe only need to consider the case of which n is a cathetuswe need to find a, b such that n^2=a^2-b^2so n^2=(a-b)(a+b)since a-b is a divisor of n^2, and a-b and a+b must have the same parity with n then a simple solution is a-b=1 for odd n and a-b=2 for even n.therefore for odd case we have ( (n^2-1)/2;(n^2+1)/2) , and ( n^2/2-1;n^2/2+1 ) for even case
•  » » 6 years ago, # ^ |   0 for n<=2 there are no solution, but for n>2 there's always a solution so we don't have to consider the case of which n is a hypotenuse
 » 6 years ago, # |   0 How to solve problem D?
 » 6 years ago, # |   0 It's a wonderful contest.But I think C is too easy for who know Pythagorean number.If you make some limit for ans ,it's a good choose for this problem.Thamk you for you problem.
 » 6 years ago, # |   0 The solution updating is not in time :(
 » 6 years ago, # | ← Rev. 2 →   0 Problem D: 20003798 can anyone tell me why I got RE in this submission I just use dfs and get back function.
•  » » 6 years ago, # ^ |   0 There are q Nodes, i.e. 1e5 nodes at max.
•  » » » 6 years ago, # ^ |   0 But I set MAXN=1e5+5 Can you explain more details please?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Oh, my bad... Sorry for the confusion.I just fed it with 1e5 queries of "4 0" and nothing went wrong, I shall see if random generated cases will trigger the RE.UPD: Well... I can't find the case... Hopefully someone else can point it out for you.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I find if type == 4 i will be larger than 1000 but when I solve different types in dfs I use sum[i], flag[i], sh[i][j], i will extend the edge (in type 4) That's why I got REIt's a fool error.
 » 6 years ago, # |   +1 When will the tutorial be released?
 » 6 years ago, # |   +4 7000+ coders participate in this contest. Maybe because the contest time is not that late as usual and begins at 21:00 in UTC+08. (In general, contest starts at 00:30 in UTC+08...) Hope more contests can start earlier.. ;-)
•  » » 6 years ago, # ^ |   0 Surprisingly, this time I have not seen any freeze or delay of web, despite of this number. I think they have hardened the back end.
 » 6 years ago, # |   0 For D it seems a simple simulation would suffice.You can create the adjacency graph.But for simulation of the process divide m into 29 bits of 35 (in worst case) integers and simulate. Operation 3 takes O(35) units of time (simple XOR'ing with all ones) in worst case.Here is a passing solution — http://codeforces.com/contest/707/submission/20019991
 » 6 years ago, # |   0 Has anybody received notification letter before the contest? I might have missed the contest owing to the absence of the announcement.
 » 6 years ago, # |   0 I think the test data for E was weak. How could this solution 20022277 pass system test?