Codeforces Round 1026 (Div. 2)

11 месяцев назад, скрыть # ^ |

0

do you mean it is a standard ( or known ) problem ?

→ Ответить

»

SYCu

11 месяцев назад, скрыть # ^ |

+1

yes

→ Ответить

»

11 месяцев назад, скрыть # ^ |

0

can you please tell me about this . I used some kind of DP based on what is the minimum charge required if I start at some suffix of the array..

but I will be happy to know if the standard way

→ Ответить

»

jakeob

11 месяцев назад, скрыть # ^ |

0

Binary search with dp and topological sort. Too bad i was not able to debug it quick enough

→ Ответить

»

11 месяцев назад, скрыть # ^ |

0

ok thanks for sharing this..

I also used binary search .. I will try to read editorial to understand more.

→ Ответить

»

11 месяцев назад, скрыть # ^ |

0

You don't need to use topological sort, simple DP works as $$$s_i \lt t_i$$$. So we can just iterate the vertices from $$$1$$$ to $$$n$$$ to update dp.

→ Ответить

»

jakeob

11 месяцев назад, скрыть # ^ |

0

Oh that would save some time. Thanks

→ Ответить

»

fafnir

11 месяцев назад, скрыть # ^ |

0

Why do we actually need to iterate from 1 to n and not just have a single BFS from 1? I think, I'm missing something on this problem (Node 1 BFS gives WA 6801 in TC 2; would be really interested in some failing testcase).

→ Ответить

»

itsraajjjuuuu

11 месяцев назад, скрыть # ^ |

0

there is problem called Maximize The root something , for me this problem was similar to that one of the reason it quickly led me to BS solution

→ Ответить

»

Saivishwas

11 месяцев назад, скрыть # |

0

for the first time i did Answer construction on a greedy problem.

→ Ответить

»

Vidush.rk11

11 месяцев назад, скрыть # |

0

I could not solve C :( . Let's see how much rating goes down

→ Ответить

»

Akash_123

11 месяцев назад, скрыть # ^ |

0

same

→ Ответить

»

osource

11 месяцев назад, скрыть # |

0

I hate C. How hard was it to find the d values :(

→ Ответить

»

dimastrakhal

11 месяцев назад, скрыть # |

← Rev. 2 →

0

Why is it failed system tests on A for everyone? UPD: It's OK now

→ Ответить

»

mychecksdead

11 месяцев назад, скрыть # |

+30

Problem F was very nice imo.

→ Ответить

»

AlexArdelean

11 месяцев назад, скрыть # ^ |

0

hint?

→ Ответить

»

mychecksdead

11 месяцев назад, скрыть # ^ |

0

Try to do observations a few observations about f(x, y).

→ Ответить

»

11 месяцев назад, скрыть # |

0

I enjoyed problems C and D .. I found them challenging and I was a little slow in solving these problems ..

also very happy to not make a silly WA submission for problem B .. lolzzz

Thanks for the nice problems..

→ Ответить

»

ckxian

11 месяцев назад, скрыть # ^ |

0

wtf was c? i tried maitaining a queue, set all -1s to 0 initially and when its required to flip the 0s to 1s (h curr < l[i]), then i pop the indices in my queue and set them to 1. ig the only problem here is that when i set the values to 1, the range between [popped index, current i]'s h values will all increase by 1, which may cause it to cross r[i], which could be probably be checked by tracking each h[i]'s, and then applying the +1 to this range using that weird prefix sum trick. but i was too lazy to do that but anyway, is there any other approach? soo many people solved c idk how is it a standard problem ?

→ Ответить

»

11 месяцев назад, скрыть # ^ |

0

oh so I did exactly same kind of thing.. but I did one extra round in the end to check if all the h[i]s are still in l to r range.. that passed protests for me.

→ Ответить

»

AaravSin

11 месяцев назад, скрыть # ^ |

0

I did it slightly differently, firstly i changed the original li,ri array, by decreasing each entry by number of 1s appeared before them, if at any place r1 went below 0 that was an obvious -1 as ans. then i created a suffix array where each entry was min of ri's appearing from i to nth pos. this gave me an idea on when i encountered d=-1 while traversing from left to right if curr height is less than the value at i pos in suffix array, then I can make d=1 otherwise make d=0. if ant any pos our curr height isnt b/w the given li ri, then report ans as -1

→ Ответить

»

11 месяцев назад, скрыть # ^ |

← Rev. 2 →

0

ok so you kind of saved that last check by changing l and r values before hand.. interesting. thanks for sharing this approach

→ Ответить

»

ckxian

11 месяцев назад, скрыть # ^ |

0

i guess im just lazy lol

→ Ответить

»

https://mirror.codeforces.com/contest/508/problem/D

11 месяцев назад, скрыть # ^ |

0

no no !! .. I also found it very tricky and solved it after 1 wrong submission and very late as well :( .. but I will still pray for >0 delta

→ Ответить

»

Abito

11 месяцев назад, скрыть # |

-21

E is cool. I couldn't code it in time, but I think it's cool.

→ Ответить

»

Edu175

11 месяцев назад, скрыть # |

+19

Problem E appeared in last year's TAP (Argentinian Programming Tournament) Problem

→ Ответить

»

fisher199

11 месяцев назад, скрыть # ^ |

0

I think this seems a bit more similar.

→ Ответить

»

oooomar

11 месяцев назад, скрыть # |

← Rev. 8 →

+4

hello, i found a hack testcase for my solution on problem D, but i couldn't figure out how to hack my own solution, any help on how to hack it?

edit: the incorrect solution still passes main tests.

edit2:

generator code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int mod = 1000000007, N = 200005;


int main(){
cin.tie(0)->sync_with_stdio(0);
    cout<<1<<'\n';
    int n = 200000, m = 300000;
    cout<<n<<' '<<m<<'\n';
    for(int i = 1; i <= n; i++){
        cout<<1<<' ';
    }
    cout<<'\n';
    for(int i = 1; i < n; i++){
        cout<<i<<' '<<i + 1<<' '<<1<<'\n';
    }

    for(int i = n; i <= m; i++){
        cout<<i - n + 1<<' '<<i - n + 3<<' '<<1<<'\n';
    }
}

→ Ответить

»

Austin4.5

11 месяцев назад, скрыть # |

+3

Problem E was interesting, but I didn't learn how to find Euler path :(

→ Ответить

»

MomentumLocked

11 месяцев назад, скрыть # |

0

Can someone tell me why my solution of problem D fails?

I used Binary Search + Dijsktra

→ Ответить

»

XMAN12321

11 месяцев назад, скрыть # ^ |

0

Use long long , also upper bound of bs is atleast sum of weights

→ Ответить

»

MomentumLocked

11 месяцев назад, скрыть # ^ |

0

I'd be so disappointed if that was the case :(

→ Ответить

»

wizzerinus

11 месяцев назад, скрыть # ^ |

+2

That's actually wrong, the upper bound is not sum of weights, it's the maximum weight of a path (so 1e9 + C works). Though, Dijkstra is on the critical performance line and would probably not pass. You should use DFS since you have a DAG.

Looking at the solution I don't see any blatant mistakes, though i didn't check that dijkstra and bs are written correctly but I assume they are

→ Ответить

»

wizzerinus

11 месяцев назад, скрыть # ^ |

← Rev. 2 →

+1

Ah, yeah, I think I've figured it out.

In each check(), you want to find not the shortest, but the longest path. Otherwise, you risk being in a situation where you've already skipped a node but could not go through a certain edge as it costs more batteries than you've already gained. Dijkstra can't find longest paths.

Example test case: 1 6 6 3 1 2 10 0 0 1 2 1 1 3 2 2 4 1 3 5 1 4 5 4 5 6 13

In this case, the correct path is to go 1 -> 2 -> 4 -> 5 -> 6 because you need to pick up the 10 batteries at point 4, but your algorithm only considers 1 -> 3 -> 5 -> 6 because of the ordering. Hence, your answer is -1 and the correct answer is 13.

→ Ответить

»

11 месяцев назад, скрыть # |

+69

I found F very satisfying to solve. When I first saw it, I thought there was a good chance it would end up being bashy and/or involving lots of technical details, so I was pleasantly surprised to find that it just involved a couple of nice observations. Thanks for the round!

→ Ответить

»

Thanos_I_am_inevitable

11 месяцев назад, скрыть # |

+6

Nice contest, no ambiguous statement like other contests..Thank you..

→ Ответить

»

un_kind

11 месяцев назад, скрыть # |

← Rev. 2 →

0

good contest

→ Ответить

»

seeker2310

11 месяцев назад, скрыть # ^ |

0

i tried the same method and got 2 wrong attempts, i somehow still dont get why this solution is wrong

→ Ответить

»

olezhkavayn

11 месяцев назад, скрыть # |

0

What is the solution to C?

→ Ответить

»

11 месяцев назад, скрыть # ^ |

+1

I went from left to right and kept adding the heights.. if I reach a -1 .. I assumed it to be zero and kept on moving . but I stored indices of all -1s visited till now in a stack like thing.. this stack will mean that in future I have some increment operations possible

so if in future I reach some situation where height > r then we fail because I only have increment operation and no way to go down.. but if height < l then I can pop from the stack and increase the zero at those places to 1 .. if stack gets empty before I can increase my height .. I fail

in the end I did one more pass to see that because I am doing increment behind the current index... all indices should still lie between l and r

→ Ответить

»

olezhkavayn

11 месяцев назад, скрыть # ^ |

0

https://mirror.codeforces.com/contest/2110/submission/321141722 can you help me understand why is this solution wrong?

seems to be pretty much the same

→ Ответить

»

11 месяцев назад, скрыть # ^ |

0

I am sorry I can't run python.. but this code


if d[i] != -1:
            h += d[i]
            if h < left[i] or h > right[i]:
                flag = False
                break

I think you are failing immediately when it is out of range.. is it not possible to change the value ( increase the value ) using some -1 previously

sorry If I am wrong.. I didn't read the whole code

→ Ответить

»

olezhkavayn

11 месяцев назад, скрыть # ^ |

0

this part of the code looks for situations when d[i] is already given

in this case i have nothing else but to add the d[i] and see if now i am out of range or not

→ Ответить

»

MaggiMonster

11 месяцев назад, скрыть # ^ |

+1

hey my approach is kinda similar to yours, im greedily converting a -1 to +1 if my current height after increasing doexnt exceed suffix min of R. https://mirror.codeforces.com/contest/2110/submission/321143380 this is my submission

→ Ответить

»

bcoskun

11 месяцев назад, скрыть # ^ |

0

I did exactly the same. Also the reason for stack is, you want to increment the height as late as possible always, starting from incrementing the last index of -1 and so on.

→ Ответить

»

11 месяцев назад, скрыть # ^ |

0

yeah I thought something similar like if I increment the nearest one.. it has less chance of messing something up .. ie causing some height to go above upper limit

→ Ответить

»

clipper21

11 месяцев назад, скрыть # ^ |

0

https://mirror.codeforces.com/contest/2110/submission/321149727 Can you help see why this is wrong too? I did the exact same thing, just different by using a suffix to check, and greedily increase the height to the max it could at the current point in time.

→ Ответить

»

akane646

11 месяцев назад, скрыть # ^ |

← Rev. 2 →

0

greedily pick all d[i] = 1 if a[i] == -1. (get an array to remember these position, let's called this array S)

If the current sums violate current right bound, use current S to reduce the sums (set those d[i] = 0)

Last check if all the li <= curr_sums <= ri

→ Ответить

»

3a51

11 месяцев назад, скрыть # |

← Rev. 2 →

0

Why my F solution 321144387 got WA on 3?

The idea is:

f(x,y) is always less(or equal) than 2*min(x,y) and max(x,y).

So if we have a pair of numbers (x,y) which satisfy min(x,y)*2>max(x,y), then f(x,y) will equal to max(x,y) and we can ignore all the numbers less than max(x,y).

Thus, we can maintain a set, which don't have a single pair satisfy min(x,y)*2>max(x,y) in it, and each time we add a new number x into it, check if there have a number satisfy the condition mentioned above.

We get answer from the max of two parts: the maximum max(x,y) which satisfy min(x,y)*2>max(x,y) and maximum f(new element, numbers in set).

It can be shown that the number of the elemnts in the set always less than $$$\log 10^9$$$.

Sorry for my bad english :(

→ Ответить

»

wuhudsm

11 месяцев назад, скрыть # |

0

My F solution:

Consider sorted $$$a$$$ (non-decreasing order), and remove duplicate numbers:

for each $$$a_i$$$:

if $$$a_i \lt 2a_{i-1}$$$, $$$\max(f(a_i,a[1,\ldots,i-1]))=a_i$$$, easy;
if $$$a_i \ge 2a_{i-1}$$$, bruteforce $$$O(logA)$$$ such numbers.

I think it's absolutely correct, but I don't know how to TLE in #8.

→ Ответить

»

11 месяцев назад, скрыть # ^ |

+5

I think your code brute forces every time there's a new maximum? If a[i] is the new highest number in the set, then it == S.end() will be true, and a[i] > lstans will also be true because the max number in the set so far is an upper bound on the answer.

I'm not sure what the purpose of the a[i] >= 2*(*it) condition is, since I think this will never be satisfied (because *it will always be at least a[i]). Maybe you meant to define it as the greatest number less than or equal to a[i] rather than the smallest number greater than or equal to a[i]?

You might realize this already, but it's worth noting that you only need to do the brute force step in cases where the new element you're adding is a new maximum (and is more than double the existing maximum). This is because we can prove that the best answer always includes the maximum element of the array. I'm not sure if handling this incorrectly actually worsens the time complexity (I think checking that the new element is greater than the last answer may be sufficient to achieve $$$n \log a_i$$$), but I think noticing this makes the solution a bit easier to think about.

→ Ответить

»

wuhudsm

11 месяцев назад, скрыть # ^ |

0

Hi, thank you for your reply. I'd like to explain my algorithm during the contest 321142583.

I defined set<ll, greater<ll>> S, so S.lower_bound(a[i]) is actually looking for the largest number smaller than a[i].

I didn't observe that the optimal answer must include max_a, but I noticed a similar conclusion: f(a[i], a[j]) >= min(a[i], a[j]).

This was my motivation for the following operation: if a[i] >= 2 * S.lower_bound(a[i]) and a[i] > lstans, add a[i] to vsp.

My analysis of the size of vsp is: if a[i] is not the current maximum or second maximum, a[i] > lst_ans cannot hold (according to f(a[i], a[j]) >= min(a[i], a[j])). Therefore, a[i] must be the maximum or second maximum to satisfy a[i] > lstans. Additionally, due to the other condition a[i] >= 2 * S.lower_bound(a[i]), a[i] causes the current maximum or second maximum to at least double. Thus, the size of vsp should be $$$O(\log A)$$$.

Overall, I believe my algorithm is $$$O(n \log A)$$$.

But sadly, based on my further testing (321273462), even only if you use a set, it results in TLE. You can see that even when vsp.size() <= 2, the code still gives TLE. I suspect this is because the constant factor for a set with $$$10^6$$$ elements is too large.

Although I didn't achieve AC in the contest, I still learned something: having a correct idea is not enough—you also need to optimize the implementation to reduce the constant factor. Regardless, thank you for your patient replies and for reading my code.

→ Ответить

»

wuhudsm

11 месяцев назад, скрыть # ^ |

0

UPD: Very sadly, got AC after using S.find(a[i])==S.end() instead of map. 321286450

→ Ответить

»

KiKoS

11 месяцев назад, скрыть # |

+17

Completed the full set today. I guess that's the first time for me during the contest time. Feels good :)

Problemset felt a bit more ICPC-style than usual, which is a good thing both for my performance and my impression of the problems. E seems like a kind of classic problem (even though the topic itself is not that popular so I liked it anyway!).

Thanks for the contest, I needed this morale boost after several poor performances last weeks.

→ Ответить

»

Inori

11 месяцев назад, скрыть # ^ |

0

Could you please explain your approach and what classical problem you used to solve it?

→ Ответить

»

11 месяцев назад, скрыть # ^ |

+5

Build a bipartie graph, the left side represents the volume and the right side represents the pitch. Each node in the original problem could turn into an edge in this graph. The problem turn into finding an Eulerian path from the bipartie graph we built.

→ Ответить

»

Ashar-Usmani

11 месяцев назад, скрыть # ^ |

0

wouldn't this be n^2 if we build vertex for every n

→ Ответить

»

11 месяцев назад, скрыть # ^ |

0

What do you mean by building vertex for every n?

→ Ответить

»

11 месяцев назад, скрыть # ^ |

+10

The vertices are the unique values of volume and pitch; there can be up to $$$n$$$ of each of these (i.e., there can be up to $$$n$$$ unique volumes in the input). The $$$n$$$ pairs in the input are the edges, not the vertices.

I suspect you might be imagining a graph where the $$$n$$$ input pairs are vertices and we draw an edge between any two pairs that share the same volume or pitch. This would indeed take $$$O(n^2)$$$ time to construct, and it also wouldn't lead to the solution's result that an Eulerian path in our graph is equivalent to a construction solving the problem.

→ Ответить

»

Ashar-Usmani

11 месяцев назад, скрыть # ^ |

0

thanks a lot i got it

→ Ответить

»

Inori

11 месяцев назад, скрыть # ^ |

0

Wow! Thats a really beautiful trick. Thanks a lot.

→ Ответить

»

KiKoS

11 месяцев назад, скрыть # ^ |

+2

Just to add a bit, even though some might just instantly remember this trick, I didn't, and here was my thought process:

I need some sort of connections from one $$$(x, y)$$$ to $$$(x', y')$$$, and I need to be able to create a sort of hamiltonian path
I say "sort of", because I need to alternate movements horizontally and vertically
Let's just duplicate each vertex so the state "i just did horizontal move" and "i just did vertical move" are separated
I now add states like $$$(x, *, H)$$$ and $$$(*, y, W)$$$ — a point and the last move direction.
I put asterisk because it is an important notice: when you do a move on constant x, you can go from any $$$y$$$ to any $$$y'$$$.
So now I can do something like $$$(x, *, H) \to (x, y) \to (*, y, W) \to (x', y) \to (x', *, H) \to \ldots$$$, and I want to find sort of Hamiltonian path covering all $$$(x, y)$$$.
Hamiltonian path is too expensive to find, so tweak the graph a bit to make Euler paths. From the sequence above it's more or less clear that the $$$(x, y)$$$ should be the edge between $$$(x, *)$$$ and $$$(*, y)$$$.

When I said it's a classical one, I meant that all of this process felt familiar and clicked really quickly for me. I believe some similar problems were already found in the comments.

→ Ответить

»

quarterHuman

11 месяцев назад, скрыть # |

0

How did you guys do the C question? I

→ Ответить

»

https://mirror.codeforces.com/contest/2110/submission/321153774

11 месяцев назад, скрыть # ^ |

0

My approach https://mirror.codeforces.com/blog/entry/143071?#comment-1277437

→ Ответить

»

3a51

11 месяцев назад, скрыть # ^ |

← Rev. 2 →

+4

Maintain two values $$$l$$$ and $$$r$$$ represents the minimum of $$$h_i$$$ and the maximum.

For the given $$$l_i$$$ and $$$r_i$$$, let $$$l_i:=max(l,l_i)$$$ and $$$r_i:=min(r,r_i)$$$. After that, you can get valid numbers($$$[l,r]$$$) of $$$d_i$$$.

Then iterate from $$$n$$$ to $$$1$$$, if $$$r_i=r_{i-1}+1$$$, then you must fill the $$$d_i$$$ with $$$1$$$. Otherwise, you can fill it with $$$0$$$. Here's the approach: 321077500.

→ Ответить

»

MyBrainGotTLE

11 месяцев назад, скрыть # |

0

I think E is easier than D ngl (even though I didn't solve it)

→ Ответить

»

vrintle

11 месяцев назад, скрыть # ^ |

+19

I think F is easier than A ngl (even though I didn't solve it)

→ Ответить

»

based

11 месяцев назад, скрыть # |

0

tfw solve C rank catapults from 3,000 -> 1,200

Solve D rank goes a measly 1,200 -> 1,000

Glad i reclaimed expert :)

→ Ответить

»

akane646

11 месяцев назад, скрыть # |

0

Can dijkstra passed D? I agree BS + bfs/dp is more logical but can anyone hack dijkstra submission? For example 321138356

→ Ответить

»

Stargazer_jeet

11 месяцев назад, скрыть # ^ |

← Rev. 2 →

0

Yes dijkstra + BS can pass D,

This is my solution:

→ Ответить

»

vrintle

11 месяцев назад, скрыть # |

0

What is the idea behind E?

→ Ответить

»

farmerboy

11 месяцев назад, скрыть # ^ |

0

https://cp-algorithms.com/graph/euler_path.html

→ Ответить

»

11 месяцев назад, скрыть # |

+7

What's the point of the announcement in problem D?

→ Ответить

»

11 месяцев назад, скрыть # ^ |

0

yeah .. very funny .. I had like 4 tabs open it shows that blocking alert popup in all pages... ha ha

→ Ответить

»

dp_gopher

11 месяцев назад, скрыть # ^ |

0

s_i < t_i means no cycle, so we can visit checkpoints in order, I guess?
Not sure how to solve if there was a cycle.

→ Ответить

»

11 месяцев назад, скрыть # ^ |

0

This is a crucial part for us to solve easily by using DP, but I don't think it is the reason for the announcement.

→ Ответить

»

mahaihang3

11 месяцев назад, скрыть # |

-7

The problem E in this contest has appeared in an ZhengRuiOI contest, and lots of people have seen it.

The solution of the that problem can solve E easily.

@MikeMirzayanov

→ Ответить

»

MaggiMonster

11 месяцев назад, скрыть # |

0

what is the approach for C? i Tried maintaining a suffix minimum of R boundary, and greedily converted -1 to +1 if my cur height<= smallest R afterwards. What is the logical flaw? and can someone pls provide a test case where my code fails https://mirror.codeforces.com/contest/2110/submission/321143380. Thank you

→ Ответить

»

hrishabhpatel09

11 месяцев назад, скрыть # |

0

Today's C why it fails?

I’m trying to keep curr (the current value) as low as possible. Whenever a jump is needed, I reduce the remaining allowed jumps by the amount of the jump. If curr becomes equal to the right end (R) of the current [L, R] range, I reset the remaining jumps to 0.

→ Ответить

»

pepelacc

11 месяцев назад, скрыть # |

← Rev. 2 →

0

Hey everyone. I've participated in programming contests very long time ago. Please update me on time restrictions. 1 second is how many arithmetic operations on C++ approximately?

Long time ago it was ~100.000.000. Is it the same now, or judge processors are much faster?

→ Ответить

»

SudoXue

11 месяцев назад, скрыть # |

0

This is crazy!!! I didn't even come up with such a simple F during the competition!

→ Ответить

»

DCSNMGPSSIK

11 месяцев назад, скрыть # |

0

I wish the contest running 30 minutes more :(. I just need more proves to solve F :(

→ Ответить

»

dpsvoyager.16

11 месяцев назад, скрыть # |

← Rev. 3 →

0

.

→ Ответить

»

AhmedPlusPlus

11 месяцев назад, скрыть # |

← Rev. 5 →

+8

XaRDKoDblCH , PvPro , N_z__ , BurnedChicken , triple__a , makrav , Noobish_Monk , mainyutin , k1r1t0 , Nil2007

Weak testcases in problem D, my solution gets accepted, but it's absolutely TLE

submission: 321103308

The code that generates TLE test :

#include<bits/stdc++.h>
using namespace std;
#define AhmedPlusPlus ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

signed main() {
/* ^^^ */    AhmedPlusPlus    /* ^^^ */

//    ->> practice makes perfect

    int n = 100000 ; // starting from n = 50 it get's TLE
    vector<tuple<int,int,int>>v;
    for (int i=1;i<=n-2;i++){
        v.push_back({i,i+1,1});
        v.push_back({i,i+1,2});
    }
    v.push_back({n-1,n,1e9});
    cout << 1 << '\n';
    cout << n << ' ' << v.size() << '\n';
    cout << 2 << ' ';
    for(int i =2;i<=n;i++) {
        cout << 0 ;
        if (i != n)
            cout << ' ';
    }
    cout << '\n';

    for (auto [f,s,t]:v)cout << f << ' ' << s << ' ' << t << '\n';


}

→ Ответить

»

fbrunodr

11 месяцев назад, скрыть # |

0

Why are there so many greys in top 200??

→ Ответить

»

amit_dwivedi

11 месяцев назад, скрыть # ^ |

+40

Because of stuff like https://mirror.codeforces.com/contest/2110/submission/321134571

→ Ответить

»

fbrunodr

11 месяцев назад, скрыть # ^ |

0

Did people leak F during contest??

→ Ответить

»

damgaurav04

11 месяцев назад, скрыть # |

+2

I attempted 3 questions and got all wrong how much my rating will decrease my current rating is 874 and today I submitted 10 wrong solution .

→ Ответить

»

Kingaroo

11 месяцев назад, скрыть # |

+1

Can someone give me testcase or explain me why my solution for C fails. 321130328

→ Ответить

»

theheatcoder

11 месяцев назад, скрыть # |

← Rev. 4 →

0

Hello I tried to solve problem D but I got tle on test 31.My debug skills are not good enough and maybe my logic is slow I am not completely sure about that. https://mirror.codeforces.com/contest/2110/submission/321157674

→ Ответить

»

Phaneendra27

11 месяцев назад, скрыть # |

0

The 3rd question's test cases may have multiple answers like there is this this test case 1 -1 0 1 The flight program for this can be both 0 or 1 as both of them give valid ranges. Kindly take a look into this.

→ Ответить

»

CoderAnshu

11 месяцев назад, скрыть # |

0

Why so tight constraints in F? Which solution are we trying to kill?

→ Ответить

»

KiKoS

11 месяцев назад, скрыть # ^ |

← Rev. 2 →

0

i still dont know the model solution but basically after I figured out $$$f(x, y) \le 2 * min(x, y)$$$ I started filtering out all small elements and bruteforcing only on elements in the window $$$[\frac{ans}{2}, \inf)$$$. If too many, you take only top-$$$K$$$ (probably top-K max and top-K min in the window should work). With high enough K you might pass, so you need a big $$$n$$$ to punish big value of K.

BTW, after that the full is just to do a full recalc each time $$$a_i$$$ is bigger than twice the current ans. But that's not easy to notice and one might try to just bruteforce more. Hence the constraints. 321166762

→ Ответить

»