→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:15:24
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя kostka

Google Kick Start 2020 — round G

Автор kostka, 4 года назад, По-английски

Round G of Google Kick Start 2020 will start this Sunday (October 18) at 12:00 UTC and will last 3 hours.

See you at g.co/kickstart.

google, google kick start

kostka
4 года назад
72

Комментарии (57)

Показать архивные | Написать комментарий?

wicardobeth

4 года назад, # |

Anyone else facing long queues?

→ Ответить

pranshukas

4 года назад, # ^ |

← Rev. 2 →

Yes, I too faced long Queues especially in Question 3.

→ Ответить

tautology

4 года назад, # |

How to solve C

→ Ответить

dush1729

4 года назад, # ^ |

← Rev. 2 →

sort the array and append the whole array with value a[i] + n.
For each window w, find the moves required to make all values equal to median which is basically Sliding Cost on CSES. You can see discussion here

Code

→ Ответить

tautology

4 года назад, # ^ |

Can you share your submission?

→ Ответить

dush1729

4 года назад, # ^ |

You can view my submissions here.

→ Ответить

VandanRogheliya

4 года назад, # ^ |

Can you explain the idea behind these lines of code in your solution?

d=d+abs(m-a[i])-abs(old_m-a[i-k]);
if(k%2==0) d-=(m-old_m);

→ Ответить

NikolPashinyan

4 года назад, # ^ |

← Rev. 2 →

Ternary search on the target node worked for me.

→ Ответить

zeddie

4 года назад, # ^ |

I don't understand, can you explain?

→ Ответить

NikolPashinyan

4 года назад, # ^ |

Sure. If the problem is with ternary search then look at https://www.geeksforgeeks.org/ternary-search/

The random heuristic that I use is repeating the search several times on different intervals and choose the best one. This is the solution https://pastebin.pl/view/bfb7d20d

→ Ответить

175iq

4 года назад, # ^ |

Why do you need to use heuristic with ternary search ?

→ Ответить

Tru3R00T

4 года назад, # ^ |

I used binary search in the following manner
Let the array be 1 2 3 4 5 6 7 8 9 10 11 12 13 14 then calculate prefix sums, for each i [1,14] we calculate two index, index1 = the point where each element before will be wrapped around using Subtraction, index2 = from where it would be wrapped around from addition
eg i=9 index1=2, so all elements before this will be wrapped using Subtraction. And from 2-> 9 all element just add.
similarly index2.
index1 and 2 can be calculated using binary search, and then you can use prefix sums and array values to get the answer

→ Ответить

NikolPashinyan

4 года назад, # |

My main interests are problem C (Combination Lock) and D (Merge Cards).

Did anybody solve C without using ternary search on the final target? I am sure there is a solution avoiding ternary/binary searches.
In problem D after some standard thinking it's fairly possible to come up with an n^2 approach. Is it possible to solve the problem faster maybe O(nlogn) or even O(n)?

P.S. Since the main goal of Kickstart round is to contribute to recruiting at Google, what do you think how much is the ranking threshold this time to be contacted by Google requiter? What do you think about that magic number?

→ Ответить

175iq

4 года назад, # ^ |

← Rev. 2 →

Does ternary search work in problem C ? How is the function unimodal ? I kept on getting WA using ternary search.

→ Ответить

NikolPashinyan

4 года назад, # ^ |

I also didn't manage to prove the unimodality. That was just an assumption + some random heuristic that worked.

→ Ответить

175iq

4 года назад, # ^ |

Can you please see why my ternary search solution gave WA ?

Spoiler

#include <bits/stdc++.h>
using namespace std;
        
//Utility functions
#define pb push_back
#define sz size()
#define fi first
#define se second
#define all(c) (c).begin(),(c).end() 
 
//Constants
#define EPS 1e-6
#define INF 2e9
 
//Printing
#define coutRV(a,L,R) FE(i,L,R) cout<<a[i]<<" \n"[i==R] ;
#define coutV(a) coutRV(a,1,a.size()-1)
 
//For loops
#define FE(i,a,b)  for(int i=a; i<=b; i++)
#define FRE(i,b,a) for(int i=b; i>=a; i--)
#define FA(x,cont) for(auto& x : cont)
 
//For debug 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
//Definitions 
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vd vector<double> 
#define vvi vector<vector<int> > //For UnGraph
#define vvpi vector<vector<pii> > //For DirGraph
#define vviwv(vecname, N, M, value) vector<vector<int> > vecname(N, vector<int> (M, value)) //For DP
#define vvlwv(vecname, N, M, value) vector<vector<ll> > vecname(N, vector<ll> (M, value)) //For DP  
#define pii pair<int,int>   
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
//Input 
#define cini(i) int i; cin>>i;
#define cini2(i,j) int i,j; cin>>i>>j;
#define cini3(i,j,k) int i,j,k; cin>>i>>j>>k;
#define cini4(i,j,k,l) int i,j,k,l; cin>>i>>j>>k>>l;
#define cinll(l) ll l; cin>>l;
#define cind(d) double d; cin>>d;
#define cins(s) string s; cin>>s; s = "#"+s;
#define cinv(a, n) vi a(n+1); FE(i,1,n) { cin>>a[i]; }
#define cinvd(a, n) vd a(n+1); FE(i,1,n) { cin>>a[i]; }
#define cinvll(a, n) vll a(n+1); FE(i,1,n) { cin>>a[i]; }

void solve()
{
    ll w, n;
    cin>>w>>n;
    vll x(w,0);
    
    FE(i,0,w-1)
        cin>>x[i];

    function<ll(ll)> cost = [&](ll st)
    {
        ll moves = 0;
        FE(i, 0, w-1)
        {
            if(st > x[i])
            {
                moves += min(st-x[i], x[i]+n-st); 
            }
            else if(st < x[i])
            {   
                moves += min(x[i]-st, n-x[i]+st);
            }
        }
        return moves;        
    };

    ll l = 1, r = n;

    while(r-l>=3)
    {
        ll mid1 = l + (r-l)/3;
        ll mid2 = r - (r-l)/3;

        ll c1 = cost(mid1);
        ll c2 = cost(mid2);
        if( c1 < c2)
            r = mid2;
        else
            l = mid1;
    }
    if(l==r)
        cout<< cost(l)<<"\n";
    else if (l+1==r)
        cout<<min(cost(l), cost(r))<<"\n";
    else
        cout<<min(cost(l), min(cost(l+1), cost(l+2)))<<"\n";
    return;
}   

int main()
{
    fastIO;
    cini(t);
    FE(i,1,t)
    {
        cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}

→ Ответить

NikolPashinyan

4 года назад, # ^ |

The ternary search solution isn't correct. I just managed to get accepted because the tests were not strong enough.

Here is my solution link https://pastebin.pl/view/bfb7d20d with a random heuristic.

→ Ответить

rananjay23

4 года назад, # ^ |

← Rev. 2 →

Don't know about your solution but i think ternary search in following way will work .

1.Sort the array of weights (say "$$$w$$$"). 2.Traverse the array.For index $$$i$$$ , minimum cost for converting all other elements to $$$w[i]$$$ can be found by doing ternary search on the left of $$$i$$$ as well as on the right of $$$i$$$ . Leftmost element will try to move to $$$n$$$ and then to $$$n-1,n-2$$$ and finally to $$$w[i]$$$ . Example : suppose $$$n = 40$$$ and array after sorting is $$$2 , 3 , 33 , 35 ,37$$$ . Suppose we are converting to $$$35$$$ . Then for $$$2$$$ and $$$3$$$ it will best to move toward $$$40$$$ and then toward $$$35$$$ . Whereas for $$$33$$$ it can move directly toward $$$35$$$.Similar explanation for the right side of $$$i$$$.

→ Ответить

NikolPashinyan

4 года назад, # ^ |

I would welcome anyone to hack the solution.

→ Ответить

_dp95

4 года назад, # ^ |

+23

The function F(X) : Min. Moves to convert all elements to X is not unimodal. Consider the following test case :

15 15
11 13 12 3 2 8 13 6 6 11 7 7 1 1 8

The values of F(X) are

F(X) for X from 1 to 15

(1,59)
(2,58)
(3,59)
(4,60)
(5,58)
(6,53)
(7,50)
(8,51)
(9,54)
(10,54)
(11,52)
(12,53)
(13,56)
(14,61)
(15,62)

The graph looks like this :

→ Ответить

yash_daga

4 года назад, # ^ |

← Rev. 3 →

My solution for C:

First we will calculate number of moves required for turning every lock to 1 and also calculate the number of locks whose value is increasing and decreasing. For each lock there is atmost 3 critical numbers (number of the lock, numbers which are at n/2 distance) where the increasing or decreasing nature may change.

I inserted all critical points and sorted them and only checked the answer on the critical points.

→ Ответить

SkyDreams

4 года назад, # ^ |

← Rev. 5 →

I did it with checking answers for each value in array as a assumed target with some manipulations using prefix sums and two pointers on sorted array

My manipulations

auto make = [&](int i, int c1, int c2) {
      int ans = 0;
      ans += give(i, c1) - (c1 - i + 1) * a[i];
      ans += (n - 1 - c1) * (k + a[i]) - give(c1 + 1, n - 1);
      ans += (i - c2) * a[i] - give(c2, i - 1);
      ans += (c2) * (k - a[i]) + give(0, c2 - 1);
      return ans;
};

int mi = inf;
int p1 = 0, p2 = 0;
for (int i = 0; i < n; i++) {
      while (p1 < n and 2 * (a[p1] - a[i]) < k) p1++;
      while (p2 < i and 2 * (a[i] - a[p2]) >= k) p2++;
      int ans = make(i, p1 - 1, p2);
      mi = min(ans, mi);
}
Give is just prefix sum of that range

→ Ответить

johnwick2b67

4 года назад, # ^ |

← Rev. 3 →

I did it using the sliding median(sliding cost on the array of size $$$2 \times W$$$).

Sort $$$X$$$ and consider array $$$A$$$ of size $$$2 \times W $$$ where first $$$W$$$ elements are $$$X_i$$$, and last $$$W$$$ elements are $$$N + X_i$$$. Then it reduces to finding minimum cost in CSES — Sliding Cost with $$$k = W$$$ and $$$n = 2 \times W$$$.

→ Ответить

AmarShukla

4 года назад, # ^ |

why are we pushing w elements of n+x_i?

→ Ответить

johnwick2b67

4 года назад, # ^ |

← Rev. 5 →

Since our cost function is $$$\sum{\min(|x - X_i|, N - |x - X_i|)}$$$ and it can be observed that $$$x \in X$$$.

UPD: I'm not sure about the correctness, but I had this intuition that adding $$$N$$$ will handle this part $$$N - |x - X_i|$$$ (like the usual doubling in circular problems).

→ Ответить

adityaRaj28

4 года назад, # ^ |

can you please provide the sliding median solution. I had the similar idea, but i needed some help

→ Ответить

johnwick2b67

4 года назад, # ^ |

https://pastebin.com/d0k58nuw

→ Ответить

vivek8420

4 года назад, # ^ |

← Rev. 2 →

problem C without ternary search. https://pastebin.com/eX0UPCSC

→ Ответить

Not-Afraid

4 года назад, # ^ |

i did it using binary search.
PS.: don't know ternary search and how it works

→ Ответить

pranshukas

4 года назад, # ^ |

Not-Afraid Hey, Can you Please share your Solution as well as approach. I too tried to implement using Binary Search but I failed to do so.

It would be helpful if you could share your Solution and your logic/some explanations.

Thanks !!

→ Ответить

Not-Afraid

4 года назад, # ^ |

Note: It would be very hard for me to explain every single bit of my solution but i will try to give a rough idea.
First let's sort the array.
If we want to calculate answer for some index $$$i$$$: then the given array splits into three parts:
[some_prefix] + [some contiguous subarray containing index i] + [some_suffx].
Note: Above three arrays do not intersect, their union is equal to given array and 1st & 3rd array might be empty.
And the idea is that all elements in 2nd array will be directly converted into $$$ai$$$.

for (val in 2nd array) answer += abs(val - a[i]);

and elements in 1st and 3rd array will be converted indirectly i.e. taking them to one end ($$$1$$$ or $$$N$$$ and then taking them to $$$ai$$$).
Now for some given $$$i$$$ you can calculate the starting and ending index of second array using binary search. The rest is just a bit of calculation using prefix sums.
PS: You can take a look at my code at your own risk, because i overkilled it and there is a 99% chance that it will be hard for someone else to understand the code.

→ Ответить

traviscott

4 года назад, # ^ |

I did it without using ternary search. My approach was calculating number of moves to convert all elements to each x[i] and taking the minimum. For doing so, I used upper bound, lower bound and prefix-sums. I'll describe in detail if someone needs it.

→ Ответить

hellomoto

4 года назад, # ^ |

← Rev. 3 →

O(w) solution

1)Just make an array of 2 * w size with the value from w to 2 * w — 1 is duplicated with extra n.

2)Now for each segment of size w find the ans assuming all elements of the segment will become equal to its median(you have to precalculate prefix sum to get sum of a segment).

3)get the max of all ans.

→ Ответить

HelloWorld

4 года назад, # |

How to solve D for full points?
I simply used brute force for 9 points. I thought of making a tree with its leaves representing the values on the cards and the root representing the answer(expected sum)

→ Ответить

Len

4 года назад, # ^ |

← Rev. 3 →

Overcomplicated solution, see Errichto's solution below.

→ Ответить

Errichto

4 года назад, # |

← Rev. 2 →

+44

Screencast with post-commentary and solutions, 2nd place: https://youtu.be/RpyWh424VCE (fast ABD, overcomplicated C with two pointers)

→ Ответить

sharath101

4 года назад, # ^ |

Your solution to D is soo amazing

→ Ответить

Mike_Mirzayanov_Is_Pussy

4 года назад, # |

what was difficulty level of question in terms of codeforces ratings.

→ Ответить

AM_I_Learning

4 года назад, # |

The random test file generated by me for debugging my C solution with 2 binary searches.

Tests

Answer

→ Ответить

Matiyau

4 года назад, # ^ |

Thank you for these tests!!! My solution was failing only for testcase 26 of yours , corrected it and my solution got accepted :P Btw how did you generate these test cases?

→ Ответить

AM_I_Learning

4 года назад, # ^ |

Just wrote these random generator in some minutes and then saved the output of this in a file.

generator

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl '\n'

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll t=100;
    cout<<t<<endl;
    while(t--)
    {
        ll n=rand()%10+1;
        ll m=rand()%10+1;
        cout<<n<<" "<<m<<endl;
        for(ll i=1;i<=n;i++){
            cout<<rand()%m +1<<" ";
        }
        cout<<endl;
    }
     return 0;
}

→ Ответить

kartik8800

4 года назад, # |

← Rev. 4 →

+14

My video editorial for the round: Google Kick Start Round G, 2020: Editorial
rough notes used: google doc notes

Proof for Problem 3, Set: 2
Initial wheel values(V) = {v1,v2,v3....vw}
Claim: it is always possible to get the optimal solution by only trying out the values v1,v2,v3...vw.
Assume that value x = p gives a better solution and p does not belong to V.

This means we bring all the wheels to the position p and cost is minimised on doing so.

We have the following scenario:
v1...v2... ... vi....p...v(i+1)... ...vw

Now all wheels will reach p by either moving forward or backward.

Let's say x1 wheels approach p from the left of it and x2 wheels approach p from the right of it.

If x1 < x2
We can obtain a better answer by shifting x=p to x=v(i+1)
On similar lines if x1 > x2 then move x to x= vi
If x1=x2
It would make no difference to the answer even if we move it to either vi or v(i+1)

Hence a better answer cannot be obtained at a value x = p such that p does not belong to V.

Let me know if this makes sense.

→ Ответить

akshatbhutra

4 года назад, # |

← Rev. 2 →

-6

Problem A:

My code:

~~~~~

code

include<bits/stdc++.h>

define ll long long

define pb push_back

define all(x) x.begin(), x.end()

define sz(x) (ll)(x.size())

define pll pair<ll, ll>

define vll vector

define INF (1ll << 60)

define ld long double

// #define tc ll tt; cin >> tt; while(tt--)

define MOD 10000007

using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(0); int tt = 1; cin >> tt; for (int tc = 1; tc <= tt; tc++) { string ss = "akshat"; cin >> ss; long long maxi = 0, ans = 0; int pos = 0; vector ki, st; while (1) { if (ss.find("KICK", pos) == string::npos) break; pos = ss.find("KICK", pos); ki.pb(pos); pos += 4; } pos = 0; while (1) { if (ss.find("START", pos) == string::npos) break; pos = ss.find("START", pos); st.pb(pos); pos += 5; } for (auto pp: ki) { for (auto qq: st) { if (qq > pp) ans++; } }

cout << "Case #" << tc << ": " << ans << '\n';
}

}

...

It was giving WA. Any idea? I could not figure it out.

→ Ответить

smitpatel1010

4 года назад, # ^ |

You should increase pos by 3 when checking string "KICK" because KICK string can overlap like "KICKICK" in this case you will skip the second string KICK

→ Ответить

akshatbhutra

4 года назад, # ^ |

Thank You very much for replying. Now I got it.

→ Ответить

smitpatel1010

4 года назад, # ^ |

← Rev. 2 →

btw your corrected code with pos+=3; should give TLE. but because of only 2 test sets google can't have 100 testcases with same string.

with below input your code will give TLE.

100 testcases with same strings of length 10^5. KICKSTARTKICKSTARTKICKSTART...(upto 10^5 length). your ki and st vectors will be of lengths (10^5)/9. so total time complexity of each test will be around 10^8. so total time will be 10^10. which will give TLE

→ Ответить

Errichto

4 года назад, # |

+56

The last problem (Merge Cards) can be solved in $$$O(N)$$$ instead of $$$O(N^2)$$$, and it's pretty simple.

There are $$$N-1$$$ possible bars (splits) between the $$$N$$$ elements, and the described process just removes bars in random order. When a bar is removed, the score increases by the sum of elements up to next existing bar on the left and on the right. We add element $$$a_i$$$ to the score when removing bar between positions $$$j$$$ and $$$j+1$$$ if and only if all bars between $$$i$$$ and $$$j$$$ were already removed (assume $$$i \leq j$$$). One bar is last among $$$j-i+1$$$ bars with probability $$$\frac{1}{j-i+1}$$$ so we increase the answer by $$$\frac{a_i}{j-i+1}$$$. Iterating all pairs $$$(i, j)$$$ is $$$O(N^2)$$$, and we get rid of iterating $$$j$$$ by precomputing harmonic sum $$$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \ldots$$$.

code (20 lines)

#include <bits/stdc++.h>
using namespace std;
int main() {
	int T;
	scanf("%d", &T);
	for(int test = 1; test <= T; ++test) {
		int n;
		scanf("%d", &n);
		vector<double> harmonic(n + 1);
		for(int i = 1; i <= n; ++i) {
			harmonic[i] = harmonic[i-1] + 1. / i;
		}
		double answer = 0;
		for(int i = 0; i < n; ++i) {
			int ai;
			scanf("%d", &ai);
			answer += ai * (harmonic[i] + harmonic[n-1-i]);
		}
		printf("Case #%d: %.10lf\n", test, answer);
	}
}

→ Ответить

DazeBoy

4 года назад, # ^ |

Since no one has answered this question above, I am asking you can you tell us what was difficulty level of problem C and D in terms of codeforces ratings?( this would help me in practice)

→ Ответить

Errichto

4 года назад, # ^ |

You can do the comparison yourself. Either by seeing how complicated topics and solutions are, or by seeing how many people solved it or how quickly people in the top got AC. Then tell us here what difficulty it is.

→ Ответить

DazeBoy

4 года назад, # ^ |

I was able to solve testset 1 and 2 for problem C but couldnt solve its testset 3, So I think testset 3 difficulty was somewhat around ummmmm.... ~1800(maybe)? And D ~2100? I dont know if its correct or not, Its been 2 months since I started CP thats why I wanted to ask form an experienced guy.

→ Ответить

nagaraj41

4 года назад, # ^ |

← Rev. 2 →

In Global round 11, C was solved by 1.3k people and it's rated 2000. So i think test case 3 of C deserves at least 2100+. In terms of difficulty as well i'd say.

→ Ответить

Tru3R00T

4 года назад, # ^ |

I solved testcase 3 of C, and i have full confidence in myself that i can't solve 2100+ rated problem in a contest.

→ Ответить

SkyDreams

4 года назад, # ^ |

Yea same here... Although i took abt an hour for c but did solve it.. It feels more like a 1700-1800 problem

→ Ответить

nagaraj41

4 года назад, # ^ |

← Rev. 2 →

I don't agree with that logic. Maybe you did it now for the first time, you never know. Edit: the problem rating on CF depend on the previous problem difficulty in the same contest so my comparison wasn't very accurate either.

→ Ответить

bits_goa_cc

4 года назад, # ^ |

← Rev. 2 →

I got the O(n^3) approach where we define 2 random variables X1, X2.

Where X1 is the sum accumulated by merging [L, I] to a single element

Where X2 is the sum accumulated by merging [I + 1, R] to a single element

So the answer would be a another random variable X = X1 + X2 + v[i] + v[i + 1]

By law of expectations : E[X] = E[X1] + E[X2] + v[i] + v[i + 1].

However I did not get why your approach works, can you share the rules/laws you used to get to the result.

→ Ответить

Errichto

4 года назад, # ^ |

I call it "contribution to the answer" but it's just linearity of expectation. Check out my old tutorial https://codeforces.net/blog/entry/62690

→ Ответить

Aloncf

4 года назад, # |

← Rev. 4 →

Problem C , Combination Lock — Please someone help :<<<
I know it's hard to debug someone else's code... But can someone please tell me what's wrong with my code? I get TLE (I'm guessing it has to be an infinite loop). I have a deque — at every iteration I have an element which is the current option for "median" — on the left of it all the elements that are N/2 at most away from the left, and to the right of it I have all the elements that are N/2 at most from the right.
i.e if there is the following sequence 1 1 1 6 6 7 8, the maximum number is 11, and the current option is 7, the deque will be arranged as such: 6 6 7 8 1 1 1.
I believe the problem in my code is an infinite loop in the "while(straight_dist(new_first, q[0],w) > dist(new_first, q[0],w))", but I'm not sure. In that loop I pop from the front and move to the back until all elements are ordered correctly as I explained.
I have no idea how it could run infinitely as eventually I will have to get to "new_first" and then dist == straight_dist == 0 must hold! please halpppp.

** Note — I switched N and W because only a maniak would make the number of elements w and the maximum number N.
*** Another explanation I forgot: The first FOR loop checks if there is a large gap between two elements, that means that you can simply find the median and You're done.

Code - only the relevant parts (not including main and all the macros)

ll dist(ll x,ll y,ll w){
	if(x > y) swap(x,y);
	return min<ll>(y-x, x+w-y);
}
ll straight_dist(ll x, ll y, ll w){
	if(x < y) return x + w - y;
	return x - y;
}
bool test_cases=1;
void solve(int test_case_num) {
	ll n,w; read(n,w);
	vll a(n); read(a);
	dbg(a);
	sort(all(a));
	ll max_dist = 0;
	FOR(n){
		if(dist(a[i],a[(i+1)%n],w) >= w/2){
			dbg("yoooo");
			vi b; b.reserve(n);
			b.pb(a[(i+1)%n]);
			for(int j = (i+2)%n; j!= (i+1)%n; j=(j+1)%n){
				b.pb(a[j]);
			}
			dbg(b);
			ll med = b[n/2];
			ll total = 0;
			FOR(n){
				total+=dist(b[i],med,w);
			}
			print("Case #" + to_string(test_case_num) + ":",total);
			return;
		}
	}
	int num_elems = sz(set<int>(all(a)));
	ll first = a[0];
	vi lasts;
	deque<ll> q;
	FOR(n){
		if(a[i] - first > dist(a[i],first,w)){
			lasts.pb(a[i]);
		} else {
			q.pb(a[i]);
		}
	}
	FOR(i,sz(lasts)-1, -1, -1){
		q.push_front(lasts[i]);
	}
	int index = 0;
	while(index < n && q[index] != first) index++;
	ll min_total= LLONG_MAX;
	ll total = 0;
	FOR(n){
		total+= dist(q[i], first, w);
	}
	umin(min_total,total);
	int iters = 0;
	int last_index = index;
	while(iters < num_elems-1){
		dbg(iters);
		ll index = last_index;
		// ll tmp = total;
		while(q[index] == first) index++;
		int num_right = n - index;
		int num_left = index;
		ll new_first = q[index];
		dbg("YO",q, new_first);
		ll diff = dist(first,new_first,w);
		while(straight_dist(new_first, q[0],w) > dist(new_first, q[0],w)){
			dbg(straight_dist(new_first, q[0],w) , dist(new_first, q[0],w));
			total-=dist(q[0],first, w);
			total+=dist(q[0],new_first, w);
			ll x = q[0];
			q.pb(x);
			q.pop_front();
			dbg(q);
			index--;
			num_left--;
		}
		dbg(total);
		dbg(num_left, diff, first, new_first, q, last_index, index);
		total += num_left * diff;
		total -= num_right * diff;
		umin(min_total, total);
		last_index = index;
		first = new_first;
		iters++;
	}

	// print(index);




	print("Case #" + to_string(test_case_num) + ":",min_total);

}

Full code if you want to try and submit:

#include <numeric>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
// #define lld long long double
#define ar array

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define vt vector
#define vi vector<int>
#define vll vector<long long>
#define vld vector<ld>
#define vs vector<string>
#define vvl vector<vector<long long>>
#define vvi vector<vector<int>>

using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
#define NUM 1000000007// 998244353 //  //
#define pb push_back
#define mp make_pair

#define pb push_back
#define fi first
#define se second

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

#define printcase(x) print("Case #" + to_string(test_case_num) + ":",x); return
#define printret(x) {print(x); return;}



template<class T> bool umin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
} 

ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
	while(lb<rb) {
		ll mb=(lb+rb)/2;
		f(mb)?rb=mb:lb=mb+1; 
	} 
	return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
	while(lb<rb) {
		ll mb=(lb+rb+1)/2;
		f(mb)?lb=mb:rb=mb-1; 
	} 
	return lb;
}

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(vt<A>& x) {
	EACH(a, x)
		read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
	EACH(a, x)
		read(a);
}

string to_string(char c) {
	return string(1, c);
}
string to_string(bool b) {
	return b?"true":"false";
}
string to_string(const char* s) {
	return string(s);
}
string to_string(string s) {
	return s;
}
string to_string(vt<bool> v) {
	string res;
	FOR(sz(v))
		res+=char('0'+v[i]);
	return res;
}

template<size_t S> string to_string(bitset<S> b) {
	string res;
	FOR(S)
		res+=char('0'+b[i]);
	return res;
}
template<class T> string to_string(T v) {
    bool f=1;
    string res;
    EACH(x, v) {
		if(!f)
			res+=' ';
		f=0;
		res+=to_string(x);
	}
    return res;
}

template<class A> void write(A x) {
	cout << to_string(x);
}
template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h);
	write(t...);
}
void print() {
	write("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h);
	if(sizeof...(t))
		write(' ');
	print(t...);
}

void DBG() {
	print("]");
}
template<class H, class... T> void DBG(H h, T... t) {
	write(to_string(h));
	if(sizeof...(t))
		write(", ");
	DBG(t...);
}
#ifdef _DEBUG
	#define dbg(...) write("LINE(", __LINE__, ") -> [" , #__VA_ARGS__ ,"]: ["); DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

template<class T> void offset(ll o, T& x) {
	x+=o;
}
template<class T> void offset(ll o, vt<T>& x) {
	EACH(a, x)
		offset(o, a);
}
template<class T, size_t S> void offset(ll o, ar<T, S>& x) {
	EACH(a, x)
		offset(o, a);
}

mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b) {
	return uniform_int_distribution<ll>(a, b)(mt_rng);
}

template<class T, class U> void vti(vt<T> &v, U x, size_t n) {
	v=vt<T>(n, x);
}
template<class T, class U> void vti(vt<T> &v, U x, size_t n, size_t m...) {
	v=vt<T>(n);
	EACH(a, v)
		vti(a, x, m);
}

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

#define VECTOR_MULT_ll(v) (accumulate(all((v)), (ll)1, multiplies<ll>()))

#define VECTOR_MULT_ll_i(v,i) (accumulate((v).begin(), (v).begin()+(i), (ll)1, multiplies<ll>()))


long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

long long mod_binpow(long long a, long long b, ll p) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%p;
        a = (a * a) %p;
        b >>= 1;
    }
    return res % p;
}

ll mod_inverse_prime(ll a, ll p){
	return mod_binpow(a,p-2,p) % p;
}

/* Modular inverse not for prime */
ll mod_inverse(ll a, ll b){
 return 1<a ? b - mod_inverse(b%a,a)*b/a : 1;
}

bool ok_indexes(int n,int m,int i,int j){
	return (i>= 0 && i < n && j >= 0 && j < m);
}
bool backtrack(vt<pair<int,int>>& a,int n, int m,int x,int y,int idx, vt<vt<bool>>& vis){
	// print(x+1,y+1);
	a[idx] = mp(x+1,y+1);
	// print(a[idx].fi);
	vis[x][y] = true;
	if (idx == n*m-1){
		return true;
	}
	int di,dj;
	FOR(4){
		tie(di,dj) = mp(d4i[i], d4j[i]);
		// print("yooo",x+di+1,y+dj+1);
		if (ok_indexes(n,m,x+di,y+dj) && !vis[x+di][y+dj]){
			bool good = backtrack(a,n,m,x+di,y+dj, idx+1,vis);
			if (good) return good;
		}
	}
	// print("yooooooooo");
	vis[x][y] = false;
	return false;

}


// vi bfs(int s){
// 	// int n = adj.size();

// 	queue<int> q;
// 	vector<bool> used(n);
// 	vector<int> d(n), p(n);

// 	q.push(s);
// 	used[s] = true;
// 	p[s] = -1;
// 	while (!q.empty()) {
// 	    int v = q.front();
// 	    q.pop();
// 	    for (int u : adj[v]) {
// 	        if (!used[u]) {
// 	            used[u] = true;
// 	            q.push(u);
// 	            d[u] = d[v] + 1;
// 	            p[u] = v;
// 	        }
// 	    }
// 	}
// 	return d;
// }




ll gcd (ll a, ll b) {
    return b ? gcd (b, a % b) : a;
}
ull gcd (ull a, ull b) {
    return b ? gcd (b, a % b) : a;
}
template <typename T>
T gcd_array (vt<T> & arr) 
{ 
	T n = arr.size();
	T result = arr[0]; 
	for (T i = 1; i < n; i++) 
	{ 
		result = gcd(arr[i], result); 
		if(result == 1) 
		{ 
		return 1; 
		} 
	} 
	return result; 
} 

template <typename T>
T gcd_set (set<T> & arr) 
{ 
	T n = arr.size();
	T result = *arr.begin();
	auto iter = next(arr.begin());
	while(iter != arr.end()){ 
		result = gcd(*iter, result); 
		if(result == 1){ 
			return 1; 
		} 
		iter++;
	} 
	return result; 
} 


ll longlog(ld base, ld x) {
    return (ll)(log(x) / log(base));
}
// int mxN = 10e3;
// int A[mxN][mxN], B[mxN][mxN];
// bool vis[mxN][mxN];
// char output[mxN][mxN];

// ll total = 0;
// void solve_rec(vll & a, ll n, ll spare =0, int start=0){
// 	if(start == n) return;
// 	if (a[start] > 0){
// 		spare+= 
// 	}
// 	solve_rec(a,n, spare + /***x***/, start+1);
// }
class Solution {
public:
   // map <int ,int > l;
   int best;
   int node;
   int dfs(int v, bool* visited, vvi& graph, int c = 0){
      visited[v] = true;
      int ans = 0;
      for(int i = 0; i < sz(graph[v]); i++){
         if(!visited[graph[v][i]])ans = max(ans,dfs(graph[v][i], visited, graph, c+1));
      }
      if(c > best){
         best = c;
         node = v ;
      }
      visited[v] = false;
      return max(c,ans);
   }
   int treeDiameter(vvi & graph, int n) {
      bool* visited = new bool[n]();
      best = 0;
      node = 0;
      dfs(0, visited, graph);
      bool* visited2 = new bool[n]();
      return dfs(node, visited2, graph);
   }
};

int dfs2(int v, int parent, int b, int dist, vvi &adj){
	// dbg(v,parent,b,dist);
	fflush(0);
	if(v == b) return dist;
	EACH(u,adj[v]){
		if (u == parent) continue;
		int res = dfs2(u,v,b,dist+1,adj);
		if(res != -1) return res;
	}
	return -1;
}





// int mxN = 3*10e5;
// int a[mxN];
// #define RIA int n; read(n); vi a(n); read(a);
// #define RLA ll n; read(n); vll a(n); read(a);
// vvi adj;
// vt<ull> a;
/*
	adj = vvi(n);
	FOR(n-1){
		int l,r; read(l,r);
		l--; r--;
		adj[l].pb(r);
		adj[r].pb(l);
	}
*/

int clz(int N) {
    return N ? 32 - __builtin_clz(N): -1;
}
int clz(unsigned long long N) {
    return N ? 64 - __builtin_clzll(N): -1;
}
bool is_peak(vll &a, ll i){
	ll n = a.size();
	dbg(n,i);
	if(i <= -1 or i >= n) return false;
	if(n == 1) return true;
	if(i == 0 && a[i] > a[i+1]) return true;
	if(i == n-1 && a[i] > a[i-1]) return true;
	if(a[i] > a[i-1] && a[i] > a[i+1]) return true;
	return false;
}
bool is_valley(vll &a, ll i){
	ll n = a.size();
	if(n==1) return false;
	if(i <= -1 or i >= n) return false;
	if(i == n-1 || i == 0) return false;
	if(a[i] < a[i-1] && a[i] < a[i+1]) return true;
	return false;
	
}
ll choose(vll &fact, ll n, ll k, ll p){
	if(n < 0) return 0;
	if(k > n) return 0;
	if(k==n) return 1;
	// dbg(n,k,p);
	return (fact[n]*mod_inverse_prime((fact[k]*fact[n-k])%p,p))%p;
}


ll dist(ll x,ll y,ll w){
	if(x > y) swap(x,y);
	return min<ll>(y-x, x+w-y);
}
ll straight_dist(ll x, ll y, ll w){
	if(x < y) return x + w - y;
	return x - y;
}
bool test_cases=1;
void solve(int test_case_num) {
	ll n,w; read(n,w);
	vll a(n); read(a);
	dbg(a);
	sort(all(a));
	ll max_dist = 0;
	FOR(n){
		if(dist(a[i],a[(i+1)%n],w) >= w/2){
			dbg("yoooo");
			vi b; b.reserve(n);
			b.pb(a[(i+1)%n]);
			for(int j = (i+2)%n; j!= (i+1)%n; j=(j+1)%n){
				b.pb(a[j]);
			}
			dbg(b);
			ll med = b[n/2];
			ll total = 0;
			FOR(n){
				total+=dist(b[i],med,w);
			}
			print("Case #" + to_string(test_case_num) + ":",total);
			return;
		}
	}
	int num_elems = sz(set<int>(all(a)));
	ll first = a[0];
	vi lasts;
	deque<ll> q;
	FOR(n){
		if(a[i] - first > dist(a[i],first,w)){
			lasts.pb(a[i]);
		} else {
			q.pb(a[i]);
		}
	}
	FOR(i,sz(lasts)-1, -1, -1){
		q.push_front(lasts[i]);
	}
	int index = 0;
	while(index < n && q[index] != first) index++;
	ll min_total= LLONG_MAX;
	ll total = 0;
	FOR(n){
		total+= dist(q[i], first, w);
	}
	umin(min_total,total);
	int iters = 0;
	int last_index = index;
	while(iters < num_elems-1){
		dbg(iters);
		ll index = last_index;
		// ll tmp = total;
		while(q[index] == first) index++;
		int num_right = n - index;
		int num_left = index;
		ll new_first = q[index];
		dbg("YO",q, new_first);
		ll diff = dist(first,new_first,w);
		while(straight_dist(new_first, q[0],w) > dist(new_first, q[0],w)){
			dbg(straight_dist(new_first, q[0],w) , dist(new_first, q[0],w));
			total-=dist(q[0],first, w);
			total+=dist(q[0],new_first, w);
			ll x = q[0];
			q.pb(x);
			q.pop_front();
			dbg(q);
			index--;
			num_left--;
		}
		dbg(total);
		dbg(num_left, diff, first, new_first, q, last_index, index);
		total += num_left * diff;
		total -= num_right * diff;
		umin(min_total, total);
		last_index = index;
		first = new_first;
		iters++;
	}

	// print(index);




	print("Case #" + to_string(test_case_num) + ":",min_total);

}


int main() {
	bool real = true;
	#ifdef _DEBUG
		real = false;
		freopen("q1.input", "r", stdin);
	#endif
	if(real){
		ios::sync_with_stdio(0);
		cin.tie(0);
	}
	int t = 1;
	if(test_cases) read(t);
	FOR(t){
		// print("Case #" + to_string(t) + ":",res); THIS GOES IN solve()
		solve(i+1);
	}

	return 0;
}

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.11.2024 12:19:36 (l1).

Десктопная версия, переключиться на мобильную.

При поддержке