NelsonMondialu's blog

By NelsonMondialu, 4 years ago, ,

Hello everyone,

I'd like to invite you to participate in a 2-hours Div2 round which will be held this Saturday, August 30th at 11:30 AM MSK. Div1 coders can take part out of competition, as usual. The problems were prepared by me and MirceaFF (B and C). I'd like to thank Gerald for helping preparation, MirceaFF for english translation and MikeMirzayanov for the Codeforces system.

The main characters of this round will be Caisa and Gargari,which have some interesting tasks for you. I hope you will enjoy the round. Good luck and have fun!

UPD: It will be used a standard scoring.

Here are the winners:

1.lymmd

3.dans

4.ZLD5

5.nxihkke

Stats about hacks can be found here.

Editorial is here.

•
• +222
•

 » 4 years ago, # |   +96 First time to take part out of competition :)
•  » » 4 years ago, # ^ |   +6 Also for me, I'm not waiting for it as hard as I waited before :)
•  » » » 4 years ago, # ^ |   +26 Congratulations ! Maybe you can become a nice couple (●′ω●)
•  » » » » 4 years ago, # ^ |   +20 too late man I already got Engaged :P
•  » » » » 4 years ago, # ^ |   +8 Well that escalated quickly :P
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 ignore.
•  » » 4 years ago, # ^ |   -9 But you can solve problems ,but your ratings will not change :)
•  » » 4 years ago, # ^ |   0 Second time!
 » 4 years ago, # |   0 I think this is the first round made by someone from Vaslui (my hometown, too) :D My round is coming soon :P
 » 4 years ago, # |   0 The day is just to sign up for a new term, and it's afternoon in China! we happen to have much time for it ^_^ !
•  » » 4 years ago, # ^ |   -11 Yes. I just think I saw it by mistake.
•  » » 4 years ago, # ^ |   -8 I'm from China too.It's a good contest time:)
 » 4 years ago, # |   +1 Very unusual contest time! :DI think there will be a high decrease of the number of registrants! Good Luck.
•  » » 4 years ago, # ^ |   +3 That is because in the same day there will be topcoder SRM + Hackerrank 101 hack august
•  » » » 4 years ago, # ^ |   +1 Oh! I didn't know these! Do the times have interference too?
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +4 Fortunately not, you can see them here
•  » » » » » 4 years ago, # ^ |   0 Thx very much, it help me much.
•  » » 4 years ago, # ^ |   0 It will surely increase there are a great number of chinese coder will join:)
•  » » 4 years ago, # ^ |   0 4077 registrants... :) In round 263 there were 3988 registrants...
 » 4 years ago, # |   0 Please add time conversions :)
•  » » 4 years ago, # ^ |   0 You can check time conversion from contests -> current contest and click on the time given :).
•  » » » 4 years ago, # ^ |   0 Oh, cool
•  » » 4 years ago, # ^ |   +9 According to this comment, you are not a programming contest addict... :PYou know you are a programming contest addict when : You have become the master of converting timezones to your country's standard time.
•  » » » 4 years ago, # ^ |   0 Hahaha, I became used to clicking the links in announcement post to check.
•  » » » 4 years ago, # ^ |   +20 That is an implication. But is it an equivalence?
 » 4 years ago, # |   -9 Very nice. I will do my best to do this round and get >1700 rating.
•  » » 4 years ago, # ^ |   0 Best of luck! I hope I take part in this contest(I don't like the time of this contest) . If I do, I wish I atleast become blue again.
•  » » » 4 years ago, # ^ |   +6 I wish you good luck. :D
•  » » 4 years ago, # ^ |   0 According to my own experience, I think that you will stay in expert for a few rounds before getting to div1
 » 4 years ago, # |   0 finally a chance to participate in a good time :D
•  » » 4 years ago, # ^ |   0 Not a good time for US though: 12:30 AM to 3:30 AM depending on the time zone...
 » 4 years ago, # |   +3 Converted Time Washington DC, District of Columbia, U.S... 3:30 AM EDT http://fc02.deviantart.net/fs71/f/2013/281/0/0/sleep_is_overrated__by_austin_comix_inc-d6ps3kj.gif
•  » » 4 years ago, # ^ |   -6 narcis_vs tnks for this contest :)
 » 4 years ago, # |   +1 There wasn't any hurry for posting the blog :D
 » 4 years ago, # | ← Rev. 2 →   -6 alert("dsjgds");
•  » » 4 years ago, # ^ |   +1 what does it mean? :)
•  » » » 4 years ago, # ^ |   +3 XSS
 » 4 years ago, # |   +11 May be i will Miss this contest Due to My Exam
•  » » 4 years ago, # ^ |   +3 My exams ended 3 hrs before contest. Yay!
 » 4 years ago, # |   0 is there any contest for beginner problem solving to start practice with ?? HELP
•  » » 4 years ago, # ^ |   +5 Take any previous contest in virtual mode, for beginners DIV 2 is the place. Why not try the last contest itself : Click here Simply register and familiarize yourself with how a codeforces round actually is.
 » 4 years ago, # |   0 very excited about contest. First time to unofficially participate!!! Hoping to solve ABCD for first time :)
•  » » 4 years ago, # ^ |   +24 Since solving AB doesn't really give you anything and there's no rating to lose, you should start from D or E. These div2 contests are a true golden mine for trying out risky new approaches :D
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Good advice :). I'll probably start from C, try D+E, then go to ABAlso, do you read all of the problem statements before starting to work on any problems?
 » 4 years ago, # |   0 I want have a good grades in this contest,bless all!
•  » » 4 years ago, # ^ |   -11 thanks(!):D
 » 4 years ago, # |   +4 I hope the problems have something to do with elegant graphs/dp/trees/combinatorics problems and not some greedy approach with a lot of conditions and corner cases!
 » 4 years ago, # |   0 Hope the problems will be interesting. Let's enjoy it. :)
 » 4 years ago, # | ← Rev. 2 →   0 this is my first contest
•  » » 4 years ago, # ^ |   +6 New genius one?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +2 no, i'm not genius
 » 4 years ago, # |   0 Waiting for a nice problemset!!
 » 4 years ago, # |   +1 good time for contest :) <3
 » 4 years ago, # | ← Rev. 2 →   0 What was the solution of problem D?I starting taking the LCS of the first and seccond line. And then LCS the result with the third line and ... (LCS calculation was DP — But I called it recursively for the new check).I got segmentation fault. Does anyone know the reason? Is my algorithm correct?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 My idea was same too, but this technique wouldn't pass the sample I/O. I mean if there is several subsequence with same length , which one would you consider ? For examplebetween 1 4 2 3 4 1 2 3 you have 1 2 3 and 4 2 3 , which one would you choose for 1 4 2 3 , here it is obviously 1 2 3 eventually you have to try all the sequences. I think there are some other technique.
•  » » » 4 years ago, # ^ |   0 I think they should have accepted all of the possible answers.
•  » » 4 years ago, # ^ |   -12 You must use suffix automat.(Sorry for mistakes ) :D
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 This problem is as like as SPOJ: X-MEN Difference is in the problem of spoj, we have to find out LCS between only one pair. But In D of this round, we have to find out LCS between each pair. And it is possible, as maximum value of k can be 5.*** The problem of SPOJ(given above) can be converted into LIS... Then I solved it in nlog(n).
•  » » 4 years ago, # ^ |   +10 Your algorithm is not correct, because there could be more than one LCS.The solution is quite simple — for every you make a vector Vx = {a1, ... ak}, where ai means position of x in i-th permutation. Now you create a directed graph — iff . Now an observation — if u1, u2, ..., um is a common subsequence, then u1, ... , um is a path in our graph. So now your problem is to find the longest path in a graph. But this is a DAG, so it is easy — you can either make a topological sort, or just brute it in O(n2).
•  » » » 4 years ago, # ^ |   0 Can you explain the graph creating part a bit please , I mean this part .
•  » » » » 4 years ago, # ^ |   +1 Sure. Let's look at positions of numbers 1 and 2 in our permutations. {x1, ..., xk} are positions of 1 (i.e. in i-th permuation number 1 is on xi -th position) and {y1, ... , yk} are positions of 2. Now we create a graph with vertices labeled with 1,2,...,n.When x1 < y1, x2 < y2, ... xk < yk, then we create a directed edge from vertex 2 to vertex 1. In other words, we create such an edge when in each permutation 2 comes after 1.
•  » » » » » 4 years ago, # ^ |   0 it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(
•  » » » » » 4 years ago, # ^ |   0 Thank you , a little question though , if the array was not a permutation , i.e there was repeated numbers , could we have solved the problem using similar approach ? I mean can the normal lcs problem be solved like this?
•  » » » » » 4 years ago, # ^ |   0 Thanks for nice explanation :)
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(
•  » » 4 years ago, # ^ |   +3 That will have problems in case of multiple LCSs. Eg, consider (1,2,3,4,5), (1,2,3,5,4) and (4,1,2,3,5). First two have two LCS : (1,2,3,4) and (1,2,3,5). If you took only one, and that was (1,2,3,4), then you will get final answer 3, whereas the final answer is 4.
•  » » 4 years ago, # ^ |   0 The trick here is that input is a permutation (no repeats). Hope this gives a hint to those who still want to think about D.
•  » » 4 years ago, # ^ |   0 i donot think u need all of that there is a very important observation which is for every sequence the numbers are found only once so u can save the index of every digit for every sequence and try to start with any of them but u will need to know the last digit taken so that the sequence in valid then u check if all the numbers are in valid position (after the last number) u add this digit in all the sequences to the solution so the state will be (last digit taken) and u will have a loop on the all the digits except the last one trying to choose any valid digit sorry if it seems a little bit messy or alot
 » 4 years ago, # |   0 Pretest 2 for problem E seems so strange...... So many people get WA or RE on this......
 » 4 years ago, # |   +4 Div.2 B — find max?
•  » » 4 years ago, # ^ |   +3 yup
 » 4 years ago, # |   0 What is the explanation of B seriously -_- . I first thought that it may be the maximum number . But I couldn't prove it. But at the last of the just before 3 min contest I see B was solved more than A , So , I just submitted by calculating the maximum number. I don't know if it is true though.
•  » » 4 years ago, # ^ |   0 It seems to be obvious that in each step the current energy is equal to h[0] — h[current_step], so you just need to increase h[0] (from 0 to max(h[]))
•  » » 4 years ago, # ^ |   +1 Instead of increasing height of some pylons you can just increase on all your money height of the first pylon, answer would be the same because increasing height of the first pylon just increases your starting energy. So you calculate minimum energy on the way and then add this energy (or 0) as a height to the first pylon.
 » 4 years ago, # |   +1 Problem C?
•  » » 4 years ago, # ^ |   +1 make dp matrix for 4 diagonal you will need 4 dp arrays for that one to add dollars from up-left and from bottom-left , up-right , bottom-right. then make another dp matrix to collect all of them dp[i][j]=dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3*mat[i][j] --> mat[i][j] is original value we subtract 3 of them because we add the same cell 4 times and we need just once. one observation is that the one bishop will be on white cell and another will be on black one (like a chess board) because problem statement says that "there is no cell that is attacked by both of them" if you tried to put both on white cells you will see there is a cell attacked by two , try it so just loop on all i,j in dp and take maximum in black cells and maximum in white one and result is the sum. feel free to ask
 » 4 years ago, # |   0 When 1 hours remaining, then my father call me and come to eat pizza..:
 » 4 years ago, # | ← Rev. 3 →   0 Nice contest Narcis and Mircea! I'm a little bit surprised that there are more pretest passed submissions on B than on A (because B was trickier in my opinion). A was very good for Div2. About C I would like to say that it's nice. I liked D the most, because it's really beautiful despite its very simple input. Initially I thought that E is some kind of HLD with segment tree, so didn't try it for long. Got the right idea in the last 20 minutes (some kind of sorting + DFS). Not the most prolific round for hacking though. Anyway, keep up the good work.P.S.: Caisa is a really nice name for a task hero. Don't you think? (image) I'm curios what does Gargari comes from.
 » 4 years ago, # |   +6 I missed a hack attempt in problem C. At 01:56 (4 minutes remaining), I saw a solution with overflow problem. I then wrote a code to generate worst case of 2000x2000 with all entries 10^9. Submitted at 01:59:57 ... It itself TLEd!... Then it striked that a 2x2 matrix would have been sufficient. LOL !! =(
 » 4 years ago, # |   +7 What a contest! I hacked for the first time!
•  » » 4 years ago, # ^ |   +17 What a contest! I was hacked for the first time! :/
 » 4 years ago, # |   0 Does anyone know how to solve C?I precomputed the sums for each position where a bishop could be placed in O(n^2), but I don't know how to find the pair of bishops without checking each possible pair.
•  » » 4 years ago, # ^ |   +1 Find the best bishop for (i+j)%2=0 and the best bishop for (i+j)%2=1, then add them. Like the board for chess.
•  » » » 4 years ago, # ^ |   0 Why is this necessary? What if two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other ?
•  » » » » 4 years ago, # ^ |   0 Give me example, please) (When two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other)
•  » » » » » 4 years ago, # ^ |   +5 Oh sorry, Just realized that is not possible as as soon as you select a bishop , if you draw a line on the board along the square's diagonals , you have divided the board into two halves. Now if you place a bishop in another equivalent square (modulo 2) you have to cross this line which will have an intersection and that square will be attacked by both the bishops.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I have to disagree with you here. Two Bishops attacking each other will have to be in the same diagonal. There is a difference between "two bishops attacking each other" and "two bishops attacking the same cell". The problem statement failed to differentiate between these two. Read this wolfram article. Cell (2,2) and (0,2) will both attack cell (1,3) but they are not directly attacking each other.
•  » » 4 years ago, # ^ |   0 colors of bishops should be different
•  » » 4 years ago, # ^ |   0 You don't need to check each and every combination of pairs. It is stated in the problem statement that "No position should be attacked by both the bishops", this made the problem simpler.Now you need to check the max for bishop on black positions and max for bishop on white position and add those. Thats it :)
•  » » 4 years ago, # ^ |   0 If you look carefully then you will see the board is bipartite.A white bishop cannot attack a black one. So find the max black diagonal and max white diagonal. answer is the summation.
•  » » 4 years ago, # ^ |   0 Oh, I missed that part. Thanks!
•  » » 4 years ago, # ^ |   0 Well , I think you know what a white cell and black cell in chess is. Now see , if you place a bishop in a black cell than you can't put the other in black too. because then they would attack atleast one common cell . try drawing it in paper. So , the problem is no bishop lines intersect each other. so you calculate for each one seperately like this //first bishop for(int i=1;i<=n;++i) int j; if(i%1) j=1 // for second bishop , j=2 else j=2 // for second bishop, j=1 for(;j<=n;j+=2) // calculate sum from fourcorners if(sum>bishop1Max) //change max value and position 
 » 4 years ago, # |   0 why so many people get wrong answer on pretest 5 in DIV 2 A problem ?
•  » » 4 years ago, # ^ |   -14 I didn't)
•  » » » 4 years ago, # ^ |   0 Well done!!!
•  » » 4 years ago, # ^ |   +1 they thought they can buy more than one pocket with sugar
•  » » 4 years ago, # ^ |   0 This is tricky test case. 1 9 9 0 Output:0 not -1
•  » » 4 years ago, # ^ |   +1 i got wrong answer because i do not see anywhere written that you cannot buy more that one unit of same sugar. I still do not see that, can someone please point out where it is mentioned in the problem A Div 2.
 » 4 years ago, # |   0 Hi, I am a newbie for Codeforces. I found that I was unable to view the results of pretest of my submissions. Everytime I clicked the number linking to the submissions which failed on pretest, the popup was just displaying my source code but no pretest results. And in the direct link of the submission was also just displaying the source. Any can help? Thanks in advance.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 this is only possible during practice. In contest You have to figure out by yourself :)
•  » » 4 years ago, # ^ |   0 You can't see your output.. You have to figure it out yourself
•  » » 4 years ago, # ^ |   0 That is the intended behavior during a codeforces round. You do not get to see the pretest that caused your program to fail.
•  » » 4 years ago, # ^ |   0 You can not see pretests during the round. You must find a wrong test and mistake in your solution yourself.
•  » » 4 years ago, # ^ |   0 You cannot see pretests during the contest ;)
 » 4 years ago, # |   0 Does anyone know the second test case of C?
 » 4 years ago, # |   0 This is very good contest that I participate first time but I could not solve any problems :D
 » 4 years ago, # |   0 in problem C change ll mx1=0,mx2=0; to ll mx1=-1,mx2=-1; Accepted :( :(
•  » » 4 years ago, # ^ |   +3 Or use <= instead of < when comparing. I had the same bug unfortunately ^^
•  » » 4 years ago, # ^ |   +3 Same :D
•  » » 4 years ago, # ^ |   +6 Same things happen with me SmartCoder ; At least this contest was unofficial for me :P
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I got TLE for using cin/cout :/
•  » » » 4 years ago, # ^ |   0 I got both the problem :p pity for me -_-
 » 4 years ago, # |   0 Too fast systest!!When I saw my ranking it was at 30% testing. In a few (~30) seconds, after I again checked the dashboard, it was 100%. I was expecting it to be around 40 — 60 at that time.this is unbelievably fast!
 » 4 years ago, # |   0 Please, could you tell how to count the sum that gives the black bishop using dynamic programming
•  » » 4 years ago, # ^ |   +9 The better solution is to use array sum[2][N*2]. sum[0] — sums of LT-RB diagonals, sum[1] — sum of LB-RT diagonals. To calculate such array you need only two formulas: sum[0][i+n-j-1] += a[i][j] sum[1][i+j] += a[i][j] Then the answer for (i,j) is sum[0][i+n-j-1] + sum[1][i+j] - a[i][j]. That's all.
•  » » 4 years ago, # ^ |   0 Just like Prefix sum
 » 4 years ago, # | ← Rev. 3 →   0 cin/cout gets TLE for problem C and scanf/printf AC ? Seriously ? Nice...
•  » » 4 years ago, # ^ |   0 Me too!I want explanation!
•  » » » 4 years ago, # ^ |   +3 cin is like a turtle. Very slow turtle.
•  » » » 4 years ago, # ^ |   0 I agree !! I knew this happens on some OJs, but it never happened to me on CodeForces. Maybe the authors are inexperienced and missed that, maybe they should reeval.
•  » » 4 years ago, # ^ |   +4 Use ios::sync_with_stdio(0); In case cin/cout is too slow, this line speeds them up
 » 4 years ago, # |   +9 Did anyone else too misread problem C as placing bishops such that they do not attack each other, rather than placing bishops such that they do not attack any common cell. I wasted an hour on this before realizing I had misread the problem.
•  » » 4 years ago, # ^ |   +1 I wasted half an hour because i thought that they were rocks and i don't know how :D then i wasted another half thinking that they mustn't attack each other :Dstrange contest time leads to weird results :D
•  » » 4 years ago, # ^ |   0 Exactly I even coded that to realise at 1:42 the insane thing i did.
•  » » 4 years ago, # ^ |   0 I calculated that max cost is 4n-4, only to realize that weights of the cells were input based. (i assumed 1!)
•  » » 4 years ago, # ^ |   0 Same here. The problem becomes much harder with this "new" statement.
 » 4 years ago, # |   0 Please publish a complete editorial and update ratings fast :)Thanks
 » 4 years ago, # |   0 in problem B wouldn't it be sufficient to find the maximum pylon and print it out ?
•  » » 4 years ago, # ^ |   0 Yes it would be. Printing the maximum of the numbers would do.
 » 4 years ago, # | ← Rev. 3 →   +7 For Prob A, if the input is 1 6 2 80 then, he can either buy just one for 2$80cents, and get 20 candies in return or, he can buy 2 worth 5$ 60cents, and get 40 candies in return. So, the answer should be 40 candies, and not 20.I interpreted the problem in the above mentioned way. It was mentioned that he can purchase only one type of sugar, but it was not mentioned that he can purchase only one quantity of that type. I ended up wasting over an hour over this ambiguity.Am I correct?
•  » » 4 years ago, # ^ |   0 Same with me,I think for 1 10 0 70, answer should be 90 (because 3 times of same type can be taken) but for all the AC solutions, the answer gives 30...WTH?!?!?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I made the same mistake and cost me 2 WAs. however, maybe the problem setter wrote this line there are n types of sugar in the supermarket, maybe he able to buy one. to inform us that he can buy only one pocket of sugar.I think the problem statement should've been clearer .
•  » » 4 years ago, # ^ |   0 Same here. The problem statement was not clear. I did the same and ultimately was not able to solve this. I do think due to ambiguity of problem A . More people solved problem B.
•  » » 4 years ago, # ^ |   0 Same with me! He can buy several kilos of sugar and get more candies for some cases. Problem has incorrect description I think.
 » 4 years ago, # |   +11 Weak test cases for problem E. Even brutes are accepted.TLE by cin and AC using scanf.very upset by the contest.
•  » » 4 years ago, # ^ |   0 Maybe test cases for problem E were generated randomly.
 » 4 years ago, # |   0 :( Just changed cin to scanf on problem C an got AC, it's ok to get TLE because of reading method or the most important part is the algorithm and it complexity ??
•  » » 4 years ago, # ^ |   +3 Si eu la fel :))
•  » » » 4 years ago, # ^ |   0 problem B is very very easy :D
 » 4 years ago, # |   0 As a Chinese I do not think there's no difference between "type" and "number".
 » 4 years ago, # |   0 Problem C got TLE just because of cin\cout.Without it I can become candidate master.Such a bad contest
•  » » 4 years ago, # ^ |   +2 Me too
•  » » 4 years ago, # ^ |   0 Same
 » 4 years ago, # |   0 Why this solution is wrong? I used DP over bitmaks of set of sequences and looked for the longest common subsequence.
 » 4 years ago, # |   +1 can anyone tell me why i am getting TLE in problem C my complexity is O(n*n) solution code LINK.
•  » » 4 years ago, # ^ |   0 Maybe because cin is very slow
•  » » 4 years ago, # ^ |   +1 You use cin. It's too slow. I made the same mistake
 » 4 years ago, # |   +4 Nice Round!
•  » » 4 years ago, # ^ |   0 it isn't surprising
 » 4 years ago, # | ← Rev. 5 →   +15 Stop ZLD! Why you create so many accounts for div.2!
 » 4 years ago, # | ← Rev. 2 →   +2 Difference is only a cin function :( too much pathetic :'(
•  » » 4 years ago, # ^ |   0 Same here
•  » » » 4 years ago, # ^ |   0 Usually this n't happen in CF :( TLE for cin instead of scanf :(
•  » » » 4 years ago, # ^ |   0 Same here
 » 4 years ago, # |   0 nice round! +169 expert again! hoho!
•  » » 4 years ago, # ^ |   0 congrats IvanJobs :)
 » 4 years ago, # |   0 Where is tutorial?!!
•  » » 4 years ago, # ^ |   0 you can play clash of clans . IT's best.
 » 4 years ago, # | ← Rev. 2 →   +2 Country Wise Standings has been updated.
 » 4 years ago, # | ← Rev. 2 →   +6 The E's system test may be too weak.If the tree is a long link with all nodes is 2 with the deepest node is 3. And I query the last node every time. There seems many AC solutions cannot pass this case.The data maker by python: n = 100000 print n, n for i in range(n - 1): print 2, print 3 for i in range(n - 1): print i + 1, i + 2 for i in range(n): print 1, n Maybe I am wrong. Please reply to point it out.
 » 4 years ago, # |   +8 Stats about hacks can be found here.
 » 4 years ago, # |   0 how can i solve C in O(n^2)? the number of black and white cells can be up to (n^2)/2so.. for white_x for white_y for black_x for black_yi thought O(n^4) but it seems wrong.. sorry for dumb question and bad english
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Compute the value for each rightwards diagonal and leftwards diagonal . Now iterate through the whole 2D array , Find the value for that particular cell as (leftDiagVal(cell) + rightDiagVal(cell) — X[cell] ) and greedily update the answer for Odd(i+j) and Even(i+j) . //X[cell] is the value input in that cell Answer = Answer_Odd + Answer_Even
•  » » » 4 years ago, # ^ |   0 Just got AC, Thanks
•  » » » 4 years ago, # ^ |   0 How about the following algorithm for C -- (I have not implemented or submitted it because I am way too sleepy and I just can't think, but I would be glad if someone validated this)1) Pre-compute the sum of all diagonals. 2) For every diagonal, there will be exactly at most 2 diagonals where you cannot place another bishop. Except for these (potentially 2 diagonals) calculate the diagonal which will give you the maximum sum by iterating through all the favourable diagonals.3) After doing this, simply iterate through all diagonals, and find sum(diagonal) + sum(max_diagonal_calculated_in_(2))`. Output the maximum sum found here.This is O(n^2). Will this work?
 » 4 years ago, # |   +9 The data of Problem E is too weak 7644499 The time complexity of his algorithm is O(q*height) Why can he accept?
•  » » 4 years ago, # ^ |   +11 I found it so... Test is too weak.
 » 4 years ago, # |   +1 In problem A Div 2, i got wrong answer because i do not see anywhere written that you cannot buy more that one unit of same sugar. I still do not see that, can someone please point out where it is mentioned in the problem A Div 2.
•  » » 4 years ago, # ^ |   0 "maybe he able to buy one" in the second paragraph?I am not really sure either.
 » 4 years ago, # | ← Rev. 2 →   0 I really appreciated with fast turtorial bcz some problem seems hard for me to understand. After understanding the div2(ABCD) problems, I wrote the why and how here.wrote in chinese. Hope useful for the guys like me^_^
 » 12 months ago, # |   0 In the Div2. C question, I get a TLE when I use cin to scan numbers which is understandable. But when I use fast io for cin, cout; precisely this :ios_base::sync_with_stdio(false);cin.tie(NULL); I get a WA on test1, which runs correctly on my shell though. However, using scanf my answer gets accepted. I have always ignored such fumble. Can anybody please explain me how I can use cin, cout in this case and still not get a tle?TIA.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +1 Here you can find information about sync_with_stdio function. The reason, why you are getting WA is you unsync your streams, so if you are using scanf and cin in one program (as you're using in yours), then you will get undefined result.To use cin/cout with sync_with_stdio, you should not use scanf/printf. In this case it will work properly.