awoo's blog

By awoo, history, 2 months ago, translation, In English

1697A - Parkway Walk

Idea: vovuh

Tutorial
Solution (vovuh)

1697B - Promo

Idea: BledDest

Tutorial
Solution (Neon)

1697C - awoo's Favorite Problem

Idea: BledDest

Tutorial
Solution (awoo)

1697D - Guess The String

Idea: BledDest

Tutorial
Solution (BledDest)

1697E - Coloring

Idea: BledDest

Tutorial
Solution (BledDest)

1697F - Too Many Constraints

Idea: BledDest

Tutorial
Solution (awoo)
 
 
 
 
  • Vote: I like it
  • +83
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

BledDest has made the task "awoo's favorite problem" :| kinda weired.

»
2 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

It shows tutorial is not available excluding problem A.

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Could any tell me why my approach to solving C is giving WA? https://codeforces.com/contest/1697/submission/160346935

My approach:

=> 1. Because we don't have ac or ca operations.

    if((s[i]=='a' && t[i]=='c') || (s[i]=='c' && t[i]=='a')) return "NO\n";

=> 2. Make s[i]=='b' and t[i]=='c' to s[i]='c' and t[i]='c' using bc operation via two pointer approach

    int l=0, r=-1;
    for(l=0;l<n;l++){
      if(s[l]=='b' && t[l]=='c'){
        r=Math.max(l, r);
        while(r<n && s[r]=='b') r++;
        if(r==n) return "NO\n";
        if(s[r]!='c') return "NO\n";
        s[l]='c';
        s[r]='b';
        r++;
      }
    }

=> 3. Finally you can remove characters which are equal i.e; s[i]==t[i] At this moment, we have all c's matched in both s and t Now we can match a's and b's using ab operation

    r=-1;
    for(l=0;l<n;l++){
      if(s[l]==t[l]) continue;
      if(s[l]=='c' || t[l]=='c') return "NO\n";
      if(s[l]=='b') return "NO\n";
      r=Math.max(r, l);
      while(r<n && s[r]=='a') r++;
      if(r==n) return "NO\n";
      if(s[r]=='a') return "NO\n";
      s[l]='b';
      s[r]='a';
      r++;
    }
  • »
    »
    2 months ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    Put it in spoiler idiot !

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    First observations is OK, sorry, I forgot statements

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The answer for this is NO, right? We can't make a in s to c.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks a lot epsilon_573! My observations are correct. The only mistake I made is removing those characters where s[i]==t[i] from the string and creating new strings. Commenting that part alone gave AC: https://codeforces.com/contest/1697/submission/160498351

        In almost every Div2 contest I do some silly mistakes in C and get WA although I get the right observations. I hope that will get fixed by giving more contests. Thanks a ton again epsilon_573!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you tell where does my solution fails

    problem id : 160924937

    my approach I try to make s and t equal from index 0 using simple idea that we can get b at any index if next all are a , i.e aaaaaaaab we can get b on any a similarly we can get c on any b , i.e bbbbbbc

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this code correct? Gives AC but just because of a single else break; it got hacked during contest. My rank went down from 2000 to 8k+. Had solved C in 14 mins. This shit hurts! Just missed a single else statement. 160439872

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Soon you will learn to gather yourself and lift yourself up from these situations. Wish you lots of good luck.

    Remember
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain problem C ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1697/submission/160358092 Can anybody please show me what is wrong on my sibmission of C?

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

F's idea was brilliant. It's not hard to recognize it as a 2-sat problem, but I got stuck with "is $$$a_i$$$ equal to $$$x$$$?" and can't come up with the idea presented in the solution.

Great problems overall. Thanks sir.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the ask_character function, can we not directly input a char instead of inputting a string and then returning its first charachter? Asking cause I seen a string being inputted in someone else's submission too

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Reading a char can be awkward as you have to be careful about spaces / EOL. Reading a string makes it more reliable and simpler (and probably has close to no impact on performance due to small string optimisations).

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh okay, understood. Thanks for the reply :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me how test #3 in problem B is generated? All other tests are fine, but test #3 alone seems to be quite an adversary to the dual-pivot quicksort which is used for the built-in primitive array sorting in java. What's more curious is that the built-in sorting algorithm switches to heap sort if it is too slow. I also tried to make a bad array for a bit via local machine and custom invocation, but it wasn't successful at all.

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
Checkout my approach for Problem C: [AC code] -> 160454978

In contest -> (Did a super silly mistake in updating Fenwick tree, due to which I got a SILLY WA in contest!)

Idea: I went backwards in string s, and checked if the characters mismatch, if it does, print "NO" if it's an 'a', as it cannot be swapped, else find the nearest 'b' or 'c' (pos) accordingly using set, and also check if there exists any other character between the current s[i] and the found pos, if it does, print "NO", else swap them, and move on (update the pos and fenwick tree as well)...In the end, just check if strings are equal...

Time complexity: ~ O(N(log(N))

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C has two pointer and dp tag, can anyone explain how can we use two pointer and dp in c?

»
2 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

for problem E Im using this fact that size of each component is at most 4 and use this to solve problem with another way

One can prove or disprove this؟؟

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I thought the same as well. It would be the four midpoints of the edges of a square.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I had just figured this out. It is entirely dependent on the 1st condition. Consider fixing the distance, and imagining the diamond of points around a given point equal to that distance. You can see that for two given points, if they are not on the same diagonal (same x + y or x — y), there can be at most two intersections of such diamonds and therefore at most two points that are equidistant to both of them, thus the max size is at most 4 if two are not on same diagonal. Obviously we cannot get more than 2 points all equidistant to each other that are on same diagonal. Lastly, you can find construction showing size 4 set is possible, therefore max size is 4.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I got this. It's not a proof, but a visualization for some cases. Let's see:

    The "big squares" are the sets of points having the same Manhattan distance to point A (or B).

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

C is a very strange problem. Let me describe my method.

We can replace "ab" with "ba", and replace "bc" with "cb". Firstly, the number of 'a', 'b' and 'c' must be equal in string $$$s$$$ and $$$t$$$. And if we remove 'b' from $$$s$$$ and $$$t$$$, the remaining string $$$s'$$$ and $$$t'$$$ should also be the same. This is because we can't change the relative positions of 'a' and 'c'.

So lets extract all 'b' in $$$s$$$ and $$$t$$$. They must match one by one like this:

  • $$$s$$$: ___b_b______b_
  • $$$t$$$: _b______b___b_

For a matched pair of 'b', where $$$s_i=t_j=$$$'b'.

  • If $$$i=j$$$, then no operation is needed.
  • If $$$i<j$$$, then we need to switch this 'b' in $$$s$$$ backward to position $$$j$$$, using operation "bc"->"cb". This means $$$s[i..j]$$$ must be either 'b' or 'c'.
  • If $$$i>j$$$, then we need to switch this 'b' in $$$s$$$ forward to position $$$j$$$, using operation "ab"->"ba". This means $$$s[j..i]$$$ must be eigher 'a' or 'b'.

The check can be done using prefix sum.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need prefix sum even, you can just iterate over the middle letters (since atmost you look at each letter once)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't put that much time into doing Codeforces contests — I am not professionally involved with programming, it is more like a hobby for me. But anyhow, I had been initially very pleased (since I am only a Newbie) during the contest when I had my solutions to A, B and C accepted. But then, during the hacking period, my solution to B was hacked. So, I was curious about what mistake I made. And now that I see the "official" solution to B described as merely "sorting the array and doing prefix sums" — which is what I did — my guess (which seems consistent with other comments) is that apparently by using one of the standard python built-in sort functions ("sorted"), it led to my solution exceeding the time limit. If that is indeed truly what happened (and maybe it wasn't?), that seems to suggest a significant problem on the Codeforces end in setting the time limits.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Input/output time seems to be critical in your case. Refer to my submissions or https://codeforces.com/blog/entry/83441

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! I very much appreciate learning the true explanation. As an outsider to these issues, I do find it interesting that on Leetcode, whose contests I regularly participate in, this — i.e., the slowness of Python in terms of input/output — doesn't appear to be much of an issue. Yes, there are times when Python's slowness does mean that a Python solution will not pass, in comparison to, e.g., a C++ solution. But I don't recall those differences being attributed to input/output issues (and thus they were not correctable by changing how participants using Python coded their input/output).

      Anyhow, thanks again for teaching me how to try to avoid this issue in future Codeforces contests. It is certainly interesting and surprising, at least to me, to learn about this being an issue.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Leetcode doesn't ask you to use standard input and output, it provides function arguments and checks return values, which has its advantages and disadvantages

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you! Yes, I certainly wasn't aware of this issue, and the questions of the advantages and disadvantages of each approach. It does raise interesting issues about what knowledge and skills a contest is supposed to be testing.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But yes in general, python is slow. In some platform, python and other slow languages are given some additional time. I've heard PyPy is sometimes a bit faster, or a bit slower, depending on problems.

»
2 months ago, # |
Rev. 3   Vote: I like it +40 Vote: I do not like it

I think my solution for E is simpler and more intuitive ( I think it might be because I observed that the maximum number of points colored the same is 4 ) I'll copy my comment from the other post (sorry if you read it there too ^_^):

"""

Just did problem E. Awesome problem!

First I noticed that the sizes of equal distance groups can only be 4 at most.

Then I noticed that you just need to keep a list of all points of minimum distance from you.

Then I noticed that the only way to color a few points the same color, is if they are all minimum distance from each other.

Then I noticed that a group (of min dist from each other) has to either be colored the same color, or all different, and this type of coloring is completely independent from the other choices for other groups.

From there it's straight forward, a dynamic programming depending on how many colors remain, and if you choose to color the group in the same color or all different colors (no other options). i.e. dp[number_of_group][colors_remaining][color_same_or_all_different]. dp size is n*n*2.

Don't yet know its rating, but might be the highest rated problem I solved!

"""

The way I found the groups is easy. After adding point X itself to the list of points with minimum distance from X (for convenience), to be part of a group, all the neighbors (with minimum distance) must have the exact same set of neighbors! if and only if one of them isn't — you are not part of a group. this was a simply O(n) for loop.

And this is not dfs as I'm only looking at neighbors!

Code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    The proof that there is at most 4 points with the same color in problem E. Suppose there are 5 points satisfy the conditions. We call it (x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5). WLOG suppose x1>=x2>=x3>=x4>=x5. Suppose their distant is N. The famous lemma from pigeonhole principle: In a mn+1 number sequence, then there exist an increasing subsequence with length m+1, or a decreasing subsequence with length n+1. By the lemma, WLOG suppose that y1<=y2<=y3. So the three equations hold. (x1-x2)+(y2-y1)=N (x2-x3)+(y3-y2)=N (x1-x3)+(y3-y1)=N But sum up the first two equation we can get: (x1-x3)+(y3-y1)=2N Which is a contradiction since N!=0. So there is at most 4 points with the same color.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Nice! I saw manhattan distance and was thinking for a bit if there was a good reason for choosing this particular metric, though I was pretty sure that it could be solved with arbitrary distances. With euclidean distance for example the problem would be trivial (max size is three.) I was guessing that with manhattan distance it might also be only a very small number of possible points in any clique with common pairwise distance.

»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Thank you sigma problemsetters for pretests in E! I really love submitting, getting AC on the last 7 minuites, FSTing, fixing it with one if statement in 2 minutes 33 seconds! It is obvious to me that if a problem includes case analysis the pretests should exclude specifically one case so you feel like an idiot! ORZ ORZ ORZ problemsetters.

I liked the problem, it is just painful to perform like a 2520, getting +154, FSTing and realizing that if that was in the testcases, you had time to correct it.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why I get TLE using Java in question B? https://codeforces.com/contest/1697/submission/160471991

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Could Problem F be solved if k is 1e5?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Submission C Plz help me to debug this I am swapping the char when its not same

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

 why?????

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain C i still don't get it

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    go through each character one by one.

    1. if s[i] == t[i] ---> it's fine, leave it and go to next character.
    1. else, string can be changed only if (s[i] == 'a'and t[i] == 'b') or (s[i] == 'b' and t[i] == 'c'). for any other combination you can't arrive to t.

    2. now let's take eg: s[i] == 'a' and t[i] == 'b', now I found nearest 'b' that is mispalced in s, let it be at index j.

    key point to note is there shouldn't be any 'c' between index i and j, because if there is 'c' in between you can't swap 'a' and 'b'. If there is no 'c' then you can simply write s[i] = 'b' and s[j] = 'a'

    I checked if there is any c in between by prefix sum method and I maintained a que for a,b,c seperately which has misplaced indexes of a,b,c respectively and took out first indexes of a and b ques, if i could swap them both.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Here are the following observations I have made some of them are relevant or later we can exclude them but they are good to understand the thought process.

    1. If the count of "a","b","c" is string "s" and string "t" then it is not possible to obtain "t" from "s".
    2. we are given two operations, one of them is ab->ba. This statement can be further visualized as For example: if we are given string "aaaba" then using above operation we can get this "aabaa" further "abaaa", etc. If you closely observe the pattern you can see "b" can be moved in the left direction and also we can observe that with the one movement of "b" in right index of "a" left to that "b" get increased by 1.
    3. Same this happen with operation 2nd bc -> cb. Here "b" is moving in the right direction of "c". and index of "c" present initially right to "b" get decreased by 1.

    4. It is clear from point 2 and 3 that in both the cases "b" is moving. So relative order of "a" and "c" in both the strings should remain same. For example: s = "abac" , t = "baca" Order of "a" and "c" in S = aac Order of "a" and "c" in t = aca Hence it is not possible to obtain t from s.

    Using above information you can rethink for you solution.

    And can anyone reply me how to think in the direction of binary search?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's an approach to problem C with O(n^2) (because the limit is 2 seconds). We will iterate i in the string from 0 to n — 1, if s[i] != t[i] then: *i = n — 1 or s[i] == 'c' or t[i] != s[i] + 1 (since to have 'ba', we need 'ab' and the same with 'cb) => NO *Next, we have j = i + 1, iterating to n — 1 and since we want to swap s[i] and s[j], j is the smallest that s[i] != s[j] *If j = n or s[j] != s[i] + 1 => NO *s[j] = s[i]

This is the code to know more what I'm saying: https://codeforces.com/contest/1697/submission/160477577

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think test cases for problem C were weak. My O(n^2) solution got AC.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Cleaner implementation for problem d 160750718

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For D if we binary search on [1, i - 1] (which is what I did during the contest) the number of type 2 queries has a loose upper bound of 1000*log(1000) which is roughly 10000. But the actual number is more like log_2(999)+log_2(998)+...+log_2(1) so I thought that might be under 6000, which was unfortunately wrong.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

It's possible to get a very readable implementation for problem F with operator overloading.

For instance, we can make it possible to write ts.either(A[i] < x, A[i] > x) for queries of the 1st type.

A full solution (in Python) is available here: https://codeforces.com/contest/1697/submission/160806370

The trick also works in C++, as it supports operator overloading too.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B

Why am i getting TLE? Please help me.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for D Can we do like this we will ask 2nd query for every substring of length 2, so if we at 0th index and answer for this is 2 then we can say this s[0] and s[1] are different and we will ask first query for index 0 and 1, and if answer is 1 then we will ask first query for 0th index and s[1] will also be s[0] and if we are at ith index i > 0, and answer is 2 for 2nd query , then we will ask first query only for (i+1)th index as we have already know the char at ith index and if answer is 1, then simply s[i+1] = s[i] this way it will ask n-1 query of 2nd type and max 26 query for 1st type

and if this logic is right ,can anyone tell me where i am doing wrong in my implementation. if logic is not right , please tell me where i am thinking wrong in this logic.

My implementation

Your code here..
		#include <bits/stdc++.h>
		using namespace std;	
		#define ll long long
		ll Max = 4e4;
		ll mod = 1e9 + 7;
		int main() {
			// your code goes here
			ios_base::sync_with_stdio(false);
			cin.tie(NULL);
			cout.tie(NULL);
			#ifndef ONLINE_JUDGE
				freopen("input.txt", "r", stdin);
				freopen("output.txt", "w", stdout);
			#endif
			// fill();
			ll tc = 1;	
			// cin >> tc;
			while (tc--) {
				int n;
				cin >> n;
				vector<string>v(n, "#");
				vector<int>a(n-1);
				for (int i = 0; i < n-1; i++) {
					int l = i + 1, r = i + 2;
					cout << "? 2 " << l << " " << r << endl;
					cout.flush();
					cin >> a[i];
				}
				for (int i = 0; i < n-1; i++) {
					if (a[i] == 1) {
						if (v[i] == "#")
						{
							cout << "? 1 " << i+1 << endl;
							cout.flush();
							cin >> v[i+1];
							v[i] = v[i+1];

						}
						else v[i+1] = v[i];
					}
					else {
						if (v[i] == "#") {
							cout << "? 1 " << i << endl;
							cout.flush();
							cin >> v[i];
						}
						if (v[i+1] == "#") {
							cout << "? 1 " << i+1 << endl;
							cout.flush();
							cin >> v[i+1];
						}
					}
				}
				cout << "! ";
				for (auto &x : v) cout << x;
			}
		return 0;
	}
.
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello!

    The same character can appear many times and make many sub-strings whose answer for the 2nd query is 2. So your number of 1st query may be very large.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me where my program fails? Submission ID: 161477229

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ans can go negative according to your case, but i shouldn't

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I love problem C, it kind of improved my thought process.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone tell why it is failing for 1697B PROMO CODE 1697B][SUBMISSION:161806993 - Промоакция

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should've used "long long int" instead of "long int". That was the main problem. Here is (your code) modified which passes: Code Link. Define long long int with ll to make things easier. Hope this helps!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anybody implemented 1697B — Promo in JAVA and passed?