Thanks for participating!
Idea: mesanu, MikeMirzayanov
Tutorial
1722A - Spell Check
Check if the string has length 5 and if it has the characters $$$\texttt{T}, \texttt{i}, \texttt{m}, \texttt{u}, \texttt{r}$$$. The complexity is $$$\mathcal{O}(n)$$$.
You can also sort the string, and check if it is $$$\texttt{Timur}$$$ when sorted (which is $$$\texttt{Timru}$$$).
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
string name = "Timur";
sort(name.begin(), name.end());
int n;
cin >> n;
forn(i, n) {
int m;
cin >> m;
string s;
cin >> s;
sort(s.begin(), s.end());
cout << (s == name ? "YES" : "NO") << endl;
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
void solve() {
int n;
cin >> n;
string s, t;
cin >> s >> t;
for (int i = 0; i < n; i++) {
if (s[i] == 'R') {
if (t[i] != 'R') {cout << "NO\n"; return;}
}
else {
if (t[i] == 'R') {cout << "NO\n"; return;}
}
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
void solve() {
int n;
cin >> n;
map<string, int> mp;
string a[3][n];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
mp[a[i][j]]++;
}
}
for (int i = 0; i < 3; i++) {
int tot = 0;
for (int j = 0; j < n; j++) {
if (mp[a[i][j]] == 1) {tot += 3;}
else if (mp[a[i][j]] == 2) {tot++;}
}
cout << tot << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
long long tot = 0;
vector<long long> v;
for (int i = 0; i < n; i++) {
if (s[i] == 'L') {
v.push_back((n - 1 - i) - i);
tot += i;
}
else {
v.push_back(i - (n - 1 - i));
tot += n - 1 - i;
}
}
sort(v.begin(), v.end(), greater<int>());
for (int i = 0; i < n; i++) {
if (v[i] > 0) {tot += v[i];}
cout << tot << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: mesanu
Tutorial
Tutorial is loading...
You can read about 2D prefix sums if you haven't heard of them before.
Solution
#include <bits/stdc++.h>
using namespace std;
long long a[1005][1005];
long long pref[1005][1005];
void solve()
{
long long n, q;
cin >> n >> q;
for(int i = 0; i <= 1001; i++)
{
for(int j = 0; j <= 1001; j++)
{
a[i][j] = pref[i][j] = 0;
}
}
for(int i = 0; i < n; i++)
{
long long h, w;
cin >> h >> w;
a[h][w]+=h*w;
}
for(int i = 1; i <= 1000; i++)
{
for(int j = 1; j <= 1000; j++)
{
pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
}
}
for(int i = 0; i < q; i++)
{
long long hs, ws, hb, wb;
cin >> hs >> ws >> hb >> wb;
cout << pref[hb-1][wb-1]-pref[hb-1][ws]-pref[hs][wb-1]+pref[hs][ws] << endl;
}
}
int main() {
int t = 1;
cin >> t;
while(t--)
{
solve();
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
const int dx[3] = {-1, 0, 1}, dy[3] = {-1, 0, 1};
void solve() {
int n, m;
cin >> n >> m;
char g[n][m];
int id[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
id[i][j] = 0;
}
}
int curr = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '*') {
vector<pair<int, int>> adjh, adjv;
if (i > 0 && g[i - 1][j] == '*') {
adjh.emplace_back(i - 1, j);
}
if (i < n - 1 && g[i + 1][j] == '*') {
adjh.emplace_back(i + 1, j);
}
if (j > 0 && g[i][j - 1] == '*') {
adjv.emplace_back(i, j - 1);
}
if (j < m - 1 && g[i][j + 1] == '*') {
adjv.emplace_back(i, j + 1);
}
if (adjh.size() == 1 && adjv.size() == 1) {
if (id[i][j] == 0) {id[i][j] = curr;}
else {cout << "NO\n"; return;}
if (id[adjh[0].first][adjh[0].second] == 0) {id[adjh[0].first][adjh[0].second] = curr;}
else {cout << "NO\n"; return;}
if (id[adjv[0].first][adjv[0].second] == 0) {id[adjv[0].first][adjv[0].second] = curr;}
else {cout << "NO\n"; return;}
curr++;
}
else if (adjh.size() > 1 || adjv.size() > 1) {
cout << "NO\n"; return;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '*') {
if (id[i][j] == 0) {cout << "NO\n"; return;}
else {
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (0 <= i + dx[x] && i + dx[x] < n) {
if (0 <= j + dy[y] && j + dy[y] < m) {
if (id[i + dx[x]][j + dy[y]] != id[i][j] && id[i + dx[x]][j + dy[y]] != 0) {
cout << "NO\n"; return;
}
}
}
}
}
}
}
}
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: mesanu
Tutorial
Tutorial is loading...
Alternate Tutorial Sketch
Output the integers from $$$1$$$ to $$$n-3$$$, then $$$2^{29}$$$, $$$2^{30}$$$, and the XOR of those $$$n-1$$$ numbers. Why does it work?
Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
int case1 = 0;
int case2 = 0;
for(int i = 0; i < n-2; i++)
{
case1^=i;
case2^=(i+1);
}
long long addLast = ((long long)1<<31)-1;
if(case1 != 0)
{
for(int i = 0; i < n-2; i++)
{
cout << i << " ";
}
case1^=addLast;
cout << addLast << " " << case1 << endl;
}
else
{
for(int i = 1; i <= n-2; i++)
{
cout << i << " ";
}
case2^=addLast;
cout << addLast << " " << case2 << endl;
}
}
int main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
}
I didn't even think that Timur is lexicographically in order. What a brilliant solution!
Edit: It isn't, but it's still an interesting solution to think of.
Its not.
It should be Timru
i... totally knew that, good reading comprehension, well done, you passed the test
there should be "Timru" instead of "Timur" in the editorial solution
it is sorted afterwards , so eventually it is Timru only
Timru
Problem D can also be solved in O(n) using two pointers
exactly
Can you give your solution here it would help
here if you need explanation feel free to ask
Hello, I saw your solution but I didn't understand this line . What is it for > for (k;k<=n;k++) ans[k]=s;
let's suppose that it was already optimal like RRLL so in the line you mentioned it just sets the remaining indexes (which could not be covered in while loop cuz of being optimal) they will just get the previous value as we will not be changing them...
Thank you.
Let's say the number of characters I needes to change was 8 and n is 10. I need go give an answer for all k such that 1<=k<=n so I just output for the remaining k
I got it. Thank you so much.
You're welcome
Check out my submission for problem D it might help you understand you the two pointer approach bettetb
Hi, I couldn't understand why you changed both the front and back pointer simultaneously in the while loop.
Edit -> Nevermind, got it. Thanks.
I solved it in O(n) aswell, but using prefix array
170271299
Can u pls explain,how did u do it using Prefix arrays
Take a look at the comments in the submission, if that doesn't help let me know once again.
Still i didn't get .M new to prefix array
You can have a look at others two-pointer solution. It's almost similar.
Here you can go to this link for prefix array.
Now, for this question in each move you make, you want to maximise the value you can get, so it makes sense to pick either the left-most or right-most direction that has to be changed.
Take this example
12
LRRRLLLRLLRL
Split it into two half's,
LRRRLL LRLLRL
Now, for the left part, you want to make everything R, while for the right part you want everything to be L. (why? i will leave that to you)
For the first part, we will work from left to right, for right part we will work from right to left. (This can be done with two pointer aswell)
Now, whenever you find a value that has to be changed, remove what it was contributing to the sum, and add what it will contribute when changed the direction.
Keep storing them in array. Then make a prefix array.
Now, for each move from 1 to n, you can add their respective moves to the sum.
Yes, I solved it in the same way.
here
What is two pointer approach... Can you share some resources from where I should learn... It would be a great help
Check Codeforces edu section. You can also read about it on USACO Guide
Two pointer is basically using two indices to traverse through an array on the basis of some condition that you can apply on both the pointers(pointing to a particular index), like in the D part of the question we take one pointer at very start and one pointer at very end of the array and then we can check if we got a left viewer with first pointer then changing it to R will give a better score till n/2-1 and checking the same thing for the right pointer for the right side viewer till n-n/2, we can do this till left pointer is less than right pointer.
To understand two pointers you should try solving problems for it instead reading about it, this link will work for basic problems Two pointers and problems on it
i do it with queue :)
It can be done too, because there indices that must be changed before others right?
Super Cool Bro ,How did that idea come about?
time O(n), space O(n) with a queue: https://codeforces.com/contest/1722/submission/174060421
Why is problem A $$$O(n)$$$? You check if $$$n = 5$$$ in $$$O(1)$$$; If it is, then sort the string which in this case will always have length $$$n = 5$$$ so sorting and checking is done in $$$O(1)$$$ (since the length is upper bounded). So overall $$$O(1)$$$, or am I missing something?
I think that's true. Change it, flamestorm.
You check if "T" is in the string, that can be done in $$$O(1)$$$ (since it only has 5 elements). Then you check if "i", also $$$O(1)$$$ And so forth. In total $$$5 \cdot O(1) = O(1)$$$
You have to read the string size of n, so it is O(n)
problem G:
topic 1
Regardless of your correct answer, when you choose some elements and take their XOR, then the value will be equal to the XOR of the remaining elements. Why?
Sample: $$$(4,2,1,5,0,6,7,3)$$$ is one of answer for $$$n=8$$$, and $$$4 \oplus 0 \oplus 3 = 2 \oplus 1 \oplus 5 \oplus 6 \oplus 7 = 7$$$
Remember $$$x \oplus x = 0$$$ and $$$a \oplus b = c \leftrightarrow a = b \oplus c$$$ (you can move an element from one side to the other side).
Let's define your answer $$$A$$$. Your answer must satisfy:
$$$A_1 \oplus A_3 \oplus \dots = A_2 \oplus A_4 \oplus \dots$$$
$$$\leftrightarrow A_1 \oplus A_2 \oplus A_3 \oplus A_4 \oplus \dots = 0$$$
$$$\leftrightarrow$$$ (XOR of elements you choose) $$$=$$$ (XOR of the remaining elements)
topic 2
There exists a randomized solution.
[1] Take $$$n-1$$$ distinct integers from $$$[0,2^{31})$$$ and name the set $$$S$$$.
[2] Let's define the XOR of $$$n-1$$$ elements $$$x$$$. If $$$S$$$ doesn't contain $$$x$$$, add $$$x$$$ to $$$S$$$ and $$$S$$$ will be the answer (Q. why? A. see topic 1). Otherwise, back to [1].
topic 3
For $$$3 \le n \le 6$$$, the answers are provided in the sample, so let's use them as a prefix.
After that, add $$$(100,101,102,103,\dots)$$$ until the length of the sequence becomes $$$n$$$. (note that the length of added sequence is a multiple of $$$4$$$ ) Then, you can get a correct answer.
Submission: 170321109
For all integer $$$k \ge 0$$$, $$$(4k) \oplus (4k+1) \oplus (4k+2) \oplus (4k+3) = 0$$$. Let's try to proof yourself!
master piece. i tried to construct a solution similar to topic 3, but unfortunately fell into tons of case work.
however, instead we can take advantage of samples, XD
thanks a lot!!
Thanks alot. Can you share the proof of topic 3 ?
Let's see the bitwise expression for some examples. For $$$k=37$$$,
The prefix of bitwise expression except the last $$$2$$$ digits are same, so their XOR is $$$0$$$. And the last $$$2$$$ digits are $$$00,01,10,11$$$, then their XOR is also $$$0$$$. So, overall XOR is always $$$0$$$.
That's great! Thanks alot.
A1⊕A3⊕⋯=A2⊕A4⊕… ↔A1⊕A2⊕A3⊕A4⊕⋯=0
can you swap randomly and still have the equality?
if yes, can you do the same in
X ^ Y < A ^ B -> x ^ B < A ^ Y ?
The latex for $$$2^{30}$$$ is bugged in the tutorial of problem G.
Aside from that, problem G is a really cool problem!
What no {} does to a mf
For anyone who is finding the solution of problem F, hard to understand/code, can take a look at my solution using DFS 170297341
D can be solved using two pointers.
The main idea is that the first half of the line should look to the right and the second half to the left. We keep two pointers l and r on both ends and recalculate the sum whenever we encounter a position that needs to be changed.
Can we solve problem E using binary search?
should give a TLE or difficult to pass since for every query you will traverse all 1000 (x) and BS for (y)
which will give "1e5 * 1000* log(1000)"
I did it this way because I didn't know about 2d sum prefixes. You need to keep a sorted 2d array, and then another 2d array of sum prefixes for 1..1000. Then you do two binary searches on the ranges to get your start and end.
It was slow but I passed using Go at 3500ms.
May be that will fail system testing.
It did TLE. I also solved with same approach and it TLEd.
And yet somebody's n*q solution passes :clownface: https://codeforces.com/blog/entry/106478?#comment-948495
Yup you were right.
Mine Problem C was also hacked due to TLE I used a very dumb method to solve that initially.
I got TLEd for that
I tried but I don't think it will pass with Python. https://codeforces.com/contest/1722/submission/170427049
Good contest, got sidetracked by D by trying to use two pointers. Your solution is much more elegant.
Weak pretests for A , so many solutions got hacked.
Your solution is weaker
Agreed and that's a pity that such a solution passed.
How to write the code for Problem G with the alternate tutorial, I am unable to understand the approach
underStood
170326725 Here you are
Simple implementation for problem G
Thanks
Problem F can be done using
DFS
:D
(￣︿￣)
That’s what I did lmao
I had school so I wasn't able to do the contest, however I've solved them all and I present my solutions. They may or may not be worse quality than the official editorial.
I did a really really really really messy implementation. The much nicer way that it could have been done is to simply sort the string and check if it's equal to the string you get from sorting Timur. I'm not linking my submission b/c the code will make you lose braincells.
Just change the 'G's to 'B's and check if the rows are the same. You can change the 'B's to 'G's if you want, but you need to pick one and change throughout the input. 170184897
Create a map. m[s] will store the number of strings equal to s in the input. Then for each player, get their score using the map. 170192041
The greedy solution of mine is to always prioritize changing people from the left and right rather than the middle as they simply affect more people. I first computed the answer you get with 0 changes and stored that. Then I kept 2 pointers i = 0 and j = n-1 to check the extreme left and right. If the element i was pointing at was an 'L', I would switch it to be an 'R' and updated my answer, vice versa for j. Finally I increased i by 1 and j by -1. What this does is it effectively does all necessary operations in the optimal order. Finally, print the answer. The answer for the ith case is the max of the answer for the ith case and the answer for the i-1th case. These values can easily be stored during the process. 170318148
Use 2D prefix sums. ps[i][j] will store the total areas of all rectangles with a height <= i and a width <= j. You can easily build this when reading the input. This works b/c the maximum height and width values are 10^3 each. So you only need 10^6 space which is doable. Each query can be solved in O(1) time very easily using the prefix sums. 170329944
Use DFS or BFS or whatever and find all the connected components of '*'s. If any of these components's size is not equal to 3, there is no answer. Now check if all the components form an L shape. After that, check all pairs of components and make sure no corners intersect. If all the conditions are met, then the answer is YES. 170329757
Note that if you add ...01 ...10 ...00 and ...11 to a good array, the array will stay good. (Note that the prefix "..." has to be the same for all 4 numbers). Now there are just 4 cases for n: n = 3 + 4k, n = 4 + 4k, n = 5 + 4k, and n = 6 + 4k. The answers for 3, 4, 5, and 6, are given in the input. Then just add the extra elements needed by iterating over that prefix and adding the 00, 01, 10, and 11 suffix respectively. 170329345
Good!
Can you please tell me where my submission 170342106 for problem E is failing?
I think your code is quite overcomplicated
tgp07 Excellent editorial, better than official one! Could you please tell me if there is a way to solve E under the same time constraints for tighter dimensions of the rectangle say 1e5 or 1e9 or even higher?
That would be a lot tougher. I'm not immediately sure of any way to solve that.
your G one is really good Thanks for sharing.
I think an improvement for F would be to extend adjacency to include diagonals, i.e., each cell has up to 8 neighbors for the purposes of DFS. Then all we need to do is make sure each connected component has size 3 and forms an L shape.
This way, there is no need to check if different blocks touch by edge or corner, since the DFS would've merged such cases into larger components.
(also, checking whether three cells form an L-shape can be done by simply checking if, for each of the three pairs of cells, the difference between the x- and y-coordinates is at most 1)
This seems smart, have you submitted a solution with this approach?
I had a partially written code, but the contest ended and I didn't bother finishing it up. But your comment encouraged me to complete and submit it, so here it is: 170513958!
Why I am getting runtime error in problem C .Here is my solution
Take a look at Ticket 16132 from CF Stress for a counter example.
My first contest solving more than 1 problem :) I was excited to realize I could use a max heap to solve problem D.
Can anyone tell me a testcase where my submission 170342106 is failing for problem E?
Take a look at Ticket 16131 from CF Stress for a counter example.
got it thanks
What's hack ??! In the verdict of my submission it's written as hacked but earlier it was accepted any one care to explain what this hack is ??!
Some of the corner test cases are not added while you submit the solution. And if you have not handled those cases and someone else break your code for any of those test cases means your solution is hacked .
Damn. I was not getting what was going wrong in the first question. Used a if condition, which updates a count and individually checked the letters with T i m u r. But, it gave me wrong results. If i had not lost time on this, 5 questions were quite easy to do
When will my rating appear, yesterday was my 1st contest.
For div2, preliminary ratings are updated in 2-3 hours. For education rounds/Div 3/Div 4, we have an open hacking phase which lasts for 12 hours so yeah, expect waiting for atleast 18 hours.
Ok
bro I am new here.Can you tell me what is this open hacking phase?
In div3/4 and Educational round, we have an open hacking phase for 12 hours. This means you can view others' code and find a test case where their code fails. If you hack their solution, the system will use this test case provided by you after these 12 hours during the system test (after which we get our final result, I hope you know the difference between system test and pretests). Hacking others won't give you extra points in the Edu round or Div 3/4. The only purpose of Open hacking phase is to promote hacking others' solutions and to understand others' writing styles. Hacking others will give you extra points in Div 2/1. To know more in detail, please use the codeforces search box. Searching is a good habit when on the path to becoming a competitive programmer. All the best!
@nikhilofindia thanks bro
usually div. 3 gets preliminary rating updates by now right?
Max to Max 5PM IST (from what I have experienced) This is worst case.
Edit: Looks like we have a new worst
Hey!, can someone help me up solving question F,
My logic for the solution was that for each * there can be only and only 2 '*' neighbors in all 8 directions(if a cell exists there) no more, no less than that.
But it fails on test no. 4, 69th ticket. can someone help me find a test case where this fails. WA link — https://codeforces.com/contest/1722/submission/170290140
Any help would be very appreciated.
Check out my solution maybe it’ll help you
Thank you, nice code
13 3.*.*.*.*.Thanks a lot, how do you come up with such cases, like how do you think of cases where our code might fail, how to develop that? any tips on that would be very helpful.
If it's after the contest, you can simply view the test cases in your submission. Often the input would be truncated, but you can often still find a way to reveal it. Modify your code by adding conditions to specifically check for the problematic test case, and then use it to print the result.
In this case, for example, you can see that in Test #4, the first case has n = m = 3, unlike the earlier Test Suites. So you can write your program such that if the first test case begins with n = m = 3 (you can use scanf for this, if desynced with cin), then you call a different function that reads the first 68 cases while printing absolutely nothing (not even the answers), and then reads the 69th case to print the complete test case details. When submitting, this should pass Tests #1-3, and then print the problematic test case in #4 for you to view.
This can be cumbersome sometimes, but at least it's a generally definite approach to finding the test case that breaks your program. I haven't yet encountered a situation where I was unable to expose the problematic test case this way.
That's an awesome way to find a test case, Thanks a lot
1722A - Spell Check Hacking not done properly, go through it once
My idea for G : XOR of 4 consecutive numbers starting from 0 is 0. 2^20 is greater than 2e5 which gave me sufficient power of 2's to play with.
Requires just some more case work for the remaining element. Approach
for problem G
for n = 5,
the solution: 0 1 33554433 2 33554434
is valid or invalid???
Can anyone please help me??
TIA
My code for C using sets concepts in maths.
Funnily I completed sets chapter only yesterday.
fst
Is it only Me or anybody else also noticed that F was comparatively easy E for those who till now havent encountered problem based on 2-D PREFIX Sum . I am feeling very frustrated as I spent more than one hour on E and also during the contest F have least successful submission so I just dont focused on F
problem D can also be solved in O(n) time using two pointers using a greedy approach. in the first half of the string, we can get better answer by converting the leftmost 'L' to 'R' and in the second half of the string, we can get better answer by converting the rightmost 'R' to 'L'.
link to my code — 170257607
A very simple and easy solution of G .
Alternate solution for Problem G:
Observe that $$$ a \oplus b$$$ $$$=$$$ $$$\sim a \oplus \sim b. $$$ Now you can construct a sequence $$$a0$$$, $$$\sim a_0,$$$ $$$a_1,$$$ $$$\sim a_1,$$$ $$$a_2,$$$ $$$\sim a_2, \dots$$$ (upto n terms) where $$$n \equiv 0$$$ ($$$mod$$$ $$$4$$$).
For $$$n = 4k+1$$$ or $$$4k+2$$$ or $$$4k+3$$$, just take some prefixes of length $$$1$$$ (0), $$$6$$$ (4,1,2,12,3,8), and $$$3$$$ (2, 1,3) respectively from the given testcases itself and the remaining sequence will be of length $$$4k'$$$.
Note that $$$a_0$$$, $$$a_1$$$, $$$\dots$$$ can be taken to be $$$13,$$$ $$$14,$$$ $$$15,$$$ ... as none of the prefixes contain elements $$$>13$$$.
Also, $$$\sim a$$$ represents 1's compliment of $$$a$$$ inverting all 32 bits of $$$+a$$$, although (even the first 20 bits would work considering the constraints on $$$a_i$$$)
On Problem 1722B Colourblindness I had the same Approach But still got WA on test case 3
what is the use of greater() in the sort function of the D problem?
Its a comparator which defines how you want it be sorted. You can read more about it here
thanks
In the problem E, trivial $$$O(n q)$$$ solution passes due $$$\mathrm{TL} = 6 \mathrm{s}$$$: 170297542
I wonder how your fastIO works...My BF solution 170407110 could pass only when adding your fastIO code. (And on test 4, it is 15 times faster than simply using untie cin/cout). It seems impossible because IO shouldn't be the bottleneck of this problem. I'm really confused about this.
We need optimize any constant in time complexity of solution. And it is fastest I/O (on Windows) that I have been seen.
In it, I completely abandoned small buffers (usually ~2KiB) that lead to a lot of file operations, and also decided to completely abandon non-system I/O functions due to overhead. Large buffers allow your program to use two file operations during work.
And when
-O3is specified, gcc inlines my functionReadInt32, but noprintfandstd::cin.I discuss this with some friends and get a weird conclusion. You can see the difference between 170435459 and 170435486. Seems that when we replace the last cin with a function (although we still use cin to read), the compiler will use SIMD to optimize the if statement. Replace function with inline function even macro gets the same result. But just using cin or scanf won't trigger optimization. I have no idea why this happens :(
I solved 3 problems but my rating doesn't change. my rating point is still 0point
I solved problem G quite differently from the editorial method utilising the property that XOR of consecutive numbers x and y is always 0 when x is an even number (if you didn't know this, it's easy to see why, by taking a few consecutive numbers and looking at their binary representation).
Let set a and b represent respectively the set of numbers at even positions and the set of numbers at odd positions. Then we break solution into 4 cases depending on the remainder of n on dividing by 4.
Here both sets have an even number of elements. So we can just keep pairing two consecutive numbers and that will suffice.
In this case, set a will have 1 more element than set b. In order for them to have the same end result (xor), we can just insert a 0 in set a as 0 is a neutral element. Now we just have to put pairs of consecutive numbers as in above case.
This case is similar to Case 2 but set a will have an even number of elements and set b will have an odd number of elements. We can make up for the lack of a pairing element in set b by just inserting element 1 (which was to be the result of the XOR of two consecutive elements anyway).
Here both sets will have odd size. That means they will both need a single extra element that can't be paired. That element can't be the same (that's why minimum n is not 2 in the problem).
We can break any such n into a combination of 3's and 2's, there will be a trio of 3 numbers and all the rest are pairs. Minimum n is 3, so this will fit. We can find 3 such numbers for both the sets s.t. they are all different and their XOR is same. I just looked at the samples which happen to have this test case for n = 6. So I took the numbers from the sample solution
(set a : 2, 3, 4 ; set b : 1, 8, 12), their XOR is 5. The remaining elements can all be pairs of consecutive numbers as described above.
I think some of the cases can probably be combined for a simpler solution. Please let me know in the comments.
Not so elegant and repetitive implementation : 170369765
I solved in the same way
In E, I'm getting MLE if I put prefix array in the heap memory, but the solution passing when I put the prefix array as a global array. Why is that so?
170374285
vs
170372939
The same thing was happening with me.
https://www.geeksforgeeks.org/why-global-array-has-a-larger-size-than-the-local-array/
Hope this helps!
A much simpler (in my opinion) and more readable solution for
Problem Fwith necessary comments : 170377676Another way to solve F: L-shapes:
ref: https://codeforces.com/contest/1722/submission/170380611
Note that, a 2x2 grid will contain L shape if and only if there are exactly 3 '*' in it.
1)Firstly for all 2x2 subgrid that contain L-shape, check whether its surrounding has any '*' in it, if so, then the ans is NO. [except for the corner along void position(exactly one such position) of 2x2 grid ,
eg: '#' in below picture [and ^ is void position] ]
...#
.*^.
.**.
....
2)Now the only problem is, there can also be any other shapes than L-shapes. To find that,
In logic1, just whenever current 2x2 subgrid contain L,(ie:exactly 3 '*' in it) , mark those positions as #.
So that all L shapes will be marked, and if there exist any other shape than L shape then it will remain unmarked(ie:remains *).
So, atlast traverse the whole grid to find any such unmarked position,
if so, the ans is NO,
Otherwise YES.
Can somebody explain solution E, I have never seen use of prefix sum like this. I dont quite get it what thay have exactly done here
suppose you have a data structure which stores 2D-prefix sums, such that sum of rectangles with height <= H and width <= W = pref[H][W]
then if you wanna know the sum of areas of rectangles with height < Hb and width < Wb (condition — i) then that would equate to pref[Hb — 1][Wb — 1]
now say you want the sum of areas of rectangles which have height <= Hs and width <= Ws(condition-ii)
the rectangles which satisfy both condition i and ii is the required answer
for learning about 2D-prefix sums I would suggest going through the USACO guide, they have detailed and easy to understand content, https://usaco.guide/silver/more-prefix-sums?lang=cpp#2d-prefix-sums
Thanks mate, U r a lifesaver
Why didn't my ratings update ? :'(
NVM LOL
My Solution for F
did the same thing as mentioned in the editorial but is easier to understand.
My solution : 170453262 for problem F
The first problem can be solved with a frequency array, by calculating the frequency of each character while taking inputs. Then check whether the frequency of each character of "Timur" is equal to one or not.
I got wa on F test 3 170393551 can somebody say the problem
Take a look at Ticket 16138 from CF Stress for a counter example.
Tnx
170377578
Lol, what's that supposed to mean?
Submission no
Unfortunately, I do not respond to personal requests. You can always consider purchasing a subscription if you need instant help.
If you want the community to help you instead, you need to describe your approach/issue with proper links to your submission. Just dumping the submission ID won't do it.
There is O(n) (I believe it is, at least amortized) solution for problem D https://codeforces.com/contest/1722/submission/170241642
Check out my solution which is straight O(N)
Is there anywhere I can view solutions in java?
The status page (https://codeforces.com/contest/1722/status) lets you filter by language.
It was a nice contest though F was quite exhaustive
Here is a bit shorter code for F: 170427907
Observe that for a valid construction:
1- Each * has exactly three neighboring *
2- Maximum connected chain of * is of length 3
second condition is neccesay to avoid patterns with shapes close to "circular" like these:
In Spell Check Why do we need to sort name too? Because if I'm not sorting name then I'm getting an error Please can anyone explain what I'm missing here
because its not lexicographic "Timur" -> "Timru" is lexicographic.
Is there any other way to solve #C without using a map?
Use sets, check out my submission here at https://codeforces.com/contest/1722/submission/170192052
Yes. I solved it using unordered_set.
c++ code: 170218148
Ahh, thanks (:
anyone , where can i get some greedy questions like "Line question", where need to handle edge cases and stuff like that?
Here you can see the promble F be sloved by using BFS.
Problem E can also be solved with offline queries and binary search on segment tree, which gives O(t*n*logn) that satisfied arbitrary large height and width of the rectangles.
Simple Solution for 1722F -L-shapes problem without DFS or BFS.
Note: Using 1-based indexing for matrix.
Traverse the elements of the matrix.
If at index (i, j) star is present, then let's take
cntStarsfor the count of stars around index (i, j) in its neighbor region of 3 x 3.Let
sumXandsumYbe the sum of x and y coordinates of neighbors of (i,j) where star '*' is found.If
(cntStars != 3) or (sumX == 3 * i) or (sumY == 3 * j), then we break traversal and print "NO".Otherwise print "YES".
If there are 3 stars in a 3x3 region around index (i, j) and at index (i, j) star is also present.
If the stars do not form an L-shape, then they will be aligned in a straight line and either sum of x coordinates or y coordinates will be thrice of i or j respectively.
C++ code: 170466848
Hello.
A question : why isn't enough to check only if the cntstars ==3 ?
what is the corner case ? 181822571
My solution for G:
xor of 2x (even no.) and 2x+1 is always 1.
Case 1: n%4 == 0: A simple solution would be 20,20+2n,21,21+2n,22,22+2n,....
Case 2: n%4 == 1: Just add a 0 at the end of Case 1
Case 3: n%4 == 2: Just add 4 1 2 12 3 8 this sequence at the end of Case 1 (Provided in sample input for n=6)
Case 4: n%4 == 3: Just add 2 1 3 this sequence at the end of Case 1 (Provided in sample input for n=3)
Nice solution!
https://codeforces.com/contest/1722/submission/170472565 Can anybody tell me the mistake in my code for Problem F
Take a look at Ticket 16145 from CF Stress for a counter example.
Thanks you sir for the help!
I got it
D in linear time : 170362765
Chekout the solution for Problem E 170565433
Upvote if you love competitive programming by heart.
Error Report:: For the 1722E ( Counting Rectangles ) Tutorial, the corners to consider should be top left and bottom right, instead of lower left and upper right!
I am not able to solve 4 th question . can anybody help to solve it?????
why does the another approach worked in G can anyone explain please?
although it was 3 months later but I have to say that the tutorial of G has a little mistake
I think it should be $$$2 ^ {30}$$$ here but it's $$$2 ^ 30$$$ :)
anyway, good problems and good tutorial !
Can anybody pls explain why all elements Xor equal to 0 is equivalent to Xor of elements in odd index equal to Xor of elements in even index. What I'm going to say is that all elements Xor equaling to 0 can't conclude to elements in odd index equaling to elements in even index. It is very confusing.
I got it. It means that the last element will Xor the same index elements also can be seen as delete the elements with the same index. Then the rest of the value is equal to the elements in the other index.
Why this code not working for A
int m; cin >> m; if (m != 5){ cout << "NO\n"; } int T = 0, i = 0,m = 0, u = 0,r = 0; for( int index = 0; index < 5; index++){ char c; cin >> c; if(c == 'T') T++; if(c == 'i') i++; if(c == 'm') m++; if(c == 'u') u++; if(c == 'r') r++; } if(T == 1 && i == 1 && m == 1 && u == 1 && r == 1){ cout << "YES\n"; }else{ cout << "NO\n"; }
Can anyone please help me in problem G, why this solution works? 170562100