### mesanu's blog

By mesanu, 3 months ago,

Hello Codeforces!

flamestorm, MikeMirzayanov and I want to invite you to Codeforces Round #817 (Div. 4).

It starts on Aug/30/2022 17:50 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behaviour. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to the testers: sandry24, SlavicG, tibinyte, Gheal, down, haochenkang, TimDee.

We suggest reading all of the problems and hope you will find them interesting!

Good Luck!

UPD 1: The contest is delayed by 15 minutes.

UPD 2: The opinions of testers about the order of problems are very contradictory. Please do not rely heavily on the order of problems in the round and read all the problems. Good luck!

UPD 3: Editorial is out!

• +172

 » 3 months ago, # |   +15 As a tester, I highly recommend everyone to participate <3
•  » » 3 months ago, # ^ |   -11 As a contestant, I highly recommend you not to test. bad pretest :(
•  » » » » 3 months ago, # ^ |   +2 You forgot to write base case my man!
•  » » » » 3 months ago, # ^ |   0 How tf did you do this
 » 3 months ago, # |   0 Div4！Long time no see!
 » 3 months ago, # | ← Rev. 3 →   -106 Why did you put a Div.4 contest on Tuesday? It would be better if it was on let's say, Sunday because Div.4 contests always have a ton of participants. This way a lot of people won't be able to participate because of their obligations.And virtual participation is just not the same as live participation because you can see how many people solved each problem till the end of the contest, solutions etc.I am not writing this because I am mad because I won't be able to participate in the contest (in fact, I will be able to participate) but because a lot of people won't participate because the contest is on Tuesday.MikeMirzayanov or whoever decides the day of the contest
•  » » 3 months ago, # ^ | ← Rev. 2 →   +15 This is the same as saying "Why is there a div 2 on Thursday?". However, I haven't seen any contest being downvoted just for the day on which it will take place and also a div 4 round may be really good for low rated people to boost their CP confidence through educational problems.
 » 3 months ago, # |   -11 Good luck for everyone. I hope the contest will be interesting.
 » 3 months ago, # | ← Rev. 2 →   +9 Strange. Why all of the commments are downvoted???
•  » » 3 months ago, # ^ |   -57 The comment is hidden because of too negative feedback, click here to view it
•  » » » 3 months ago, # ^ |   -16 look at my icon
•  » » » 3 months ago, # ^ |   -24 You almost got me, unfortunately my wifi sucks so the video didn't load
•  » » » 3 months ago, # ^ |   +1 Ha! YouTube ads saved me from that clever trick! Thx youtube!
 » 3 months ago, # |   -25 Good luck for everyone<3
 » 3 months ago, # | ← Rev. 4 →   -29 Expecting some intresting problems
 » 3 months ago, # |   0 As a tester, I don't like sausages.
•  » » 3 months ago, # ^ |   -53 As a tester, I disrespectfully disagree with your opinion. Sausages could have increased round quality so much.
•  » » 3 months ago, # ^ |   -22 As a participant (out-of-competition), why?
 » 3 months ago, # |   -30 Why Top G wasn't mentioned in the blog? I thought he tested the round
•  » » 3 months ago, # ^ |   +6 they hate a user with the name andrewtate for no reason just because of the name. god these people
 » 3 months ago, # | ← Rev. 4 →   -42 .
 » 3 months ago, # |   -34 First unrated CF round for me!
 » 3 months ago, # |   -16 Hello everyone dear friends! I'm sure you can all solve these tomorrow's tasks. Such tasks Div.4 are easy for you. Let's try this time too. I wish you good luck and the best success.
 » 3 months ago, # | ← Rev. 2 →   -17 Registered in the contest but in the Registered participants list, my handle "THKHAN" showed as unregister. What should I do?
 » 3 months ago, # |   -11 Div 4 arrives... Every Specialist be like: First unrated contest for me!
 » 3 months ago, # |   -22 My first unrated contest
•  » » 3 months ago, # ^ |   -13 hehe
 » 3 months ago, # |   -12 :(
 » 3 months ago, # |   -13 Sounds like special
 » 3 months ago, # |   -11
 » 3 months ago, # |   -13 As SpoilerThe Timura tester, mesanu should add me in this blogpost.
•  » » 3 months ago, # ^ |   0 when will ratings change
•  » » » 3 months ago, # ^ |   0 When I will decide.Now I don't want.TimDee
 » 3 months ago, # |   -7 I Pray that I reach specialist again
 » 3 months ago, # |   -6 Best of luck...
 » 3 months ago, # |   0 As a participant, i wish positive delta upon you all. (I want to be 1400 ;))
•  » » 3 months ago, # ^ |   -6 Me too
 » 3 months ago, # |   0 Very exited <3
 » 3 months ago, # |   -15 Why did you put a Div.4 contest on Tuesday? It would be better if it was on let's say, Sunday because Div.4 contests always have a ton of participants. This way a lot of people won't be able to participate because of their obligations.And virtual participation is just not the same as live participation because you can see how many people solved each problem till the end of the contest, solutions etc.I am not writing this because I am mad because I won't be able to participate in the contest (in fact, I will be able to participate) but because a lot of people won't participate because the contest is on Tuesday.MikeMirzayanov or whoever decides the day of the contest
 » 3 months ago, # | ← Rev. 2 →   +8 What's wrong with the people who are downvoting every single comment? Is everyone supposed to not like these rounds just because you don't? This community is weird
 » 3 months ago, # |   -6 Particularly liked the part about urging people not to register new accounts solely for narcissistic purposes =)
 » 3 months ago, # |   +7
 » 3 months ago, # |   0 Come on down voters, I'm here
•  » » 3 months ago, # ^ |   0 gave you one
 » 3 months ago, # |   +43
 » 3 months ago, # |   +10 Damnn! 5000+ unrated accounts are participating in this contest, isn't a huge number? what do you say?
•  » » 3 months ago, # ^ |   +3 how did you count?
•  » » » 3 months ago, # ^ |   0
•  » » » » 3 months ago, # ^ |   -8 You have solved many problems and consistently look like you would have been an expert till now.
•  » » » » 3 months ago, # ^ |   0 how did you sort them?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 The standing will probably look pretty weird Edit: Forgot about the trusted thing. Sorry..
•  » » » 3 months ago, # ^ |   0 Only trusted participants are shown in standings.
 » 3 months ago, # | ← Rev. 2 →   +12 Is the starting time changed?
•  » » 3 months ago, # ^ |   0 Yes
•  » » 3 months ago, # ^ |   0 Yes~10 minutes
•  » » 3 months ago, # ^ |   0 Yes, it will be held sharp in 10 minutes. Some random people may be downvoted me. Sorry!
 » 3 months ago, # |   +2 Any reason for delay of 15 minutes?
•  » » 3 months ago, # ^ |   0 This delay is a complete waste of time coz can't do anything good in this delayed time
•  » » » 3 months ago, # ^ | ← Rev. 3 →   -15 You can downvote my comment meanwhile
•  » » » » 3 months ago, # ^ |   0 Now most people don't waste their time and started downvote your comment ^^
•  » » 3 months ago, # ^ |   0 The connection was unstable here so
 » 3 months ago, # |   +3 Why contest postponed?
•  » » 3 months ago, # ^ |   0 It's not but delayed
•  » » 3 months ago, # ^ |   0
 » 3 months ago, # |   0 Hope at least today I won't see the grid.
•  » » 3 months ago, # ^ |   0 Just look at problem F...
 » 3 months ago, # |   0 contest delayed
 » 3 months ago, # |   0 "The contest has started" announcement still appeared lol.
 » 3 months ago, # |   +26 My first coding competition ever! Kinda excited
 » 3 months ago, # |   0 Why is the round delayed?
 » 3 months ago, # |   0 Hope time will not change further
 » 3 months ago, # |   0 I pray that every grey becomes green after this contest. Happy Coding!
 » 3 months ago, # |   +71 As a tester (I really tested it tonight!) I updated the post with the following text: The opinions of testers about the order of problems are very contradictory. Please do not rely heavily on the order of problems in the round and read all the problems. Good luck!
 » 3 months ago, # |   +6 Thank you for this contest!Favourite problem is E it is simple to understand, but it isn't easy.Nice Contest!
 » 3 months ago, # |   -34 Wtf problem F sick implementation?!Stop proposing this kind of problems!
•  » » 3 months ago, # ^ |   +33 it's not at all a bad problem for Div4. If you find there are lots of if-else, maybe you need to look for better observations.
•  » » » 3 months ago, # ^ |   0 casual codeforces, someone points out an obvious issue with the problemset and people call him the idiot who can't solve the problem. are you okay?
 » 3 months ago, # |   0 don't really know why but my submission kept on getting WA on test 2. I think my logic is on point but guess i misread or did something wrong midway. Any testcases that disprove my solution? ofc after the contest
•  » » 3 months ago, # ^ |   0 I initially got stuck at the same thing. It's that when your di or dj is negative you aren't doing anything. Where instead you should keep moving forward until you get a positive di. Same goes for dj. Here's my solution: https://codeforces.com/contest/1722/submission/170256652
 » 3 months ago, # |   0 how to solve E?
•  » » 3 months ago, # ^ |   0 TimeLimit is 6 secs. I maintained prefix sum of width for each height.
•  » » 3 months ago, # ^ |   +1 I don't want to spoil the whole solution ... so I'll give hints since height and width of rectangles are under 1000,hint: use a matrix such that matrix[l][r] = Area of all rectangles with height <= l && width <= r.Basically a prefix sum matrix.
 » 3 months ago, # |   +12 Contest was fun and tasks were great. Thank you for this Div4!
 » 3 months ago, # | ← Rev. 2 →   0 how to do E
•  » » 3 months ago, # ^ |   0 i also get stucked in Problem D
•  » » 3 months ago, # ^ |   0 I did like this. For each height we maintain prefix sum for width. I am not sure if I get TLE.
 » 3 months ago, # |   +18 if anyone is interested, I recorded myself doing all problems
•  » » 3 months ago, # ^ |   -7 if u had explained the problems then it would have been great video
 » 3 months ago, # |   0 if only for E it was hs<=hi<=hsb and ws<=wi<=wb, it would have been so much easier, well anyway can someone give me a hint, i stored areas of all rectangles , sorted them , stored prefix sum array, then searched idx_left=upper_bound(hs*ws) and idx_right=lower_bound(hb*wb)-1 on sorted areas, then got the sum with the perfix sum array, can i tweak this to fit the hs
•  » » 3 months ago, # ^ |   +4 I just did hs--, hb++
•  » » » 3 months ago, # ^ |   0 wow im a dumass, thanks for this btw
 » 3 months ago, # |   0 Why this code got runtime error at test 8? https://codeforces.com/contest/1722/submission/170265006
•  » » 3 months ago, # ^ |   0 Probably because of overflow
•  » » » 3 months ago, # ^ |   0 I am using (#define int long long) !
•  » » » » 3 months ago, # ^ |   0 For the same h there maybe more than 1000 w's. resulting in out of bounds o pre[i][j] at line 47.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 for each h, can be more than 1000 widthRuntime Error: This line is not true (line 26)vector pre(1001, vector(1001));Solution: You can resize each i in for loop of prefix sum for(int i=1;i<=1000;i++) { pre[i].resize(v[i].size()); for(int j=0;j
•  » » » 3 months ago, # ^ |   0 I got it, thanks
 » 3 months ago, # |   0 I found F easier than E. The time limit of 6 seconds on E allowed my O(q*1000*logn) solution to pass.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 can u please share your approach for E?i used binary search four time for solving each query. my code link:https://codeforces.com/contest/1722/submission/170286434
•  » » » 3 months ago, # ^ |   -11 that is not true, because when you search for a range assume the height you got a range from L to R satisfying the condition hs < hi < hb inside this range, you can't search for another range for width because it is not sorted (monotonic function) so binary search fails here. Think about the constraint of h and wCode: 170265292
•  » » 3 months ago, # ^ |   0 Yea F was actually easy, I'm suprised so less people solved/attempted it
•  » » 3 months ago, # ^ |   0 Btw, $O(q n)$ solution passes too.
•  » » » 3 months ago, # ^ |   0 wtf
•  » » » 3 months ago, # ^ |   0 no?
•  » » 3 months ago, # ^ |   0 Seems like you got hacked!
•  » » » 3 months ago, # ^ |   0 Reason being the constant factors involved due to excessive map usage.I did same except that I used 2D arrays 170284462 passing in less than 2s
 » 3 months ago, # |   0 Hello, Recently I have been practicing 1200 rating question. And the thing I came across is that all rounds under 700 ,The question with 1200 rating are easier as compared to rounds above 700. Is it the case or its just in my head?
•  » » 3 months ago, # ^ |   0 Older problems are easier.
 » 3 months ago, # |   0 What is the point of $\mathrm{TL} = 6 \,\mathrm{s}$ in the problem E? To make stupid brute-force solution pass?
•  » » 3 months ago, # ^ |   0 But it didn't pass ig
•  » » 3 months ago, # ^ |   +1 not every language is as fast as C++
•  » » » 3 months ago, # ^ |   0 C++ binary search inside binary search got TLEhttps://codeforces.com/contest/1722/submission/170275268
 » 3 months ago, # |   0 Nice contest!Couldn't solve D :-(Forgot to use long longs, otherwise would be correct...Realised only after the clock ended ahah
 » 3 months ago, # | ← Rev. 2 →   0 I was so close to solving 1722G - Even-Odd XOR (or I at least think so)! Can anybody please explain to me how to solve it?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Here's my solution: Observation 1: If the xorOdd == xorEven, then xorOdd ^ xorEven == 0, which mean xor of all elements is equal to 0.This leads to observation 2: If n%4==0 then the answer is 0 to n-1. Consequentially, answer for n%4==3 is 1 to n.if n%4==2 then we take the answer for n-3, then we add 3 numbers of our choice (mine was 2^30, 2^29 and 2^30 + 2^29).if n%4==1 then we take answer for n-6, then we add 6 numbers.AC code: 170284159
•  » » 3 months ago, # ^ | ← Rev. 2 →   +2 I did it by adding incrementing numbers (from 0) until the array was length n-3. Then add 1 << 29 and 1 << 30. The final value is then the xor of the entire array (proven to be unique as it has both 1<<30 and 1<<29)
•  » » 3 months ago, # ^ |   0 You can check my code if you want
•  » » 3 months ago, # ^ |   -10 if a == b, then a ^ b == 0 so you just need to make array xor = 0 you can make ai = i and an = a0^a1...^an now the only problem is that an can be equal to other value if n is odd you can set 30th bit to 1 in all numbers except an if n is even you can set 30th bit to 1 in an and some other ai (if an==a0 choose a1, else a0 for example)
•  » » 3 months ago, # ^ |   0 Consider adding pairs of numbers which in binary are like $(x)0$ and $(x)1$, where $(x)$ are any other bits. Note that the xor will always be equal ignoring the least significant bit. When $n \equiv 0 \mod 4$, every $4$ numbers we will have the xor of the least significant bit be $0$ $(0 \oplus 0$ and $1 \oplus 1)$, so we see that the xors are indeed equal.We now only need to reduce other cases to this one. You don't even have to think about it because the sample test cases already give you answers for $n = 3, 5, 6$, so you put those numbers first and now you add the remaining numbers, starting from, say, $20, 21, 22, 23...$.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 If $n \% 4 == 0$, I gave the even indices values from $1$ to $n/2$ and the odd indices the same value except by adding a fixed high power of 2. The XORs on this high bit position cancel to 0 since there are an even number of odd indices (since $n$ is a multiple of 4).For $n \% 4 == 1$, I did the same for the first $n - 1$ elements, then added an extra 0.For $n \% 4 == 3$, I did the same for the first $n - 3$ elements, then added three values in which two of them XOR to the third by utilizing two high powers of 2 ($10 \oplus 01 = 11$, except these are at some high bit positions)For $n \% 4 == 2$, I did the same for the first $n - 6$ elements, then added six values on high bit positions that get canceled out. This took considerably time, but I eventually came up with $1000 \oplus 0100 \oplus 0010 = 1001 \oplus 0110 \oplus 0001$ (these are four bits at some really high bit positions). I'm quite curious to see if there is a more elegant solution for this case.170258132
•  » » 3 months ago, # ^ |   0 We can easily make the XOR equal in a group of 4 numbers (i, i + 1, 2^k — 1 — i, 2^k — 1 — i — 1).For example, k = 4: 1 (0001) ^ 14 (1110) = 2 (0010) ^ 13 (1101) = 15 (1111). We match the numbers so that the XOR result has k bits set. Let's pick k so that 2^k > 200000.What if the number of elements are not divisible by 4? Then we just need to add some numbers at the beginning of the sequence n mod 4 == 1: begin with 0 because x ^ 0 = x n mod 4 == 3: begin with 1 2 3 because 1 ^ 3 = 2 How about n mod 4 == 2? Since XOR of the rest elements are equal, then these two numbers should be equal too, which means they are not distinct. So starting with 2 numbers is not possible. But we can start with a sequence of 6 numbers. In the contest I found a sequence which is 1 2 4 6 8 9 using brute force.Finally, subtract n by the numbers we have added to the sequence, we should have n divisible by 4 to generate the group of 4s. The initial value i should be at least 10 to be distinct with the starting numbers.Code: 170265768
•  » » 3 months ago, # ^ |   0 Thank you guys.
•  » » 3 months ago, # ^ |   0 You can just set the first n-1 values arbitrary, then the n_th value is the xor sum of the first n-1 values. It's almost impossible to hack.
 » 3 months ago, # |   0 I think that I did a code hard to problem D :P, great contest, now to hack to newbies.
 » 3 months ago, # |   0 when codeforces post its contest editorial ?
•  » » 3 months ago, # ^ |   0 After hacking phase is completed.
 » 3 months ago, # |   0 Can anyone explain the error in my submission?170267520
•  » » 3 months ago, # ^ |   0 look like stackoverflow
•  » » » 3 months ago, # ^ |   0 Can you explain further??
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 You are using char array but you are not resetting them after every test case. So if test cases are like this — 2 10 abcdetIMUR 5 Timur Your code will output No for 2nd test case because strchr(str,"I") will return non null value
 » 3 months ago, # |   0 Can someone hack my solution for problem G. I think my answer might generate duplicate numbers. Link
•  » » 3 months ago, # ^ |   0 It won't generate duplicate numbers. Observe that all the numbers except the number you inserted, at last, are <= 2^30. The last number you inserted xor ^ temp, will actually be > 2^30, so it won't be duplicated
 » 3 months ago, # | ← Rev. 2 →   0 For the problem D i thought of using prefix sum. I was not able to implement it. What you guys did for problem D?
•  » » 3 months ago, # ^ |   0 Just maintain count for each word and then iterate over the given words again to calculate points for each player Code: 170196340
•  » » 3 months ago, # ^ |   0 you can use an array of maps 170197935
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 What made you think to use prefix sum? Anyway, I did it by just storing who wrote which word and then checked how many people wrote it. This can be simply done by using map (I used set aswell, it just made things easier for me)Edit: I just realised each person wrote only distinct word xD (but my solution also works for duplicates) , so there is no need for set actually, just store each occurrence170203831
•  » » 3 months ago, # ^ |   0 I used a map that stores a string and an integer for how many times it's repeated, then I looped over the arrays for each of the three people, incrementing a variable based on the integer stored in the strings map. I hope that helps
 » 3 months ago, # |   0 I think D can be done with dp. Here is my solution: Every next answer is sum of previous answer and max points we can get by changing side of looking of some person. So ans[0] is score that we have in start. Max points we can add is actually biggest difference between points we can get from one person by its current looking and other side looking. So we can just make difference and sort it. Here is code for my submission: https://codeforces.com/contest/1722/submission/170308742
•  » » 3 months ago, # ^ |   0 What is ans[1]?
•  » » » 3 months ago, # ^ |   0 ans[1] will be max score we can by only one change of looking side(it can be called dp[1]).Voli
•  » » » » 3 months ago, # ^ |   0 najace
 » 3 months ago, # | ← Rev. 2 →   0 can someone please explain how to do E?hints please?
•  » » 3 months ago, # ^ |   0 Can you make use of h<=1000 and w<=1000 ?
•  » » » 3 months ago, # ^ |   0 the only thing that comes in my mind is brute force,i read about about people applying prefix sum but i dont have idea about prefix sum in 2d.
•  » » » » 3 months ago, # ^ |   0 You can make such that for every h calculate prefix for all possible w
•  » » » » » 3 months ago, # ^ |   0 thanks alot,learnt something new today.
•  » » » » » » 3 months ago, # ^ |   0 You're welcome
 » 3 months ago, # | ← Rev. 2 →   0 Why did my code gave WA test 2 on E?https://codeforces.com/contest/1722/submission/170276269Edit i saw it =(
 » 3 months ago, # | ← Rev. 2 →   0 Can someone hack my solution of G? I randomly fill an array with N-2 numbers and then just add two numbers to make XOR's equal. If I fail (i.e. needed number already in the array), I randomly fill the array again.https://codeforces.com/contest/1722/submission/170260049
 » 3 months ago, # |   0 Seriously, Today's round was better than previous div.4s... Pset was balanced I think...
 » 3 months ago, # | ← Rev. 2 →   -8 .....
•  » » 3 months ago, # ^ |   +1 Hi, no offence, but how did you solve problem G in just 3 minutes?I guess it was not that much easy. Even the highest-rated coders took 5-6 minutes as well.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I wish it happened but it took 21 minutes check carefully bro......btw are you detective?
 » 3 months ago, # | ← Rev. 2 →   -11 Can anyone Explain Problem D? I used two pointer and greedy approach but don't know why is it failing for some test cases?Here is my code Code: #include using namespace std; #define ll long long #define loop(i,a,b) for(ll i=a;i #define pqs priority_queue > #define w(x) ll x; cin>>x; while(x--) #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++) #define mii map #define umii unordered_map #define mll map #define umll unordered_map #define pii pair #define pl pair #define vi vector #define vl vector #define si set #define sl set #define vpii vector #define vpl vector #define vvi vector #define vvl vector #define fastinout ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL); #define MOD 1000000007 ll binExpIter(ll a,ll b,ll mod){long long ans=1;while(b>0){if(b&1){ans=(ans*a)%mod;}a=(a*a)%mod;b>>=1;}return ans;} ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);} ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N)) vector sieve(int n) {int*arr = new int[n + 1](); vector vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;} //************************************// int main(){ w(t){ ll n; cin>>n; string s; cin>>s; int x=0; int y=n-1; for(int i=1;i<=n;i++){ int c=0; int ans=0; while(x<=y){ if(s[x]=='L'){ s[x]='R'; c++; } if(c==i){ break; } if(s[y]=='R'){ s[y]='L'; c++; } if(c==i){ break; } x++; y--; } for(int k=0;k
•  » » 3 months ago, # ^ |   0 u can see my dp solution on this comment : https://codeforces.com/blog/entry/106422#comment-948238
•  » » » 3 months ago, # ^ |   0 It can be solved without dp as well
•  » » » » 3 months ago, # ^ |   0 u can see that my implementation is easier than greedy approach.
•  » » » 3 months ago, # ^ |   0 Actually, I didn't learn dpCan you implement without dp
•  » » » » 3 months ago, # ^ |   0 yeah
•  » » 3 months ago, # ^ |   0 I suppose you are missing that when you increase k by one, only one person's direction in the line could be changed. But your solution when you are going from k to k+1 can change an arbitrary number of person's directions from 0 to k+1. I would also recommend you to not calculate the value each time you change the line. Instead, you could calculate inital state of the value and then increase it by difference between the old countribution of person in the value and a new one. That will change your asymptotics from O(n^2) to O(n).
 » 3 months ago, # |   +6 Today is Hacking day
 » 3 months ago, # |   +4 Is there problems with hacking process, no one unable to hack this user for the same problem and it still in queue state?
 » 3 months ago, # |   0 Too weak pretest for A. :(
 » 3 months ago, # |   0 Can D done with prefix sum?
•  » » 3 months ago, # ^ |   0 Different people said they solved it like that
 » 3 months ago, # |   0 Why do you use many comments in your code sailikpandey?? MikeMirzayanov Please look into these submissions of him during contests, Is writing huge amount of comments in code and make it unreadable ok? He cheated not only in this contest, Also in many other contests :
 » 3 months ago, # |   0 Why my raiting is less than 1400 but it isn't rated for me ?
•  » » 3 months ago, # ^ |   0 tough luck bro
•  » » » 3 months ago, # ^ |   0 Do you know where you can give feedback to Codeforces?
•  » » » » 3 months ago, # ^ |   0 i was joking, your rating will get updated by end of day
•  » » » » » 3 months ago, # ^ |   0 Are you sure?
•  » » » » » » 3 months ago, # ^ |   0 yes, even my ratings have not been updated.
•  » » » » » » » 3 months ago, # ^ |   0 thank
 » 3 months ago, # |   0 Where is the ranking update?-_-
 » 3 months ago, # |   0 Hello everyone my solution for 1 problem is accepted during contest but now it's shows its hack and solution is wrong?? What is mean I didn't get. Can you please tell how I got my solution correct.
•  » » 3 months ago, # ^ |   0 Consider this case : Timurcc`
•  » » 3 months ago, # ^ |   0 It means a few things: 1. The round has open hacking, which continues (as far as I know) for 12 hours after the end of the contest; 2. Every participant(as far as I know) is able to hack anyone's solution. If you find a testcase that might make others' solutions fail, you can submit the testcase and hack their solution; 3. Someone saw your solution, found a testcase for it and hacked it successfully.After the hacking phase, all of the submissions will be re-judged with updated testcases, which will include testcases of successful hacks(as far as I know).
•  » » 3 months ago, # ^ |   0 Most of the solution of problem A got hacked..these solutions were like this ..they counted frequency of T,r,m,i,u characters and sum them up...if sum==5 they printed yes else no ..They completely neglected that fact that there can be others characters as well ..For example TimruP .. theirs codes will print yes because total Frequency of T,i,m,r,u is 5 but what about P? ...here the codes fails
 » 3 months ago, # |   0 After a long time, finally Div.4
 » 3 months ago, # |   0 Very quality full Problem.
 » 3 months ago, # |   0 Mize orz!!
 » 3 months ago, # |   0 My favourite problem is G. It's fantastic problem
 » 3 months ago, # |   0 Can we have rating change quickly please
•  » » 3 months ago, # ^ |   0 Everyone’s wAiting
 » 3 months ago, # |   0 i'm looking forward to rating changes.
 » 3 months ago, # |   0 When will rating calculated?? Till now nothing change in my rating
 » 3 months ago, # |   0 Why this round is unrated for me?
•  » » 3 months ago, # ^ |   0 Ratings are not updated yet
 » 3 months ago, # |   0 is it unrated?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 yes they announced in the end, I'm kidding it's not.
•  » » » 3 months ago, # ^ |   0 ok
•  » » » 3 months ago, # ^ |   0 nice joke brother
•  » » » 3 months ago, # ^ |   0 What a nice joke bro !
•  » » » 3 months ago, # ^ |   0 My stomach jump when I read the first part.
 » 3 months ago, # |   0 Why i am not rated for this contest???
 » 3 months ago, # |   0 why rating had not yet change?
 » 3 months ago, # | ← Rev. 2 →   -8 Attention! Your solution 170296922 for the problem 1722G significantly coincides with solutions Gaurav__Arora/170273818, om_arsa_2312/170279944, nihal_gupta/170293955, AhmedEl-Gohary/170296922. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.So my evidence that I didn't cheat or communicate with any one in the round is that i used a pre-written blog on geeks for geeks about finding an array of size n whose xor value is some k and I adjusted that function to solve yesterday's DIV4 G, you can take a look at my submission and compare for yourself.https://www.geeksforgeeks.org/find-n-distinct-numbers-whose-bitwise-xor-is-equal-to-k/
•  » » 3 months ago, # ^ |   +3 Sorry, I reverted the punishment.
 » 3 months ago, # |   -8 I have got a system message that my solution coincides with some other participant's solution for the question G, and as asked I am presenting here the common source published before the competition.https://www.geeksforgeeks.org/find-n-distinct-numbers-whose-bitwise-xor-is-equal-to-k/As I had seen this post earlier on geeks for geeks, I simply used it.Please consider my participation for this contest.
•  » » 3 months ago, # ^ |   -8 Same case with me! I also used the code from this website as I had seen it earlier. Please resolve this issue!
•  » » 3 months ago, # ^ |   +3 Sorry, I reverted the punishment.
 » 3 months ago, # |   -8 I have picked a portion of my code from an article of gfg: (https://www.geeksforgeeks.org/find-n-distinct-numbers-whose-bitwise-xor-is-equal-to-k/) You can verify the same. Please look into this and consider my participation. MikeMirzayanov
•  » » 3 months ago, # ^ |   0 Sorry, I reverted the punishment.
•  » » » 3 months ago, # ^ |   0 I got my rating. Thank you.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +1 Congrats on the rank, but I got a little confused.Your previous rating was 1289, mine — 1283; I placed 333, you placed 394; And you ended up receiving more points than me. How does that work MikeMirzayanov?
 » 3 months ago, # |   0 This round is not rated for me. I do not know why this is the case. Can anyone help me understand why this round is unrated for me?
•  » » 3 months ago, # ^ |   0 Actually it's rated for all below 1400 but one reason i think is most of the participant have copied some code for the solution for G from GFG and since those who copied the code from that blog are same. The cheat detecting system consider them to be violating the rule as cheating since code are same. My assumption from reading previous comments.
•  » » » 3 months ago, # ^ |   0 Hey, Thanks for the reply. I did not even attempt G. I only solved the first 4 and got a TLE on the 5th question.
 » 3 months ago, # |   0 Hi my code for a problem 'D' in this contest matches with a user(rajveer_09), not with the intention of cheating, the other user and i was practising a question before hand of this contest which includes the same algorithm which is used in D problem, i thought we had done same code that we have practised, that's why our code matches, all my submission for this contest had been skipped, please help to resolve this issue.
 » 3 months ago, # | ← Rev. 2 →   0 I got my rating tnx
 » 3 months ago, # |   0 my email says — "Your solution 170209476 for the problem 1722C significantly coincides with solutions vayush070/170209476, vayush070/170210073. Such a coincidence is a clear rules violation."what does this mean. I can't understand. Does it says my solution got plagiarized by my own submission.Pls help!!
•  » » 3 months ago, # ^ |   0 pls look into this matter
 » 3 months ago, # |   0 Why ratings are still not updated?
•  » » 3 months ago, # ^ |   0 They are usually updated around 10 PM (IST)
 » 3 months ago, # |   0 Was this round declared unrated?I checked quite a few profiles from the comments and this round is marked as unrated for every single of those I checked. Any updates?
 » 3 months ago, # |   0 Why this contest is unrated for me?
 » 3 months ago, # |   0 plz dont cheat. plz dont make an excuse.
 » 3 months ago, # |   0 Waiting for the rating... :-D
 » 3 months ago, # | ← Rev. 2 →   -19 I have got a system message that my solution coincides with some other participant's solution for the question G, and as asked I am presenting here the common source published before the competition.https://www.geeksforgeeks.org/program-binary-decimal-conversion/ Also used previosuly posted gfg function of binary to decimal conversion. As I had seen this post earlier on geeks for geeks, I simply used it.Please consider my participation for this contest. Thank You
•  » » 3 months ago, # ^ |   +4 I don't see in your submissions 170280792 and 170278642 any code/ideas from https://www.geeksforgeeks.org/find-n-distinct-numbers-whose-bitwise-xor-is-equal-to-k/ Can you point out where I'm wrong?
•  » » » 3 months ago, # ^ |   -19 I have been coincided wrongly just for using decimal to binary conversion function.Please make the contest rated for me.
•  » » » » 3 months ago, # ^ |   0 No offence, I might be wrong,But even 90% of your comment is copy-paste of another comment..
•  » » » » » 3 months ago, # ^ |   0 The topic of concern is different here.
•  » » » » » » 3 months ago, # ^ |   0 Not my place to say it, but I don't see anything close to the linked GFG article in your submissions to problem G.PS: On a side note when do you intend to include an implementation of Segment Trees in your template? :)
•  » » » » 3 months ago, # ^ |   +6 Stop deceive. You cheated and therefore were punished. Please don't distract me. Just don't do it again.Other solutions: 170249794, 170266270, 170277345.Your submission: 170280792
•  » » » 3 months ago, # ^ |   +3 Spoiler
•  » » » » 3 months ago, # ^ |   0 fact
 » 3 months ago, # |   0 Finally :)
•  » » 3 months ago, # ^ |   0 Finally what ?
 » 3 months ago, # |   0 Hello I've got a system message that my submission to problem G coincides with some participants, but I've used the code present on GFG link to the GFG article Kindly consider my participation in this round. Thank You.
•  » » 3 months ago, # ^ |   0 Sorry, I reverted the punishment.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 My solutions are still skipped and got huge negative delta :(
•  » » » 3 months ago, # ^ |   0 reverted ? i think the punishment got increased.
•  » » » 3 months ago, # ^ |   0 MikeMirzayanov Will i get my ratings back or not ? please reply...! My submissions' status is still showing skipped... :(
•  » » » 3 months ago, # ^ |   0 MikeMirzayanov Why only my ratings is dropped ?? :(
 » 3 months ago, # |   0 I have got a system message that my solution coincides with some other participant's solution for the question G, and as asked I am presenting here the common source published before the competition.I have even put the link above in my submission. So please revert the decision.
•  » » 3 months ago, # ^ |   +9 Sorry, I reverted the punishment.
•  » » » 3 months ago, # ^ |   0 Damn. That was fast.
 » 3 months ago, # |   0 why is the rating update taking so long?
•  » » 3 months ago, # ^ |   0 Yeah, I was checking it all night.(about ten times
•  » » » 3 months ago, # ^ |   0 Guess it got updated 24hrs after the contest
 » 3 months ago, # | ← Rev. 3 →   -13 .
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 .
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 .
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 .
 » 3 months ago, # |   0 My solution got matched with some xyz person. And I just do not know how.. Maybe because I tried running the solution on ideone.com I just do not know how to justify it now.. but since it was the first time, I just do not know how to tackle it. Please consider my request to give my ratings.. this should be seem that I have done 3 more questions, and since I did them all correct, I would not have cheated for sure.. I request you to please consider me this time.. next time, I wont be using any online ide. And I assure that.
•  » » 3 months ago, # ^ |   0 And I request you to revert the decision for the first unintentional mistake that I committed. Please sir.
•  » » » 3 months ago, # ^ |   0 MikeMirzayanov, sir.. please have a look at my request.
•  » » » » 3 months ago, # ^ |   0 MikeMirzayanov, sir.. please atleast let me know the status. I do not have any evidence to justify this.. but the past records can be checked and then, I might be judged. The ans to B is matching, and I did till D. See the feasibility of me cheating. I just want to say, it was completely unintentional that it got leaked. But because of this unintentional error, the records will get affected, and even all my work for that particular contest will go in vain. Please consider these issues while making a decision what to do with my contest rating.
 » 3 months ago, # |   0 In memory of my first AK (without editorial)! The only pity is that F didn't solved in time, since $i$ and $j$ are written backwards. qaq
 » 3 months ago, # |   +10 Your solution 170295384 for the problem 1722G significantly coincides with solutions Jeopardy_007/170181586, kshitijsabale/170235981, pravin_as/170236185, sksusha8853/170244580, daijoub_dattebayo/170253614, Ag.akhand29Dec/170260220, vipin/170268963, coomlhamdle/170268986, no-one/170270439, pritish_001/170280715, vamshikrishna7697/170283391, saranshgoel_20/170287297, O_QufaD/170287888, noozy/170289556, noob5367/170290799, anurag78_20/170293266, CodeR_SaaD/170294427, singham_20/170294546, anupam_singh20/170295384, blablablacksheep/170295836, abhirai24/170297702, xorhero_02/170299463. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.Hello! This question had a similar logic as https://www.geeksforgeeks.org/find-n-distinct-numbers-whose-bitwise-xor-is-equal-to-k/, which means the code was published before the round, so I thought to use it. I think that the coincidence has occurred due to the use of a common source published before the competition. I don't even know any of the person's mentioned above. Is it a violation of rules, if it isn't then I request you to please look into this and resolve this. Thank You@MikeMirzayanov Why only I got the penalty, and not everyone, while no one else got it Only my rating became negative
•  » » 3 months ago, # ^ |   -12 If you use a piece of code that’s not yours, you’ll need to mention in your code (probably commented out) the source of the code
•  » » 3 months ago, # ^ |   0 My rating got negative too :( and nobody is replying...
 » 3 months ago, # |   -12 My account was stolen by my classmate, so he saw my submission code and submitted it on his account. Please give my raiting back.And I don't now that!!!@mesanu@ mesanu@flamestorm@ flamestorm
 » 3 months ago, # |   +4 Me looking at my code for F after getting it accepted. (170379863) ...
•  » » 2 months ago, # ^ |   0 what is the idea behind your solution?
 » 3 months ago, # |   0
•  » » 2 months ago, # ^ |   0 Actually, I am checking out that, is there any connected component of size which is not equal to 3 (here two nodes are connected if they share a side or a corner). if so, then just print NO. Otherwise, I am viewing all the components which are connected and checking that whether they are L-shape or not.