SlavicG's blog

Codeforces Round 859 (Div. 4)
By SlavicG, history, 21 month(s) ago, In English

Hello Codeforces!

mesanu, flamestorm and I are very excited to invite you to Codeforces Round 859 (Div. 4)! It starts on Mar/19/2023 17:55 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

  • 5-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to all testers: jampm, Max_Calincu, KrowSavcik, TimaDegt, nyaruhodo, tibinyte, badlad, Phantom_Performer, AlperenT, Bakry, keta_tsimakuridze, Gheal, RedstoneGamer22, Dominater069!

And thanks to Alexdat2000 for translating the statements!

We suggest reading all of the problems and hope you will find them interesting!

Good Luck to everyone!

UPD: Editorial

  • Vote: I like it
  • +210
  • Vote: I do not like it

Comments Comments (205)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

What will I gain from hacking if there are no points?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

As a tester, I suggest you participate! Problems are nice and educational!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I love div4 contest because i get positive delta.thanks for doing div4 contest!!!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I wish to see nice problems like other div4s

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

As a participant, I want to thank you for the contest!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What I was waiting for the most!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

ooh div.4 . Means SlavicG in action :)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

OMG SlavicG Round!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

As GPT-4, tomorrow will be my 5th contest participation. I hope I become green :)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Added you as a friend, already. Please, note, that while all the rest were laughing at you, I was always on your side! Hope you'll kill me last.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Going to be my first unofficial round.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

flamestorm orz

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    people on their way to post this meme hoping they will get some upvotes

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 4

So, easily will do 80% of the problems.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -36 Vote: I do not like it

As a tester, Give me contribution!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become expert in this contest.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Hope to see the colour change in this round !!
( Δ > +6 )

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

hello. i am man; i am from to mars and run away at abi abi is brother but not brother; abis isnt cool; int monkey; monkey = monkey + wepon; cout << monkey kill nuraly SH;

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Hey, are you a contest? 'Cause you're looking CUTE!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -6 Vote: I do not like it

I would smash this contest

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Delayed round?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Starting time 10 mins. extended...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

Div 4 contest, more like load testing for Codeforces Servers

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    2 tests failed, +20 minute penalty

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

the contest keeps getting delayed by 10 minutes for me? just me?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

LateForces

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

More than 30k participants and now Codeforces is trafficked

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Today i'm grey again..

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

DelayForces

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Feeling like participating in onsite contest where after every refresh 10 minute increase.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -17 Vote: I do not like it

Worst Server I Have Ever Seen!..

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Div.4 is good for me~

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

May be, the queue more long than my imagination :3
)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

If there was going to be interactive problem.It should be mentioned in blog beforehead.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Interactive problem isn't really that different from normal problem.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

that long queue really sucks

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Didn't know for like 10 minutes my solution was too slow...

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

QueueForces:(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

In queue forces :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

There must be a prior information about Interactive problem in contest. i have seen several div 2 contest where author has given prior info about interactive problem.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Where in codeforces rulebook does it say that? Why does everyone hate interactive problems?

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

I like the contest, but the website is not co-operating :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it was supposed to be mentioned before the start of the contest about the interactive problem.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

I'm praying to the universe this contest does not go unrated :)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

Seems like Mike is manually judging solutions

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +89 Vote: I do not like it

I apologize for the long queue at the round. Today's round was a record in terms of the constant huge flow of submissions. Unfortunately, we ran into the speed of compilation. I already have plans to move the compilation somewhere to the cloud in such extreme cases. I plan to implement this for the next div4.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    bits/stdc++.h showing it's true power

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please make this round unrated it wasn't a normal Codeforces round queue was way too long T_T

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It was fair because everyone was at a disadvantage. Everyone's queue was 10 minutes long, I don't see how it affects one's ability to problem solve.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Interactive problem + long queue = nice COMBO!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

The long queue has taken a toll on those of us who rely on proof by AC.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

solving 1 (last problem took me more time than solving all the rest of the problems combined...

Due to WA and LONG WAITING QUEUE.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -10 Vote: I do not like it

Lagforces...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Are pretests on hard version of G weak? I realized my code was doing the opposite of what I wanted it to do after submitting and it still got AC... I have no idea how my solution works.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Bruh why did you let bitset pass G2?

UPD: I got hacked lol

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    div4Forces

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hacked uwu

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I solved 1807G2 - Subsequence Addition (Hard Version) with C++ bitset too. At current time I have 800 ms.

    My submission.

    I see, that iiand tries to hack it right now. Hope, that he will share test case when succeeded, it is quite interesting.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Perfect solution:)

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        I thought all this time that this is bitset-related problem and solution with bitset is intended solution. Was really surprised when discovered alternative greedy solution in comments under this blog...

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Very hard to track if the submitted answer was right or not !!

A lot of time wasted there. Apart from that really very goooood contest.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How did I get G1 accepted and G2 WA with the same solution provided

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    just use long long

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    My advice is if you use c++, add

    #define int long long int

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      that is not a good advice, you can TLE if you're not careful, I advice you to manage your limits properly instead.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I suppose, but that has never happened to me before.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, many of the setters are pretty generous with their time limit, and you should easily pass even with long long, this is not always the case though, better to be careful

          → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can get MLE or TLE with that in some problems.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing Problems <3

I loved E because It was first time I solved an interactive problem.

Only if Queues werent that long I could have figured out my Idleness Limit Exceeeded 10 minutes before :(.

Solved everything except F

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Contest over,still my solution is in queue :))

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I am using prefix sum in G,why it is giving WA My solution

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if(n == 1 && v[0] > 1){ pn; return; }

    you dont need n==1 here because you cannot change all 1s in the initial array.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G2?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if the kth element of the sorted array is less than or equal to the sum of all 0...k-1 elements then ok else no. iterate for all from 1 to n-1 (0 based) and sorted

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It is always correct to add numbers in increasing order. So you can sort a and there holds invariant: if a[i] > a[0] + a[1] + ... + a[i - 1] then there is no way to add a[i]. And if a[i] <= a[0] + ... + a[i - 1] then you can add a[i] and you can add for a[i + 1] any number from 1 to a[0] + a[1] + ... + a[i].

    So just sort and check that for each i a[i] <= a[0] + ... + a[i - 1]

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      " And if a[i] <= a[0] + ... + a[i — 1] then you can add a[i] "

      How?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Let's assume that you processed indexes 0..i, and you established that you can always get any sum from 1 to S = sum(a[0..i]). Then there are two cases:

        1. a[i + 1] > S then you cannot add a[i + 1] and answer is NO.
        2. a[i + 1] <= S then you can add a[i + 1] and you can get any sum from 1 to sum(a[0..i+1]) (because you can take any sum from 1 to S in indexes from 0 to i, and you can add a[i + 1] to that).
        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    G1-G2 were easy when u observe that as we have the minimum unit as 1 so we can form any possible sum. So say we sort the array now following conditions should hold.

    • $$$a_0$$$ should be 1. (as it was initially given and not gonna change).
    • $$${a_i \ge a_0 + a_1 + ... + a_{i - 1}}$$$. (as if prior max subsequence can't form current number than it's impossible to make $$$a_i$$$)
    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      " when u observe that as we have the minimum unit as 1 so we can form any possible sum "

      Could you please explain how is it possible to form any sum?

      Although minimum unit is 1, but we need to make sure that intermediate values should also be there in a.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        As we are given, $$${a = [1]}$$$.

        • In the next step, $$${a = [1, 1]}$$$
        • In the next step, $$${a = [1, 1, 1]}$$$ or $$${a = [1, 1, 2]}$$$
        • In the next step, $$${a = [1, 1, 1, 1]}$$$ or $$${a = [1, 1, 1, 2]}$$$, or $$${a = [1, 1, 2, 3]}$$$.

        So by this, you can observe that in any way we can form the next number $$${1, 2, 3, 4}$$$ by choosing any above combinations.

        So via this, you can prove any next number is possible if the prefix sum is greater or equal to that number.

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can prove it by induction. Lets say I can make any sum from $$$1$$$ to $$$k$$$ using the current numbers from $$$a_0,a_1,\cdots,a_i$$$. Then consider $$$a_{i+1}\le k$$$. Since I can make any sum already from $$$1$$$ to $$$k$$$, I can make $$$a_{i+1}$$$ and add it to my list of numbers, and now if I add $$$a_{i+1}$$$ to those previous sums, I can now make any sum from $$$1$$$ to $$$k + a_{i+1}$$$. However, if $$$a_{i+1}\gt k$$$, then notice that I can never make $$$a_{i+1}$$$, because the current numbers cannot make any sum greater than $$$k$$$.

        So if at any point $$$a_{i}$$$ is greater than the sum of the numbers before it in sorted order, the answer is NO.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Simple solution: Sort array, go over each number and make sure its not greater than the running sum, unless the number is 1.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

beautiful problems, even if i couldnt solve all i was manage to at least have a go at it. Perfect div.4 round

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yes. Perfect Div4 round indeed. Was able to solve only A-E during contest, but first time I upsolved all questions of any contest.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for F? I got TLE :D

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

PrefixsumForces

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1807/submission/198254663 why T.L.E

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Good contest! Wasn't too fond of F though, so didn't do.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Waited 15min to get wa on test 1 (E problem).

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In fact, testing was slow today. But I'm not sure you're right about 15 minutes. What is the id of your submission?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      E had the longest queue out of all my submissions for some reason. Waited so long to get WA on both sucked when I could have used the time to solve F

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +2 Vote: I do not like it
      • Sent: 2023-03-19 19:25:39
      • Judged: 2023-03-19 19:36:12

      It looks like 10, but not 15 if you want to round it. It took a long time to test (sorry about it), and I'll work on it. But you exaggerated almost one and a half times.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

For G2 and G1, after sorting the array I knew that that one of the conditions was that every element should be at max the sum of all the elements that occured before it. Little did I know that it was the only condition required. Could someone explain me why we can always make every number from [1 — sum of all elements occured] from the given elements ?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    We can prove by induction...

    Obviously it is possible to reach all numbers that are less than or equal to 1 by using 1. Then consider a time when we add a number j and the sum of existing elements is i. Assuming that all numbers up to i can be reached. Then all numbers from i to i + j can be reached by adding j to a number from 1 to i.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

F will be an interesting (and definitely too hard for div4) problem if the constraints are n,m<=1e9 and no guarantee for their sum.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why the following code for D is getting TLE? It has time complexity of O(n+q)

Spoiler
→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Even after many attempts , i am unable to remove "Idleness Limit Exceeded" to the problem E : 198257666.

Your help is appreciated.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    endl in c++ flushes the i/o stream by default so no need to use cout<<flush after using endl Though I didn't check your code thoroughly (some other bug maybe there)

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i did the same but still it gives the same error.submission

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Remove the n == 2 case. query output format is wrong and this case is not needed at all.

        → Reply
»
21 month(s) ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone please explain how to do problem D within time limits? And what optimization was needed for G2, i got G1 correct, sorted the array and checked if any element was larger than the sum of those before it, but TLE on G2 at test 19(coded everything in C)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    using prefix sum. .. pre compute the prefix and suffix sum of the array. so for range[l,r] we need the sum of elements excluding this range which can be calculated using the pre computed sum. prefix[l-1]+suffix[r+1]and for the range sum can be calculated as k*(r-l+1)..

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I found the sum of all elements once and then just subtracted the elements in that range for each query and added k*(r-l+1), won't that be faster than calculating prefix sum for each case https://codeforces.net/contest/1807/submission/198251225

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no, clearly not, prefix sum calculation takes o(n), and query takes o(1), the worst time complexity if you calculate for each is o(nq), while if you precalc, its o(n+q)

        → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is wrong with my solution of D.?? Please look into it. https://codeforces.net/contest/1807/submission/198208523

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    int overflow where you used --->>> (r-l+1)*k <<<----

    → Reply
»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

please can someone tell me why is my solution to problem E giving WA on testcase 1? https://codeforces.net/contest/1807/submission/198264987

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    you printed the "value" at the indices in the queries, we had to print "indices" in the queries

    change v[i] to i

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I see someone using correct way to do G2 but it hacked...

a[0] must = 1 for all 1 <= i < n, if a[i] > sum(a[0]~a[i-1]) then answer is NO. else is YES

is it wrong?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think the general idea is right (it's what I did anyway). Which submission are you referring to?

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E Flushing Problem what's the wrong with using '\n' always (Idleness limit exceeded on test 1), using endl (Accepted)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I submited with '\n' and it passed.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    • cout<<"! "<<s<<'\n';
    • fflush(stdout);

    No! First one unties cin/cout operations from stdin/stdout operations, so it is implementation-defined (or even undefined, but no sure) behaviour to mix up them both after that.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem F was not hard to understand but hard to implement. My guess is that there is probably a great implementation that does not require bunch of if and else blocks.

Can someone share a nice and compact implementation or the idea behind it?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

F with simulation

Solution
→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How on earth Yodasen made possible to write solution and submit within the time interval of 5 second (solution A(3 min 53s) & D(3 min 48s)) and 21 second (solution C(7 min 30s) & G1(7 min 9s)) second!

Is this real??

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Also, look at his submissions. The templates are different, obvious 2/3 people on a single account.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F, while contest I didn't read constraints properly, I designed more generalised solution. my solution will work for N <= 10^5 ( or even N <= 10^6 ) .

[submission:https://codeforces.net/contest/1807/submission/198280396] .

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't think you solution is a more generalized version. If the pigeonhole thingy from your solution actually holds, then it holds in everyone's solution that memoized too.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      most of the solutions are using dx[4] = {1,1,-1,-1}, dy[4] = {1,-1,1,-1} , and ball is moving one by one step( from cell (i,j) to (i+1,j+1) or (i-1,j-1) .. etc ).

      In my solution, ball jumping from one wall to another wall in O(1) time.

      Pigeonhole principle will hold only for boundary cells. Not for inner cells.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 3   Vote: I like it -28 Vote: I do not like it

        I haven't seen any solution moving cell by cell, they will probably TLE if they do that. Every AC solution I've seen moves in O(1) time between the walls.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          mine moved cell by cell and it work fine, no TLE

          → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +42 Vote: I do not like it

          You should really check before making incorrect claims. btw, these were the first 8 submissions I checked.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
            ← Rev. 2   Vote: I like it -18 Vote: I do not like it

            oh no, another ScarletS notification. leave me the fuck alone.

            Did you even read his initial comment? How is that a generalized solution?

            I said I haven't seen any AC solution using that, and they will PROBABLY TLE, so what is the wrong claim there???

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              oh no, another instance of Trippie saying dumb shit, misleading people and expecting to not be corrected!

              I said I haven't seen any AC solution using that, and they will PROBABLY TLE, so what is the wrong claim there???

              And I said nearly everybody submitted such a version, and pulled up the first 8 submissions I checked, implying that you probably didn't check.

              Keep spreading nonsense from an alt though, I guess noone would take you seriously on your main anyways.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) ago, # ^ |
                ← Rev. 2   Vote: I like it -19 Vote: I do not like it

                Where did I mislead anyone? Lol

                Go through the first page of the submissions, and more than half of them don't go through cell by cell.

                The Div1 guy is always right anyway, enjoy your internet points.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it +10 Vote: I do not like it

                  First submission on the page: 198531289.

                  The Div1 guy is always right anyway.

                  In this case, sure. Keep digging yourself a hole though.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it -8 Vote: I do not like it

                  Man, how stupid are you? I said more than half of them did I say the very first one?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it +10 Vote: I do not like it

                  Pretty much every single submission on that page is cell by cell. Stay grey though.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it -18 Vote: I do not like it

                  Lol, how'd you figure I'm grey? Oh, no! Anyway, this conversation isn't going anywhere and has diverted from my initial argument. Ths solution wasn't a generalization, and I thought the solutions moving cell by cell will TLE that's why I used the word PROBABLY (you can use a dictionary). Have a bad day!

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it +10 Vote: I do not like it

                  The right move would be for you to admit you were wrong and move on. Keep digging your hole though!

                  → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, why is my code for problem D giving WA on test case 4? The logic should be correct and I cannot think of any bugs. Is there something I have failed to account for? There shouldn't be any issues with int overflow I believe.

Code

Thank you all very much in advance.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it 
    1
3 1
1 1 1
1 3 999999999

    Your code outputs "NO" instead of "YES"

    The error is that l, r, and k are ints, so temp += (r-l+1)*k first evaluates (r-l+1)*k as an int, which overflows.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think (r-l+1)*k can overflow

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how is e related to dp???

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you sort array, then:
    dp[i][s] = if you can make sum S using the first i elements

    base case:
    dp[1][1] = 1 (and check if a[1] == 1)

    transition is:
    dp[i+1][s] = dp[i][s] | dp[i][s-a[i]]

    Observation is that if some sum t can be created using first p elements, then it's also possible to create any sum <= t. So we can remove one dimension from the dp and store only the max s for which dp[i][s] = true.

    This is actually how my reasoning went during the contest.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you prove this observation?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        proof by induction:

        Define s[i] max sum that can be created from first i elements.

        It's true for i == 1, because a[1] == 1 and it's possible to create sum s[1] = 1 only

        Assume it's true for i, now prove that it's also true for i+1. If a[i+1] is greater than s[i], then the answer is NO, so assume a[i+1] <= s[i]. There are 2 cases. To create sum x <= s[i] we can do so without including current element, because it's already possible to do so using previous elements. To create s[i] < x <= s[i] + a[i+1] we can use current element, and create sum x - a[i+1] from previous elements. Creating sum x > s[i] + a[i+1] is impossible, because x - a[i+1] > s[i] and (by definition) s[i] represents maximum sum that can be created using first i elements. So s[i+1] = s[i] + a[i+1]

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Forgot to mention why sorting is necessary:

          A number can only be constructed using numbers less or equal to it, because no negative numbers are allowed

          → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How does one become a tester?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why am I getting TLE in the given code below.

https://codeforces.net/contest/1807/submission/198262166

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I am not sure but I think because the worst thing for your code to not find a solution for 1000 cases, in this case your complexity is $$$10^8$$$, but multiplied by many constants such as functions parameter and body, and so on

    Update

    I made a mistake above: the code will never reach to 10000 because you have visited array

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

A small trick for Problem F

If you represent {DR, DL, UR, UL} as {0, 1, 2, 3} and have $$$d$$$ as direction variable, you can change directions easily

  • To change between $$$U$$$ and $$$D$$$, it can be done by XORing $$$d$$$ by 2, for example: ($$$d$$$ ^ 2)
  • To change between $$$L$$$ and $$$R$$$, it can be done by XORing $$$d$$$ by 1, for example: ($$$d$$$ ^ 1)
→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Are ratings changed yet?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It doesn't changes individually.Either it will change for all or none.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating should be update before today's Div 2 round start.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are they redoing system testing?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question related to Problem D. Odd Queries If the queries affect future queries. What would be the solution for this

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably Segment-Tree or other similar DS's.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      doubt segment tree because it does point update in log(N) but here we are changing entire subsegment (L to R with k) right? so time complexity per update will still be N*log(N)

      thus time complexity to process all queries will be Q*N*log(N)

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        segment tree can do range update in O(logN) with lazy propagation

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 3   Vote: I like it +1 Vote: I do not like it

          my bad i assumed lazy propagation would imply we need to check for the condition in the end i.e., check if the updated range sum is odd or not , i learnt something new thank you :)

          → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I was Thinking Like You

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved the problem D. In the contest, but After re-System Testing i get TLE :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

"Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you."

My rating was 706 before attempting the contest, and it hasn't been affected yet. Wasn't the contest rated?

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

..

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

Solved the first 4 problems in 8 minutes and 5 problems in 17 minutes. Check the screen recording here https://youtu.be/HsGvOHmTwOw

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

why does problem 1807A - Plus or Minus have the "interactive" tag?

→ Reply