Всем привет!
20 августа в 16:05 MSK состоится рейтинговый раунд Codeforces #368 для участников из второго дивизиона.
Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.
Я постарался сделать задачки, в которых нужно больше думать, чем кодить. Надеюсь, каждый найдет себе задачку по вкусу.
Спасибо координаторам danilka.pro и GlebsHP за помощь в подготовке контеста, vovuh за прорешивание, Roms за вычитывание условий, а также MikeMirzayanov за платформы Codeforces и Polygon.
Удачи!
UPD1: 500-1000-1500-2000-2500
UPD2: Поздравляем победителей!
Div. 2:
Div. 1:
UPD3: Разбор
It seems interesting:)
I am good at half-zhang. So take my bus quickly.yo ka wa ka ti ki yo ku la wu!
竜がこの水物なトピ主を喰らう!
no one will understand what "half-zhang" is unless he is a Chinese...
There's a slight typo in the post. It should be round 368 instead of 365.
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.
And the points will be 500-1000-1500-2000-2500 as usual. I guess B-)
It will be tough and tricky I guess. Long break and again regular round, Thanks codeforces. Wish you all have a great jump..:)
I think it was because of IOI, codeforces doesn't want IOIers to miss the rounds.
vovuh for testing....I think problems will be on Pokemon Go! and we'll have to try to catch Pinsir, seems bit interesting.
If you are doing your best,you will not have to worry about failure.
傻逼真多
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.
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...
6500+ registrants already, I'm getting feeling of long queue again !!
The server has handled even more participants before, so don't worry, just concentrate.
Могу поспорить, что задача C будет по геометрии)
Давай на 100 рублей =)
Кто-то мог остаться без соточки :)
Будь мужиком, кидай деньги сюда: 4377 7314 2790 2959.
Контест, конечно, завалил, но хотя бы денег заработаю...
Ты в танке?? Задача C была по геометрии.
_**PERFECT TIMINGS FOR ROUND #368 :D **_
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 are
To 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 days
Maybe 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 regrets
To 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 embrace
To 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 reborn
The 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 not
I 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 sunrise
To 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 embrace
To 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.
I think you've got the wrong post...
but your words are really nice
:)
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.
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
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:
Must be an interesting contest, 7000+ participants.
Good luck for ya all.
Where is scoring distribution?
7k+ participants. I hope the queue wait time for a submission is low.
coders are increase day by day.
I really like round. Thanks for nice contest :)
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.
If n <=2 ans = -1
if 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)
Interesting. Thanks for the help!
I didn't realize odd can be handled so easily!! I factorized and all that.
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 ?
No, no, no. It's much more simple. They just google it.
Here is justification for that behavior Click.
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
There are some interesting methods for this problem. Thanks for the help!
a = n^2 — m^2, b = 2*n*m, c = n^2 + m^2
m < n
Assume that the side is one of a,b,c
and 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) < n
For validating the other two values, you can use binary search to find the sqrt of
n^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))
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.
I used binary search and used the traditional 3SUM interview question to solve it in nlogn
where n is the number of perfect squares less than 10^9
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
:)
First contest for me here! I struggled to see where I was going wrong in B — I'll read the editorial ASAP.
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
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.
It is O(Sum of Garland_size + 2000*k)*log(NM)=2000*2000*log(2000)
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)
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.
Without the 2D-Segment tree, We have to do the Loop which
It is O(Sum of Garland_size * 2000).
Because of part 2 has an bad complexity, we have to use 2D-segment tree.
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. =D
UPD: Nvm, fixed it. =P
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
So many people solved C... Was it really that easy or you just write the bruteforce out of despair like me?
It's solution is googleable.
Ok. So, at least, I didn't cheat =)
Using prewritten codes or resources that are published before contest is not considered as cheating.
Why do you want to make me upset?
Why do you want to make me upset?)
If the solution is googleable it just means the problem is unoriginal, nothing more.
yeah! the problem setter should be upset LOL :P
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
Every pythagorean triple (a, b, c) can be written as:
a = m^2 — n^2
b = 2mn
c = m^2 + n^2
for 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.
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.
Is the intended complexity for E O(ASK_Q * K * log^2(N)) or there is a better solution?
Can you please explain your approach? I couldn't come up with anything other than sqrt decomposition. :\
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.
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..
Does anyone can't visit codeforces during the contest? I can't visit codeforces for about 20mins from 0:15 after contest,and then during 1:00 I can't visit codeforces too.I'm sure that my Internet connection is okay.
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.me/contest/707/hacks/249193/test
GOD DANG IT I WROTE "cout<<n<<m;" instead of "cout<<n<<' '<<m<<' '<<q<<endl;"
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 * 2mn
c = k * (m^2 + n^2)
The editorial should be published shortly...
Not yet published :(
How to solve D? I encountered persistent data structure for the first time in my life...
Offline
Yeah, offline. I have built tree of requests and walked over it using DFS
Iam keeping a counter that counts changes, and therefore, I know the answer instantly after each update.
Huh, I did the same but recursively, which TLE-d. I guess function overhead was too much.
Never mind, yours is recursive too.
Oh, the way you handled the third case is pretty neat — I didn't do that.
I also interested in idea of solution of D.
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 5
1 1 1
3 1
4 0
4 1
3 1
Then:
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.
Hi. What does
adj[i]represent for? What value it stores? Thank you. ;-)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.
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 :P
UPD: System test case 15 got me, surprisingly by wrong answer not by TLE...
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
I like your approach. I solved it directly with a persistent data structure :P
I represented the state as
vector<vector<bool>*>, 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
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"
20000000 th submission I can't belive , 20000000!!!
It should have been AC!
Surprised so many people solved C..
We have access to google, and we ran the search "Pythagorean triplets".
Sadly, I'll fail systests thanks to n=2
What a sad story. I would have ended in the same spot if there wasn't a sample for n=1.
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.
I didn't consider n=2, luckily someone hacked me and I found the bug.
Is there anyone who kept on getting WA for pretest 4 in D ? Here is my code 20003997
Oh, you have the same solution with mine. Take a look on it, my code have passed pretests
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..
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.
I need more 3 minutes ,so that I can solved problem D. It's a sad story.
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.
How exactly would djikstra help here . Wouldn't fit in the time limit i guess .
Just insert into set all k storages with distance 0, then run Dijkstra.
Overkill
What is the more efficient solution then?
Answer is one edge.
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
Well mine version passed the system test. Guess the time limit wasn't that tight.
http://codeforces.me/contest/707/submission/19986208
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.
I am not sure that Dijkstra will pass
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 :)
I can't find it, any links? thanks!
http://www.friesian.com/pythag.htm
@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*n
now, a*a +n*n = c*c => n*n = (c-a)*(c+a) = p*q
Now assume min(p,q) = c-a and max(p,q) = c+a. Now just check if equation is satisfied. My code
What 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.
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
can O(m*q) solution pass D?
You can keep a counter that keeps track of change of number of books, so you won't have to iterate over the shelves.
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...
was my first contest. solved only A and B . :(
Can anyone tell me how to hack?
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.
"being turned on, brings Alesha some pleasure," ...
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
Instead of treating each query one at a time first store all the queries. Then create a tree where for node
pthe parent node is eitherp-1if the query is 1, 2, 3 andk[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.
could you elaborate your algorithm a bit please .I know dfs .Thanks for replying
For reference, 20018322
For example take the test case,
In which we can form the tree,
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 withO(q)queries."being turned on, brings Alesha some pleasure, " ...
A completely wrong program (http://codeforces.me/contest/707/submission/20000102) caused by a misunderstand of the problem (div2D) pass pretest... So weak pretest !!(crying,/(ㄒoㄒ)/)
pls tell an approach to solve D
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
This is not a segment tree, just tree, I guess
You must use some data structure to do changes and qureies. My focus is not on SegmentTree. You must have misunderstood what I meant.
a classic problem is not OK for contests! I'm talking about problem C.
anyway it was a new experience, I'll google your problems in your next contest
It is actually a good problem for educational rounds.
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.
I got AC without Googleing. Running time was O(n) though, not O(1).
Could you explain your approach?
brute force
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?
https://www.quora.com/Trigonometry-mathematics-How-can-I-get-a-Pythagorean-triple-from-a-given-hypotenuse-if-it-exists
The first answer gives a pretty nice solution it may be possible to solve it faster tho.
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...
Totaly Right.
and because of this , my rating will suffer today , and those who google each and every question for copy pasting answers will enjoy :(
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.
Well , I am pretty sure that those 2000 people didn't derive the equations
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.
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.
What factoring?
Very Bad Pretests in A & C.
I guessed it from the "pretest passed" response. it was so quick. :D
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.
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 ...
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.
can any one tell me why this failed the test 19984978?
never mind found the mistake
The unseen '\n' is the deadliest.
what is the mistake? I am same as you and i got WA in 5
http://codeforces.me/contest/707/submission/19984724
mine are different my code shows black&white even if there is a coloured pixar but it should show colorful
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.
c is the worst problem ever you can google it and get the mathematical law
Yet you failed at that google-able worst problem ever.
i tried to solve it without cheating
Cheating or no cheating, it's still not the worst problem ever. Though I might agree if you said unoriginal.
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
This contest was for hackers, not for coders
Darn I failed B because I set infinity as 10^9, not 10^9 + 1 :(
i set it to 10^9+1 but now i got TLE on test41
why dont problem setters just use hard and extreme test cases for the contest
Because we all need hope.
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
why my "19990351" is WA?
include
include
include
include
include
include
include
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; }
http://codeforces.me/contest/707/submission/19990351
You read the '\n' characters so something like this: (分行符號也被讀進去了, just a translation in Chinese don't judge me CF)
1 2 B M
would cause problems as the read input would be '\nB'.
Can someone tell me where is the mistake? http://codeforces.me/contest/707/submission/19983693
You have 2 nested loops both using the integer i.
that's not the mistake because i is redefined in inner loop so outside i is unaffected.
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.
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?
When you read n and m you are not actually reading the entire line, you need add a
Right after you read n and m.
Damn,small detail costed a WA !! thanks anyway!
cin.ignore() would also be a great command to learn.
what is wrong in this solution for A
http://www.codeforces.com/contest/707/submission/19984174
It failed on test case 5
Plzz Anyone tellme the mistake
Same happened with me!!
Probably because scanf also reads blank spaces as characters.
ex: 2 2 G G G Y
Your code says that it's #Black&White.
The invisible '\n' character got you.
just a guess
change
scanf("%c",&a);toscanf(" %c",&a);You're almost reading the char wrongly.
scanf("%c",&a) reads also the spaces you should make it scanf(" %c", &a)
I got score 0 this competition and I DONT KNOW WHAT IS WRONG WITH EVERY SOLUTIONS I PUT IN THE SYSTEM!!!
a -> http://codeforces.me/contest/707/submission/19984724
b -> http://codeforces.me/contest/707/submission/19995846
d -> http://codeforces.me/contest/707/submission/20003567
somebody please help me!!!
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. :'(
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.
a-> http://codeforces.me/contest/707/submission/20007401
b-> http://codeforces.me/contest/707/submission/20007552
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.
I just got D completed with O(q).
http://codeforces.me/contest/707/submission/20009279
Somebody 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.
in B your problem is this line :
cost=987654321. The distances are up to 1e9, so your program gives WA in testwhich I managed to hack with succesfully :)
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.
Can we please have a statistic about how many contestants had '\n' and ' ' slayed in problem A. =P
Probably most of these:
WA on test 85 for problem C.
http://codeforces.me/contest/707/submission/20001952
I am the unluckiest person in this contest :/
at least, you won't make the mistake again (;
Very bad contest. Very bad pretests. :-(
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.
pretests for B and C was weak .. I think...
System testing stuck on 100% for a long time. :/
I think the pretests are too bad :( but anyway,thanks for preparing this contest and also thanks for Codeforces' good job.
Yes, C was bad, but B and D are really interesting, imho
Can Anyone explain why this solution works he's taking 2*m*n inputs . why no TLE ?
http://codeforces.me/contest/707/submission/19985014
because m, n <=100. So 2*m*n <= 20000. Usually for 1 second, 10^7 operations will pass.
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.
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 >> xat the end of your program for testing purposes.ok got it thnks.
B and D and E without tags!
Dabagh's rating in all(three) his contests are 1516 :D his diagram is horizintal :D
Thats one of the amazing things i ever seen !
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?
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
It's because name hash of your global variable is already used by std::hash in c++11.
Thank you :D
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.
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|<x<z+y should hold, I iterated the divisors of n^2 starting from the smallest one and till n since (z-y) must be smaller than x(also n). and then I found z-y and z+y and checked whether it is valid or not.
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 ?
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
In problem C,
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 ?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.
That's what I came to know at the end.
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.
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 ideone
ideone
codeforces
Does the input have some extra '\n' characters or spaces? :/
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 -_-
http://codeforces.me/contest/707/submission/20009279
Actually 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).
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
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
ihas type 4, then it will ask us to return the shelf state to the one of queryk; in the graph, it meanskis the father ofi.If the query
ihas type different from 4, then the father ofiisi - 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.
http://codeforces.me/contest/707/submission/20011849
Runtime error on test 27
I am very confused and debug for a long time.
Node a[N] is incorrect, there are actually q nodes since we are considering each queries as a node.
I used the same algo :)
I see, it was fairly simple to code up and is much faster and less space-consuming. Thanks!
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.me/contest/707/submission/20002884
Before 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.
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.
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
the pretest in this contest was so bad
this contest was hacking contest not for solving problems
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.me/contest/707/submission/19996544
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!
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:
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, and
Here's link to my submission:
http://codeforces.me/contest/707/submission/20014005
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.
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/2
So 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.
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.
For C
You know that the difference between squares is odd and there is a pattern.
1 4 9 16 25 36
3 5 7 9 11
Where in every odd number comes
Hence 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 -1
else for 4 you know 3 and 5
so 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
http://codeforces.me/contest/707/submission/19994995
In 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...
some one tell me how to derive a formula for C ?
Good day to you,
the "things" in C are Pythagorean Triples — you can find a nice article here.
Hope it helps
Have nice day! :)
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?
You may have mistaken the answer for what your program output. Your output is definitely not a Pythagorean triplet.
sorry for hacking you man, I hope you read the problems completely for now on
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!
(96466018,96466082,111120) is a Pythagorean triple,not (96466018,96466082,111117):)
the value of the phythagorean triplet in your output is (96466081.996544324252684266295429) you have to sure that the values are correct before output it
i think my solution for prob C is quite simple
we only need to consider the case of which n is a cathetus
we need to find a, b such that n^2=a^2-b^2
so 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
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
How to solve problem D?
Problem D: 20003798 can anyone tell me why I got RE in this submission I just use dfs and get back function.
There are q Nodes, i.e. 1e5 nodes at max.
But I set MAXN=1e5+5 Can you explain more details please?
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.
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 RE
It's a fool error.
When will the tutorial be released?
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.. ;-)
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.
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.me/contest/707/submission/20019991
Has anybody received notification letter before the contest? I might have missed the contest owing to the absence of the announcement.
I think the test data for E was weak. How could this solution 20022277 pass system test?
hahahhahahaha