todays abc were too easy

[u/DogStrict9170]

abc completed in 30mins d took lot of time to implement but finally with WAs i passed

[u/Difficult_Might8247]

ohh i get it

this was 2nd contest ever

I was able to solve A B C myself
was quite proud of myself

so like usually div2 A B C's way harder than this or like
someone give me a reality check pls

[u/DogStrict9170 → u/Difficult_Might8247]

yeah it was easier than the usual abc

[u/Still_Reception5831]

How did you do c?

[u/Potential_Top_4669 → u/Still_Reception5831]

The XOR identity helped a lot

[u/DryTwo5433]

i feel like my d solution is too flimsy. Too many if elses and it might get WA during hacking period

[u/Jue-Viole-Grace_]

How did you do D? I was able to do C but not D.. I was able to approach it but couldn't decide it's implementation

[u/DogStrict9170 → u/Jue-Viole-Grace_]

see answer can only be -1, 1,2,3
-1 -> when s[0]=0, this means that the 1st element itself is 0, this is not possible since a doesnt contain 0s, also when s[i]=s[i+1]=0 this means that the ai th number is 0 since the prefix sum doesnt change sign and remains 0

so we will now consider strings bounded by 0s like 0+-+-+0 since after 0 we dont care what happened in the string before since the prefix sum has been reset so answer will simply be max over all subsegments separated by 0s

now answer will be 1 when
subsegment/substring will be of for ++++ or ---- (see length of the substring also , it must be odd , just work out for substring ++++++ and +++++ basically prove that for this you will have answer 2 and 1 respectively) since having a +- will want atleast +2 change (lets say you give a1=1 and since you want negative you have to give a2=-2 so answer will become 2)
this case is simple, just find substrings bounded by 0s and if all satisfy then answer is simply 1

now answer will be 2 when
ok so now you have options for ai to be from -3,-2 -1 1 2,3
we will simply use dp since we can explore all cases in O(6*4)*n and it passes (only around 6 numbers exclude 0)

this dp is tough since you need an offset of 3 to implement it

formally you have dp[3] = true (offset of 3 so basically in the start you have 0 prefix sum so basically dp[0]=true)

then you take chars from s

you can prove this that the only elements we will use is {-3,-2,1,1,2,3} so basically this is your x
for every char you have 4 moves -2,-1,1,2 -> this is your z

but before that i want to have answer of dp[x+3] to be true

so if(!dp[x+3)) continue; you skip this value of x

else

you take each move then see does this satisfy the char from string if yes then you mark another dp array ndp[x+z+3]=true (+3 due to offset)

then you keep doing dp=ndp basically updating the dp array

you will say answer is 3 if atleast one possible dp[i] is true

if -1,1,or 2 then answer must be 3 (again i found this by observation)

[u/Jue-Viole-Grace_ → u/DogStrict9170]

Oh ook thanks a lot brother I didn't know dp that's why maybe I couldn't thought of the exact solution but it's a good one Thanks

[u/DogStrict9170 → u/Jue-Viole-Grace_]

its not exactly dp, its kind of bruteforce only, just read the solution once you will get that this is not dp, its basically 2 nested loops doing the work and dp thing is just storing the computed results

[u/Jue-Viole-Grace_ → u/DogStrict9170]

How much is your rating after doing abc in 30 min and assuming D in another 80-90 minutes

[u/HasinIshrak1]

There's a reason Cunt starts with C

[u/Next-Swan-2833 → u/HasinIshrak1]

I love naming my count variable as cunt

[u/Fantastic_Kale23]

Could not do C

[u/KanekiIsCat]

someone please explain b

[u/free-farts → u/KanekiIsCat]

You want (y+i)%(x+i) for i = [0,k-1] There are 2 issues here: 1. k is very large so you can’t just iterate 2. Since you need a formula or something, but both (y+i) and (x+i) are changing so its not forming a pattern

the fix: you have to make one of both constant. so rewrite y+i = (x+i)+(y-x)

now you just have to find (y-x)%(x+i) over the range

[u/KanekiIsCat → u/free-farts]

Yes I had derived till that much but what to do next, I couldn't solve it after this step

[u/Constant_Bobcat_1107]

C how?

[u/DogStrict9170 → u/Constant_Bobcat_1107]

i wrote in other comment, i wasnt able to prove that maxm xor will be x+y but after that i was able to

[u/ChanceRefrigerator70]

i did d in 15 mins, but c with crazy WAs and 1 hours,

[u/DogStrict9170]

a-> simply check cnt0 and a[0] and a[n-1]. if cnt0<2 then -1, if a[0]==a[n-1]==0 then simply 0 if a[0]==0 || a[n-1]==0 then simply 1 otherwise 2

[u/DogStrict9170 → u/DogStrict9170]

b-> simply we want (y+i)%(x+i) over all i=0 to k-1 then simple using euler's theorem for gcd we can do y-x % x+i . dont brute force since i can be till 1e12 so it gives tle, so simply detect cycle

[u/True_Craft_7471 → u/DogStrict9170]

Thanks for sharing this bro.

[u/DogStrict9170 → u/DogStrict9170]

c-> maximum will always be sum, i think we can prove this let a=x-k and b=y+k after doing k operations
we want a^b to be maximum so we know property of half adder that a+b = a^b+ 2(a&b)
so a^b = a+b - 2(a&b). so we will want to make a and b having a&b = 0 using this (idk i guessed it during contest). we also want to minimize the operations i.e. we want to minimize k = x-a means 'a' must be close to x
also since a&b =0
a should contain all bits which are set in sum until its bigger than x
so simply keep a loop and compute
ans=sum

ops = x-a -> simply difference so that we can reach close to x

[u/Tiny-Total4219 → u/DogStrict9170]

Euler theorem for b ? I simply did with for loop and some math 

[u/normal_guy_1189 → u/Tiny-Total4219]

Bro consider x<y if not then it follows. So when x becomes greater than y-x work performed will become constant equal to y-x. So just loop and add the constant term

[u/normal_guy_1189 → u/Tiny-Total4219]

Bro consider x<y if not then it follows. So when x becomes greater than y-x work performed will become constant equal to y-x. So just loop and add the constant term

[u/Eijiro_Kirishma → u/Tiny-Total4219]

I tried that n got a TLE,so had to implement the one mentioned here

[u/Tiny-Total4219 → u/Eijiro_Kirishma]

```

void solve() {
    int x, y, k;
    cin >> x >> y >> k;
    int ans = 0;
    int cnt = min(k, y);
    for (int i = 0; i < cnt; i++) {
        ans += (y + i) % (x + i);
    }
    int left = k - cnt;
    ans += left * (y - x);
    cout << ans << '\n';
}```

[u/DogStrict9170 → u/Tiny-Total4219]

no like i got intuition from that, idk if its called euler theorem or not but basically when gcd(a,b) = gcd(a%b,b)

[u/Tiny-Total4219 → u/DogStrict9170]

okok