Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Ajosteen's blog

By Ajosteen, 3 months ago, translation, In English,

Hello, community!

Codeforces Round #509 will be held on Sep/16/2018 13:35 (Moscow time). The round will be rated for Div. 2 contestants. There will be 6 problems for 2 hours. Please, notice that the start time is unusual.

The round will be rated for the div. 2 participants. The statements will be available in Russian and English languages.

The round will start 2 hours after the start of the Qualification Stage, so they will finish around same time. That's why we ask the participants of the Quals to stay silent and don't share the statements of the contest with anyone. Unfortunately, we cannot add all the problems from Quals to the round, it will contain only six problems.

The problems for the official contest were prepared by the guys from the jury in the person of Alex fcspartakm Frolov, Adilbek adedalic Dalabaev, Ivan BledDest Androsov and me.

We also would like to express our gratitude to Anton arsijo Tsypko for coordination of the round and Mike MikeMirzayanov Mirzayanov for the permission to make a mirror and Codeforces and Polygon platforms. Also big thanks to the testers: IlyaLos, Perforator, kuviman, HolkinPV, zubec, StasyaCat, Karasick for testing.

As usual, the scoring distribution will be announced just before the round.

Good luck!

UPD: Scoring Distribution: 500-1000-1500-2000-2500-3000

UPD2: Editorial

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

»
3 months ago, # |
  Vote: I like it +29 Vote: I do not like it

After 9 days, wait is over.

»
3 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Early tomorrow morning there is also the Qualification Stage of Singapore (mirror available on Kattis).

Looks like the ICPC preparation is underway simultaneously all over the world :D

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve D and E?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My soln for D —
      You can refer here (Question is a bit similar to this) to find all cycles in D.
      One observation — if there exist 2 edges of a vertex which leads it to 0 then this vertex belongs to the soln set => vertex belongs to cycle.

      Now all cycles which have zero as vertex belongs to the soln set. And If at least one vertex of cycle belongs to soln set then all vertex belongs to the soln set. So dfs2 was made to find soln set which marks all cycles which belong to soln set. And then runs dfs2 for all vertex of this set.

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Another approach for D that I found after contest time (should give some credits to my friend liv1n9 for some ideas within it, not sure if this was his exact approach coz' I didn't fully manage to get his words :D).

      A junction can be considered safe if there are at least 2 paths from junction 0 to it (obviously, junction 0 is a safe junction itself).

      Therefore, I'll transform the given undirected graph to a directed graph (each bidirectional edge will be considered as 2 edges between two junctions, just with different directions).

      With this new graph created, I'll perform 2 separate DFS traverse, both started from 0:

      The first traverse will give me a directed subgraph (consisting of directed edges) that allow me to reach every junction from junction 0 (yet not the other way around). After that traverse being complete, I'll delete that whole subgraph.

      The second traverse will let me know if each junction is safe (i.e. there exists another path from 0 to that junction, after deleting the first path given in the previous subgraph).

      The subgraph deletion can be handled easily if adjacency list of each junction is maintained by a set instead of vector/array.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think this approach will fail on following test case. 3 3 0 1 0 2 1 2

        Because deleting a subgraph will delete 2 of 3 edges. And based on which 2 edges are deleted remaining graph will have 0 or 0,1 or 0,2 as an answer.

        But in fact, all 3 vertexes are in soln set.

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Actually, I should apology for my explanation being a bit vague.

          The subgraph being deleted is a directed one, that means I'll only delete the edges that can lead from junction 0 to other junctions (but not the other way around).

          Therefore, after 1st DFS, directed edges (0 → 1), (1 → 2) will be deleted.

          The second DFS can still reach all other junctions (one possible path is 0 → 2 → 1).

          (Explanation edited in the main comment as well).

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    How to solve C, E ??

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My idea for E: binary search + flow

      You can binary search the answer: with each value z, build a bipartite graph that, there exists a edge between (xi, yj) if aij ≥ z. z can be the minimum value of a combination if the maximum bipartite matching of the newly built graph equals exactly N — this could be solved by maxflow algorithms.

      (I didn't solve it during contest time, just knew the idea, but couldn't implement maximum bipartite matchings properly :-P)

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 4   Vote: I like it +11 Vote: I do not like it

      You can solve C using dynamic programming. First observation: after building N characters, we can uniquely determine the last N characters.

      So let's dp(i, j, k) be the number of ways, we are at i-th character, already at j-th character of string s from prefix and at k-th character of string s from suffix.

      Then answer will be sum of dp(n, j, k) where j >= k.

      Solution for E: first we binary search the answer, let's assume we are at mid, build a network flow, add an edge with capacity equal to 1 from source to every row, add an edge with capacity equal to 1 from every column to sink, then for each row and each column (assume it's i-th row and j-th column), if aij >= mid then we add edge from row i to column j with capacity equal to 1. Then if maximum flow equal to size of board then l = mid + 1, else r = mid

»
3 months ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

thanks cf

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i don't understand this line properly. "The round will start 2 hours after the start of the Qualification Stage, so they will finish around same time." can you please explain it in details?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It means that Quals is the 4-hour length contest

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      when i can start? from the qualification stage?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        You can start tomorrow on 13:35 (moscow time) at cf round

»
3 months ago, # |
  Vote: I like it -16 Vote: I do not like it

It is rated for Div2. My rating is 1900+ is it rated for me?

»
3 months ago, # |
  Vote: I like it +55 Vote: I do not like it

Perfect time for Chinese users!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    You are right!

    thanks for Codeforces!

    the begin time is so good!

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      I'm Chinese too. The time is really wonderful!

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        Wonderful time!Thanks for codeforces!

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it

    Wow! It's wonderful. And I hope that the description of the problems will concise


    After the Contest:

    ………………

    I can only make a joke:

    "My English is so bad"……

»
3 months ago, # |
  Vote: I like it -9 Vote: I do not like it

It Was So long time.

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Ajosteen, are problem statements gonna be long like in NEERC rounds or adapted to CF round?

»
3 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Personally speaking, I think that Codeforces is the best oj in the world.

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

8000+ contestants

»
3 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Solved 2 problems for the first time

»
3 months ago, # |
  Vote: I like it +37 Vote: I do not like it

queue

»
3 months ago, # |
  Vote: I like it +27 Vote: I do not like it

My submission has been staying in queue for 5 minutes, any help ?

»
3 months ago, # |
Rev. 3   Vote: I like it +33 Vote: I do not like it

I have much more penalty on pC because of the queue, can I have some points back?

Edit: Actually, 40 points won't affect me too much, but I feel sad for those who were actually affected by the delay.

»
3 months ago, # |
Rev. 4   Vote: I like it +22 Vote: I do not like it

If one is not good at English (such as me) : then :

Is it EnglishForces???

Is it Codespeed???

……

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

extend the round due to queue by at least 10 minutes

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

why the f I checked my submission after I had locked.....

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

EnglishForces

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's wrong with this solution for D? 42940213

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Test Case 5-
    2 1
    1 2
    3 4

    Your output is 3. But the answer is 2. My one attempt failed due to this. :P

»
3 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

This problem set seems to be the most balanced one in recent times on codeforces:D

Btw how to solve F? I could reduce it to finding maximum number of points lying on a straight line in a given set of points,but couldn't use the property that distance between adjacent points(along one co-ordinate) is same.

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    let assume your picks B and A , and B-A is T;

    so in the first line you get A + 2t + 4t + 8t, and in the second line a+t , a+3t ....

    you only need find the answer for every t which is power of 2.

    because for example picking t=6 is subset of t=2;

    I guess you can find an answer of every power of 2 .

    Note: for every T you should look at numbers in mod 2t. so increase mapA[a[i]%2t]++ and mapB[(b[i]%2t)]++

    so look for the maximum mapA[i] + mapB[i+t];

»
3 months ago, # |
  Vote: I like it -66 Vote: I do not like it

please consider making it unrated

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

test case 5 on problem d ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I think it is similar to

    2 1 1 5 6 10

    The answer is 5. Wrong solutions might output 9.

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Anyone has idea what pretest 7 for C is?

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

https://codeforces.com/blog/entry/61876

this says editorial posted 3 hours ago

»
3 months ago, # |
  Vote: I like it -11 Vote: I do not like it

i think cf started div4...

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea on what might be the pretest-9 in Div2 C? Thanks

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Why i can't see another's solutions?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Each input must be in the form of i n since node n will fall into one of the parts after erasing an edge. If i n exists multiple times, add nodes with smaller indices between them.

»
3 months ago, # |
  Vote: I like it +33 Vote: I do not like it

RIP all contestant who thought that A can be equal to B in F...

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Isn't "RIP all contestant who didn't thought that A can be equal to B in F" ??

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Wait, so it turned out that the clarification for my question is incorrect?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        I'm really sorry for that(

        When your question arrived, the only thing I had in mind was "A and B are on the different sides of the tube, how can they be equal?" I haven't thought that the question was about x-coordinates.

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

          I could not solve F in time, so it didn't affect me anyway.

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think BledDest is formally right in this case...

»
3 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

In F, for the test

1 100
1
1 200
1

would the answer be 1 or 2 (ray bouncing off vertically)?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I have the same question

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    It should be 2, since there is no restrictions on relative positions of A and B. I'm sorry for the absence of such test in the pretests, trying to break some clever solutions, I forgot about this basic one.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    2. I got hacked for this case.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got fst for this case

»
3 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Explain me please why I got TL on pretest #9 (Problem C) Solution

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    cur=upper_bound(ms.begin(),ms.end(),pp);

    complexity of upper_bound on set is O(n), If you want to use upper bound use s.upper_bound(value to be searched) which is O(logN)

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      One more bit of information in addition to what you've said: http://www.cplusplus.com/reference/algorithm/upper_bound/.

      Complexity On average, logarithmic in the distance between first and last: Performs approximately log2(N)+1 element comparisons (where N is this distance). On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I just don't get it why would that take runtimeerror

even if i erase an iterated element from set I should still be able to reach the iterator value

I kept getting runtimeerror until i changed this... but why would that work for some test but not for pretest 9

solution

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    even if i erase an iterated element from set I should still be able to reach the iterator value

    Lol.

    After you've erased the element, the iterator is invalid. Essentially, it can be seen as a nullptr or any other random trash.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know that means this is a mistake but that worked for some tests and it shouldnt at all if it is

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's called undefined behavior. Sometimes iterator might still point to the memory which has useful data, sometimes it might not.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If I submit a solution at time t, my submission is inque for a hour, what's the final submitted time of the solution? t or t+60?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Of course t. Penalty is counted by the time of submission, not by the time of judgement.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe I will become gree tomorrow...

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why pA with counting sort would pass...

a O(1e9) solution passes the test with 534ms...

»
3 months ago, # |
Rev. 14   Vote: I like it +61 Vote: I do not like it

The round just became worse... :'(

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

There are same submission of problem C by some participants so please look into this matter. MikeMirzayanov

»
3 months ago, # |
  Vote: I like it +136 Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

RATED PLIZZZ

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Tutorial #1 and Tutorial #2 redirect to the same link

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rated Rated Rated xD

Give me back my purple <3

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I can't make a submission, seems like practice mode is disabled. Is this supposed to happen?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Practice mode is disabled during system testing. You can submit now.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know that. Systest was over, and usually practice mode is instantly enabled. Thanks for answering anyway!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How does this soln passes System Test Cases?
It iterates from 1 to 1e9 in worst test cases.
Even passes Test Case (My failed hack.)
3 1 1000000 1000000000
with time 15ms.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    Because of compiler optimizations, that source is literally O(n), which is good enough. I once got tricked by this, and i've learned my lesson since

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got 5 unsuccessful hack because of this(-_-).

»
3 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it
»
3 months ago, # |
  Vote: I like it +28 Vote: I do not like it
»
3 months ago, # |
  Vote: I like it +24 Vote: I do not like it

What wrong with D? Don't make me scare :(

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

WTF?

»
3 months ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

When somebody being a candidate master and can edit tags.

![ ]()

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For all of you who had WA on E on test 33 and don't know why. My problem was:

    int i = 0;
    pair<int, int> p = make_pair(i, ++i);

Pair p contains (1, 1) instead of (0, 1) :/

I would be grateful if someone could explain briefly what is the cause of such behavior.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Arguments of any function/constructor could be calculated in any order (it's not strictly wrote in C++ standart). Thus, some compilers use left-to-right calculations, some of them use right-to-left, some of them could even use some crazy rules.

    You can learn more here: https://en.cppreference.com/w/cpp/language/eval_order

»
3 months ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

The number of tags (algorithms that can be used to solve the problem) of problem C, D and E is huge and impressive. :) Ajosteen, thank you very much for this awesome and interesting contest.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So why do I think that D is much easier than C?For D u just need to get the prefix sum and do lower_bound.I get WA on pretest 9 of C :(.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does everytime I spend hours during contest to get an idea but the idea hits my brain in just about 10/15 minutes after the contest is over? So frustrated... :(

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its okay as long as you keep getting ideas. Some of us dont even get the idea.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What's the point of getting the idea though if you can't submit in contest time? Well it's still better than nothing but submitting correct in contest is what it really matters

»
3 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

Wrong answer on sample test cases isn't supposed to get time penalties, correct?

I accidentally submitted an incorrect solution to the 3rd question (which was wrong on sample test case 2) and I got time penalty. Is this wrong or am I incorrect?

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I failed WA in D test 11, any ideas what I do wrong? (Was trying to solve with 2 pointers)

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Sorry, it's offtopic.
Anyone knows how to add Codeforces contests to google calendar?
Upd:- Got it now.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem D get a DP tag too? My approach was to calculate the covered distance when I start from the i'th segment and using previously stored data of other segments which are already calculated. Of course, there are better approaches to this problem.

»
3 months ago, # |
  Vote: I like it -22 Vote: I do not like it

sorry,codeforces,i feel surprised that i will receive a letter from you. As a foreign person, i often attend some contests in cf. But i not always get good grades, because my contest skills and English are not so good.I don't want to become green pupil, i just want to be a specialist.In the contest, i copy my friend's coding, this is truth,i don't want to hide from responsibilities.At first,i want to do D problem, because i have done the similar problem before. Unfortunately,there is some thing wrong with my coding. But i don't want to decrease my rating, so i copy. At first, i don't know CF can find the problem, maybe AC automation or trie? And i don't know CF will consider the problem so seriously. I swear i won't do this again. Some people will ask why i don't login a new id, because i don't want to let my story faded away.I want to record every contest, so i can always let myself keep hardworking.I will keep practicing,please don't look down me. All in all, i'm very sorry, i won't do this again.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    oh, and i can do problem c, but i want to increase my rating more, so i just saw D.10minutes is not enough for c. Also,my stl is not so good.

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Easiest F I've ever seen

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody help me in problem C 43011918, i am getting the message "wrong output format Unexpected end of file — int32 expected" on test case 13 ,but i am not able to find any such mistake where i am accessing value from any wrong index.Thanks in advance!

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Full Qualification Stage have been added to Gyms.