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

Автор Ajosteen, 11 дней назад, По-русски,

Привет, Codeforces!

В 16.09.2018 13:35 (Московское время) состоится Codeforces Round #509 для участников из второго дивизиона. Участникам раунда будет предложено 6 задач и 2 часа на их решение. Обратите внимание на необычное время начала раунда.

Раунд будет рейтинговый для участников второго дивизиона (с рейтингом менее 2100). Условия будут доступны как на русском, так и на английском языках.

Раунд начнется через 2 часа после начала квалификационного этапа и закончится с ним в одно и тоже время. Поэтому мы просим участников квалификационного этапа не распространять задачи до начала раунда. К сожалению, все задачи не поместятся в стандартный Div. 2 раунд, поэтому мы выбрали шесть из них.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов и Александр fcspartakm Фролов.

Благодарим MikeMirzayanov за возможность провести зеркало квалификационного этапа и за платформы Codeforces и Polygon, Антона arsijo Цыпко за помощь в подготовке раунда, а также IlyaLos, Perforator, kuviman, HolkinPV, zubec, StasyaCat, Karasick за тестирование.

Как обычно, разбалловка будет объявлена ближе к началу раунда.

UPD: Разбалловка: 500-1000-1500-2000-2500-3000

UPD2: Разбор

 
 
 
 
  • Проголосовать: нравится  
  • +237
  • Проголосовать: не нравится  

»
11 дней назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

After 9 days, wait is over.

»
11 дней назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Так а можно было бы два раунда провести, не?

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    боюсь, что сложность задач квалификации не позволит.

»
11 дней назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

Лучше б сделали контест со всеми задачами, как в прошлом году.

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    10 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to solve D and E?

    • »
      »
      »
      10 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      10 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        10 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          10 дней назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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).

  • »
    »
    10 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    How to solve C, E ??

    • »
      »
      »
      10 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

    • »
      »
      »
      9 дней назад, # ^ |
      Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится

      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

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

thanks cf

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
10 дней назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

it is rated for div2.

I have 1900+ rating.

Is it rated for me or not?

»
10 дней назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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

»
10 дней назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

Perfect time for Chinese users!

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Очень нужно переделать объявления:

В русском несоответствие рейтинговый для второго дивизиона — с рейтингом менее 2100.
В английском просто рейтинговый для второго дивизиона.

В чем истина? Или 1900-2099 это уже Div2?

  • »
    »
    10 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Это всё еще див1, но для таких людей див2 раунды рейтинговые. Это нововведение появилось вместе с последним крупным обновлением.

»
10 дней назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

It Was So long time.

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

8000+ contestants

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Solved 2 problems for the first time

»
9 дней назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

queue

»
9 дней назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

»
9 дней назад, # |
Rev. 3   Проголосовать: нравится +33 Проголосовать: не нравится

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.

»
9 дней назад, # |
Rev. 4   Проголосовать: нравится +22 Проголосовать: не нравится

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

Is it EnglishForces???

Is it Codespeed???

……

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

extend the round due to queue by at least 10 minutes

»
9 дней назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Неужели так трудно было написать в условии задачи С, что все значения a_i различны, а не во входных данных? Это было очень легко пропустить☹

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Прошу прощения, не подумали, но по-моему, входные данные являются такой же частью условия как и легенда.

»
9 дней назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

EnglishForces

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What's wrong with this solution for D? 42940213

  • »
    »
    9 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

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.

  • »
    »
    9 дней назад, # ^ |
    Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

    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];

»
9 дней назад, # |
  Проголосовать: нравится -66 Проголосовать: не нравится

please consider making it unrated

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Test case #6 of problem C? anyone.

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

test case 5 on problem d ?

»
9 дней назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Anyone has idea what pretest 7 for C is?

»
9 дней назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

this says editorial posted 3 hours ago

»
9 дней назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

i think cf started div4...

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Why i can't see another's solutions?

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

»
9 дней назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

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

    • »
      »
      »
      9 дней назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 дней назад, # ^ |
          Проголосовать: нравится +19 Проголосовать: не нравится

        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.

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

In F, for the test

1 100
1
1 200
1

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

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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)

    • »
      »
      »
      9 дней назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe I will become gree tomorrow...

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why pA with counting sort would pass...

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

»
9 дней назад, # |
Rev. 14   Проголосовать: нравится +61 Проголосовать: не нравится

The round just became worse... :'(

»
9 дней назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится +136 Проголосовать: не нравится

»
9 дней назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

RATED PLIZZZ

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Rated Rated Rated xD

Give me back my purple <3

»
9 дней назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
»
9 дней назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится
»
9 дней назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

WTF?

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

When somebody being a candidate master and can edit tags.

![ ]()

»
9 дней назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

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.

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :(.

»
9 дней назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Спасибо авторам за задачи! Скажите, пожалуйста, будут ли доступны все задачи квалификации на этом сайте? Если нет, то где тогда можно будет их дорешать?

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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... :(

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
9 дней назад, # |
Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

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?

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 дней назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 дней назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

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.

  • »
    »
    8 дней назад, # ^ |
      Проголосовать: нравится -14 Проголосовать: не нравится

    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.

»
8 дней назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Easiest F I've ever seen

»
7 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
5 дней назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

А остальные 6 задач из квалификации будут в виде контеста или тренировки? + их разбор

  • »
    »
    5 дней назад, # ^ |
      Проголосовать: нравится -55 Проголосовать: не нравится

    Нет. Саратовцам же это невыгодно. Вдруг их кто-то решит и получит какие-то знания? И так на весь южный подрегион спалили.

    • »
      »
      »
      4 дня назад, # ^ |
        Проголосовать: нравится +55 Проголосовать: не нравится

      Вас, конечно же, не волнует, что с заливанием тренировки могут быть некоторые проблемы, Вы, конечно же, считаете, что эти злые саратовцы жадничают и не хотят делиться своими задачами! Но мне кажется, что Вам просто хочется оставить очередной язвительный комментарий по поводу каждого произошедшего события. Но смею вас заверить, что как только проблемы будут решены, тренировка появится на Codeforces.

      • »
        »
        »
        »
        4 дня назад, # ^ |
          Проголосовать: нравится -57 Проголосовать: не нравится

        Спасибо, что хоть в четверг ответили.