I have an idea for F — Puzzle is that we first we will simplified fraction p/q and if p is odd we will mul p and q with 2 and we will try all (p,q),(2*p,2*q),... so when we have p we will create a nearly square with a=(p/2)/2 ,b=(p/2)-a(because it has the biggest area with perimeter p) and when we delete 1 small piece from the top-right the perimeter will not change and the area will reduce 1 so we can check if that is possible to have the raito (p,q) if we delete some small piece and also i it can it will be the smallest perimeter and area that we can build.(i can prove that but i can't comment here because my english is bad).

I tried something different on F, I realised that whenever a unit square shares exactly two sides with the existing shape, adding or removing it changes only the area (by +1 and -1 respectively) and leaves the perimeter unchanged. After this, I reduced the p/s fraction to it's basic form, where gcd(p, s) = 1; In this form, s * 2 + 2 is the maximum possible perimeter achievable by s squares, if the needed perimeter ratio exceeds this, then we output -1. Otherwise, we start at (0,0) and alternately attach one square upward or leftward: each step adds area +1 and perimeter +2. As soon as the current perimeter is divisible by p and the target area = s·(perimeter/p) fits inside the m×n “L” we have built (where m,n count how far up/left we have gone), we fill exactly the needed interior squares (each of which shares two edges, so perimeter stays fixed) until area = s·(perimeter/p). This makes a single connected shape with perimeter/area exactly p/s and under 50,000 pieces.

Here is my submission that implements the same, 322889890

An easier way to come up with the correct greedy for E: after observing that you won't use both b -> c -> a and c -> b -> a in the optimal solution, just simulate twice, once for the case where you never do b -> c -> a and once where you never do c -> b -> a, and take the minimum of the two cases. In the first case, for B's you will always try b -> a, for C's you will first try c -> a (so that you don't take away a b -> a for a future B) and then try c -> b -> a, and lastly try c -> b. The second case is similar, for C's you try c -> a then c -> b, for B's you try b -> a then b -> c -> a.

My submission

in problem B why we are not checking condition f[n] >= x & f[n] >= y & f[n] >= z we checked for largest side of box only.. why..? .Each f[i] is a cube that means each side of box (x , y , z ) must be at least f[n] for f[n] to be fit in box..what i am thinking wrong in this

In my solution for problem E, I too have used a greedy approach with sets, but for some reason it is giving me a TLE on test case 2

https://codeforces.me/contest/2111/submission/322749796

(My code might not be that readable, but I only want to know why is it exceeding time limit)

My solution for F: for each multiple of the perimeter, we will check if we can make the corresponding area possible. Lets say we are considering parameter X. X is equal to 2*(a+b), where a and b are the sides of the enclosing rectangle of the shape. so then lets consider the a shape whose sides add up to X/2. the minimum area a shape whose sides add up to X/2 is a+b-1 and the maximum is a*b, where a=(X+1)/2 and b=X/2, so that the area of the corresponding rectangle(or a square if (a+b)%2==0) is maximized. then as long as the corresponding area is within that interval, a solution exists. the construction itself is then trivial

I used the same approach for problem E, I just used variables to count the frequency of each sequence and utilizing the frequency to modify the string.

322753408 Why does it fail for test 4?

Why is this 322905305 failing on problem E. (Code has been written by little bit different algorithm and has been sent with my second account during contest)****

Thanks for Nice and in-detail, cool tutorials :)

Problem E can be solved in O(N+Q) with regret greedy.

322907253

Since we always want to turn the earliest non-'a' character to 'a', we can take a greedy approach initially. As we go through the queries (which are each a 'find'->'replace' character pair), we store the amount of c->b and b->c that we have seen, since these are not immediately optimal to use. We keep track of the earliest 'b' and 'c' in the string by using pointers, so going through the string is O(N).

Whenever we encounter b->a or c->a, we can use it by itself if the 'find' character is the same as the earliest non-'a' character. If the earliest non-'a' character is not the 'find' character, we can still turn it to 'a' if we have a nonzero amount of c->b or b->c left over (whichever works with our current query) to make c->b->a or b->c->a, respectively. However, if we encounter a c->a or b->a later, respectively, we will want to use that instead. As such, whenever we do a c->b->a or b->c->a, we will store it to query later when we run into a c->a or b->a, swapping them out if it would be optimal. If we do swap them out, we can use the now-available b->a or c->a to modify a later character.

Due to the nature of this problem, we can implement regret greedy by using queues instead of heaps for O(N) overhead instead of O(NlogN) overhead.

After finishing, we use up as many remaining c->b as possible. This can be seen to be optimal.

Overall, this solution is O(N+N+N+Q) = O(N+Q), improving upon the O((N+Q)logQ) solution in the editorial. Please tell me if you have any questions or concerns regarding my code.

In problem F how can I get the ratio? I dont understand

I misread problem D by a big margin, I thought that its asked to maximize the minimum no of moves between the floors among all groups and didn't realize until after the contest. I wonder how this version would be solved ?

There is another idea for problem F. It can be solved using Pick's rule for an area of a figure without any holes in it.

So basically Area = inner + border/2 — 1 (inner is a number of integer points strictly inside a figure, border — a number of integer points on the border of a figure). In our case perimeter = border. And also we can observe that in our case 'border' >= 4 and 'border' is also even, which can be quite easily proved.

And with this we can rewrite the formula with the ratio and express 'inner' in terms of 'border'. After this we iterate over 'border', find its 'inner' if it's a positive integer.

And all that's left is to create a construction to build a component (without any holes) with such area and perimeter. I'm sure there are other constructions, but i was able to come up with a not that hard one.

So imagine a 90 degrees angle with sides of width 1 (inner = 0), and we can observe that if we add one piece which will have two adjacent pieces that we already added before, the number of inner points will increase by one, but the number of border points will be the same. And the maximum number of inner points that we can get in such way equals to the (a — 1) * (b — 1), where a, b — sides of the initial angle. And so we want to find such {a, b} with maximum product, and we can find them using formula for 'border', which did not change after the creation of an angle( border = a * 2 + b * 2 ).

Submission

Wow glad that you posted solution 2 in G. That's what I came up with

A with bitmask $$$O(logn)$$$

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<complex>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll mrt=3;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
 
ll msb(ll x){forr(i,30,0) if(x&(1<<i)) return i+1; return -1;}
void solve(istream &cin){
	ll x;
	cin>>x;
	cout << 2*msb(x)+1 << '\n';
}
 
int main()
{
    fast_io;
    ll testcase;
    cin>>testcase;
    // testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

Actually i found something interesting,the key of problem A can be think alternative which is the most significant bit cannot exceed more than 1,for example $$$3=0011_2$$$ and $$$0=0000_2$$$ so if the most significant bit of two number more than 1,then you can't make the smaller one larger than the bigger number otherwise we can just let the smaller number be bigger number right shift 1 position in binary representation.

The problems are extremely hard((

why in task G, in 8th test, in 9th query, the answer is YES?

You can solve G in $$$O(N\log(N)+Q)$$$.

This solution's goal is to construct a binary-jumping structure as follows:

• $$$BL[i][j]$$$ represents the best possible $$$r$$$ given the left of the range starts at $$$i$$$ and the size is at least $$$2^j$$$.
• $$$BR[i][j]$$$ represents the best possible $$$l$$$ given the right of the range starts at $$$i$$$ and the size is at least $$$2^j$$$.

If we have both $$$BL$$$ and $$$BR$$$, the answer to any query is true whenever $$$BL[l][o] \geq r$$$ or $$$BR[r][o] \leq l$$$ where $$$o=\lfloor \log_2(r-l+1) \rfloor$$$. For any $$$(L, M, R)$$$ (defined same as editorial) that is a valid solution for $$$l$$$, $$$r$$$, at least one of the ranges covered by $$$BR$$$ and $$$BL$$$ will fully cover $$$[M-1,M]$$$ and therefore that solution will be included.

To note is that normal construction of binary-jumping structures does not apply to this problem. For the next part I will show only how to construct $$$BL$$$ because $$$BR$$$ is built the same when the original permutation is reversed. Instead, for every $$$(L, M, R)$$$ pair we wish to do the following:

• Push $$$R$$$ onto the range $$$BL[\max(L,M-2^j+1)...M-1][j]$$$ for all $$$j \gt 0$$$ s.t. $$$L \lt M-2^{j-1}+1$$$.

I'm sure there are many ways to do this quickly. This is what I did:

1. For each $$$(L,M,R)$$$, push $$$R$$$ onto $$$BL[\max(L,M-2^j+1)][j]$$$ for all $$$j \gt 0$$$ s.t. $$$L \lt M-2^{j-1}+1$$$.
2. Use a monotonic deque to convert $$$BL[i][j]=\max(BL[i-2^{j-1}+1...i][j])$$$
3. Set $$$BL[i][j] = \max(BL[i][j], BL[i][j-1])$$$, working from low to high with $$$j$$$.

Lmk if anyone needs clarification. Here's my submission for reference: 323347704

I would like to share my approach to F. First we divide both p and s by GCD(p, s). Big thing I noticed is that it must hold 4 * sqrt(S) <= P <= 2 * S + 2 (you can get this by looking at biggest possible P / S, which is straight line and smallest possible, which is a square). From here you can manually solve the cases P = 2 * S + 2 (straight line) and P = 2 * S + 1 (just look at 2 * p / 2 * s, and you get P = 2 * S + 2 again). For P <= 2 * S, no matter which p * k / s * k you take, second part will always hold true. So now we only need to satisfy the first part of the inequality. We need to find smallest k such that 4 * sqrt(k*S) <= 4 * P, so k >= 16 * S / P^2 (note that this k may not be the ideal one because we took assumption that we can take sqrt(S) freely, so we need to check tighter constraint and possibly increase k by a little). Tighter constraint is if S = a^2 + b, b < 2 * a + 1 1) b = 0, O >= 4 * a 2) b < a, O >= 4 * a + 2 3) else, O >= 4 * a + 4 We increase k by 1 until this tighter constraint holds, and possibly by 1 more if P * k is odd (P must be an even number). Now we have p = p * k, s = s * k. After this, we first create a line of P squares, which will have S2 = 2 * P + 2 and start creating a square of size floor(sqrt(P)). Notice that by moving a piece from the line to the square, S stays the same and P2 reduces by 2 when we move the piece to touch 2 parts of the square. So we do this until P2 = P (on the very end, if we create the whole square and it still doesn't hold true, we can start creating square with a side 1 bigger until it holds true)

problem A — O(1):

ans = ceil(log2(n + 1)) * 2 + 1

F can be solved with Pick's theorem

(Area) S = i + b / 2 — 1. (Perimeter) P = b. Where i is number of points inside figure and b is number of points on the border. s / p = (i + b / 2 — 1) / b i * p + p * (b / 2) — p = b * s. Lets make t = b / 2 new variable i * p + t * (p — 2 * s) = p. That is out diophantine equation to solve. Lets solve it, make sure i >= 0, t >= 1. How do we construct an answer? It i == 0 then we can just output a line. If i > 0, i suggest doing greedy. Lets build rectangle with sides maximizing the area, but maintaining its perimeter to be 2 * t. Then if i > (side1 — 1) * (side2 — 1) then we won't be able to fit the needed number of points inside. Otherwise we are fine, can construct the answer like two sides of rectangle to get needed perimeter and then fill the inside area to get needed area.

In order to be sure, that answer does not exist in case where we cannot fit it inside we must greedely maximize the sides. That's some ifs with coefficient gained from diophantine equation. This solution requires at most 40100 squares for case p / s == 1/ 50.

324262068

$$$O((n + q) \log^2{n})$$$ solutions for G can be made to fit within the TL: 326467958

the answer of A is (int)__lg(n)*2+3

Damn! I can't understand the meaning of question A.