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
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...
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
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.
it seems that we have the same idea
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
i do it with queue :)
It can be done too, because there indices that must be changed before others right?
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 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$$$.
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
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
Now , I got it
Thanks
170326725 Here you are
Simple implementation for problem G
Thanks
Problem F can be done using
DFS
:D
(￣︿￣)
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
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!
My first contest solving more than 1 problem :) I was excited to realize I could use a max heap to solve problem D.
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.me/contest/1722/submission/170290140
Any help would be very appreciated.
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.
Can u share how to write the fuction how to out the input of the test
Let's consider your latest attempt at Problem 1722F: L-Shapes. Your latest submission is 286022069, where you failed Test Suite #2, and the feedback says that the 50th token does not match. Since the output is just one line of YES/NO per test case, this means that the 50th test case is incorrect. Now, the objective is to find out what is the 50th test case in Test Suite #2.
To do this, we can first detect Test Suite #2 by checking if the number of test cases is exactly 100. If not, then the code should run as normal and pass Test Suite #1. But if it is exactly 100, then we are in Test Suite #2. From there, you can simply read the first 49 test cases without printing anything, and then read the 50th test case and print only the input for the 50th test case. I have done this (using your submission) to construct the following submission: 286061011; it's the same code as yours, except with two new functions, burn and reveal, and a check in the main function where if the number of test cases is 100, then burn the first 49 cases and reveal the 50th case.
Of course, the submission verdict is Wrong Answer, but you can view the output that the submission produced, which is the 50th test case:
You can test and see that your code does, indeed, output YES, when the answer should be NO.
Oh tks u so much
Can u send me your code :(((, I don't understand :(
Oh sorryy I see it
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
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$$$)
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
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 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
Another way to solve F: L-shapes:
ref: https://codeforces.me/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.
My Solution for F
did the same thing as mentioned in the editorial but is easier to understand.
My solution : 170453262 for problem F
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
Is there anywhere I can view solutions in java?
The status page (https://codeforces.me/contest/1722/status) lets you filter by language.
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:
Is there any other way to solve #C without using a map?
Use sets, check out my submission here at https://codeforces.me/contest/1722/submission/170192052
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.
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)
Problem F can be solved easily using 8-directional floodfill
As a fun fact, you can solve G just by printing random numbers and equalizing Xor with the last two elements.
whats the logic behind it
because if xor of odd position is same as even position then xor of whole array will be zero so we need to create an array such that xor of all element is zero
For problem G: After noticing we need n numbers such that their xor is zero, we can use https://oeis.org/A003815 as follows:
My solution to G.
basically xor of x,x+1,x+2,x+3 is 0 and also xor of their alternate indexes. so every n could be writtern in form of 4x,4x+1,4x+2,4x+3. we will be taking avantage of this as an extension
Code ``` vector<vector> arr(4); arr[0]={0,1,2,3}; arr[1]={2,0,4,5,3}; arr[2]={4,1,2,12,3,8}; arr[3]={2,1,3};
ll n,x=16; cin>>n; ll val=n%4,extra=n-arr[val].size(); for(ll i=0;i<(ll)arr[val].size();i++){ cout<<arr[val][i]<<" "; } while(extra--){ cout<<x<<' '; x++; } cout<<nl;```
E :solution with 1d prefix sum https://codeforces.me/contest/1722/submission/265651414
In fact in
G, we can choose any number from[18,30]as the lastbutone'th number as because theXORof the(n-2) elementswould atmost be(n+1){by the consecutive XOR property of elements} and as elements range from2*10^5 which is approximately < 2^18, butn+1 is less than 2^18so we can use anything from18 & beyond. Hope it helpsE can be solved in $$$O((n+q)\log(max(h_i))\log(max(w_i)))$$$ with the same amount of memory (if you choose the container as nested hash tables) or $$$O(max(h_i)max(w_i))$$$ (if you choose arrays which are faster) if you used 2D BITs. The solution is 2x faster than the normal solution: https://codeforces.me/contest/1722/submission/267849082, https://codeforces.me/contest/1722/submission/267849782.