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

Автор Gol_D, история, 21 месяц назад, перевод, По-русски

Привет! В 10.07.2022 17:35 (Московское время) начнётся Codeforces Round 805 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, MisterGu, myav, Vladosiya, Aris, senjougaharin и мной Gol_D.

Также большое спасибо turmax, ivanz, antonis.white, Ronnie007, okwedook, oversolver, Kavaliro, antoshkin, omikad, yorky, Jostic11, Ziware, Kniaz, andrey.starodubtsev, Spaggetti
aniervs за тестирование раунда и весьма полезные замечания.

Всем удачи!

UPD: Разбор вышел!

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

»
21 месяц назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Auto comment: topic has been updated by Gol_D (previous revision, new revision, compare).

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Gol_D (предыдущая версия, новая версия, сравнить).

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

aniervs Chad <3

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Excited. Hopefully I will solve problems and learn many things form this contest. Thank you for organizing this contest.

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

Eid Day contest for South Asians! <3

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

Hoping that I can get out of gray tomorrow...

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

Eid Mubarak to evryone.

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

Very excited! Hoping to get a positive delta!!

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

EID MUBARAK!

»
21 месяц назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

First div 3 on a weekend since July 10,2021 (exactly 1 year ago!)

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

I like div.3 !!!

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

It's going to be fun solving doing #803 problems !!!

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

what topics to expect in problems C to D?

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

Is div3 harder than div2 or eazier?

»
21 месяц назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Where are the "as a tester, blah blah blah" comments? Lol. Good luck guys!

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

There was a time when div3 was unrated for me )

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

fighting!!!

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

Very exited for speedforces for div 1 participants..

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

wish to be blue today :D

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Specialists are least worried of their rating drop today, bcoz they hav div 4 coming soon to rescue in that case.

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

nice

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

my rating is less than 1600, still, it is showing unrated for me. why?

»
21 месяц назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Round 805 — cout << (ok ? "YES" : "NO");

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

E seems so easy , but not able to get Accepted :( . Frustration

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

Easier div3 but problems are also nice :p

»
21 месяц назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For G2 what do we need to pre-calculate.

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

      yes I thought about that but was not able to figure out actual process to solve query, I mean what to look for in the queries.

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

        First, convert the tree into a rooted tree.

        Let $$$d_i$$$ be the depth of a vertex $$$i$$$, and $$$u$$$ and $$$v$$$ be two vertices where $$$d_u <= d_v$$$.

        For each $$$(u,v)$$$ pair, there are two cases:

        Case 1: $$$lca(u,v) = u$$$ : This means that you are going "upwards" in a straight path and the path never goes down.

        1

        In this case, as long as $$$lca(u,v) = u$$$ is true, we are going upwards and every vertex is in the same path.

         

        Case 2: $$$lca(u,v) = x$$$ : This means that the path is not a "vertical" straight line. It has broken into two paths from vertex $$$x$$$.

        2

        Now, it is clear that every new vertex $$$y$$$ must exist within the shortest path from $$$u$$$ to $$$v$$$. Otherwise, the set is not passable.

        The vertex is present in the path if and only if:

        1. $$$d_y > d_x$$$ or $$$y = x$$$ ($$$lca(x,y) = x$$$)
        2. $$$y$$$ lies between $$$u$$$ and $$$x$$$ ($$$lca(u,y) = y$$$) OR $$$y$$$ lies between $$$v$$$ and $$$x$$$ ($$$lca(v,y) = y$$$)
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hey, I was seeing your G1 code, but not able to understand what you doing in the dfs func..coud you pls explain briefly? thanks

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

Although I didn't perform very well, I enjoyed the contest.

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve E?

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

    Just use dsu. If cycle of odd length exists then the answer is NO.

  • »
    »
    21 месяц назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    I did it with 2SAT using Kosaraju's SCC algorithm.

    Edit: Easy first check: Make sure no domino has the same number (e.g {3,3}) and no number is in more than 2 dominos ({1,2},{1,3},{1,4} since 1 appears 3 times).

    Next, for each domino $$$i$$$, define a variable $$$x_i$$$ for if $$$x_i=true$$$ set domino $$$i$$$ in set 1 and $$$x_i=false$$$ to put it in set 2. Then for each two dominos $$$(i,j)$$$ that intersect ($$$O(1)$$$ per domino because of the checks above), add the 2 sat constraints $$$(x_i\lor x_j) \land (\lnot x_i \lor \lnot x_j)$$$. Then there is a valid satisfiability if and only if $$$x_i, \lnot x_i$$$ do not exist in the same strongly connected component.

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

    Bipartite graph knowledge is needed to solve it.

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

      Could you pls explain a little more..I know bipartite though...but i cant get that if a domino is {1,2} are we taking 1->2 as edge? if yes, then how we are partitioning them as they would come together in 1 set?

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

        Each Domino is a node. And edge is when 2 dominos have a common element like {1, 2} and {2, 3}. Then basically we do graph coloring like assign Red color to node A and recursively assign Blue to all its neighbours since they cant be in same set. While doing this we are dividing the big set into 2 sets. If during recursion, the neighbors have same color : recursion fails and graph is non-bipartite and we cannot divide the big set into 2 sets.

        Hope it clears things++

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

    Bipartite Colouring

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

    check if all the connected components in the graph formed by (ai, bi) as edges are bipartite, and also make sure that the degree of all nodes is at most 2

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

      I just checked for degree of each node and the number of nodes in each connected component should be odd and it works fine no need for bipartite.

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

Problem G2 had appeared in CodeChef July Long 2021 K Path Query

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

I hate E.

»
21 месяц назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Problem F: ABC254-H

»
21 месяц назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Problem G can be found on Codechef — submission

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

    No wonder I submitted my exact Code from long challenge without even touching it 1 bit and everything passed xD.

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

i got the desired output for question d and i am pretty confident that the logic is correct as well but in test 1 it showed an unexpected error "wrong answer Line [name=s] equals to "aa ", doesn't correspond to pattern "[a-z]{0,200000}" (test case 1)", i don't understand what this is, please tell me where i am wrong or if this is an issue on your end please fix it, here is my submission https://codeforces.com/contest/1702/submission/163545146

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

Really know little about string....I can only use the STL thus then I failed C and D while my code is ok on the test set x<

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
»
21 месяц назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

YesNoForces

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Solving E:

  1. Ahahahaha easy question, not fit for E; Writes code using set stl;... Wrong answer test (2)
  2. wtf??? Think think think... Finds that ordering matters; Anguish

LOL, even after that I found a viable solution using graphs and cycle detection (any odd cycle detected = NO) else true. Graphs are not simple; but i kept them undirected ...But then the contest finn (more anguish)

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

    I also solved E using set and got WA on test 2 but cannot figure out any counterexample can you please explain a counterexample where set fails.

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

      {{1,2},{3,4},{3,5},{2,5},{4,6},{1,6}} We can partition as {{1,2},{3,5},{4,6}} and{{3,4},{2,5},{1,6}}. But your code will give NO

»
21 месяц назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

In B, I would have been happy to read something like "Poly does not remember letters from previous days". Or at least having a sample from that this detail would become clear.

In E it would have been helpfull to have an example of two dominoes that must not go into one group, like "if there is an domino {x,y} in one group, not other dominoe with x or y can go into the same group". Instead there are positive examples only, and no formular description.

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

    Agree B...however didnt quite get you for the E one... I think there was an announcement too about this... Also, if anything they could add as a visible testcase, it could have been an example where changing the order of queries/dominos would result in a switch between NO/YES.

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

      The phrase "all numbers on the dominoes of a set are different" was unclear to me. After having that read, I asked if {1,2} is same domino as {2,1}, which shows that I completly did not understand what was asked for.

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

why a greedy method will fall for E? If no dup in set1, put in set1, if no dup in set2, put in set2. Otherwise, output No.

163580026

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

    That would fail for a case like: (1 2), (3 4), (3 5), (2 5)

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

    Consider these pairs for N = 6 2 5 3 1 4 1 4 2 5 6 6 3

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

    1 3

    1 2

    2 3

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

    {{1,2},{3,4},{3,5},{2,5},{4,6},{1,6}} .By greedy method you will insert 1 2 in fisrt set then 3 4 also in first and 3 5 in second .After that you can't insert 2 5 in any of the two. But we can partition it as {(1 2)(3 5)(4 6)} and {(3 4)(2 5)(1 6)}

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

Did anyone have a prediction for 0 rating changes? I had on this round)!

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

Although I now hazily see that I should have used dsu for problem E, I don't clearly understand why my greedy approach wasn't accepted: 163579353

I can't see what kind of test case rendered it wrong since it's 6930th one down in the abyss. Can anyone raise an example?

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

well problem c was confusing for me.

Let us say for the test case:-

1

4 1

1 2 5 1

5 2

we can go from station 5 to 2 because we can go from 5 to 1 and then 1 to 2. So Answer should be yes.

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

    It does not work like that. The train goes from 1 to 2 only in the first appearance of station 1, but going from 5 to 1 happens in the second appearance of 1.

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

wtf is with place 19?

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
void solve() {
        string s;
        cin >> s;
        ll p;
        cin >> p;
        vector<ll> mp(26, 0);
        ll w = 0;
        for (auto &i : s) {
                ll t1 = i - 'a';
                w += t1 + 1;
                mp[t1]++;
        }
        vector<int> pq;
        for (int i = 0; i < 26; i++) {
                if (mp[i] == 0)
                        continue;
                pq.push_back(i);
        }
        ll o = w - p;
        sort(pq.begin(), pq.end());
        int j = pq.size()-1;
        while (j >= 0 and o > 0) {
                ll val = pq[j];
                o -= val + 1;
                mp[val]--;
                if (mp[val] <= 0) {
                     j--;
                }
        }
        string res = "";
        for (auto &i : s) {
                int t1 = i - 'a';
                if (mp[t1] > 0) {
                        res = res + i;
                        mp[t1]--;
                }
        }
        cout << res << endl;
}

Can anyone point out why this gives TLE on test case 6. I think the complexity is O(nlogn) at max and it should work. It would be of great help if anyone could point to what i am missing.

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great job on this round but we're still waiting for the tutorial hope it comes out fast also I want to ask problem E can it be solved using two sets and if not why

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

Why is this failing, Problem (E)
Bipartite coloring is used
Code
Thanks in Advance

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

G2 is exactly the same as CodeChef KPATHQRY.

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

    I understand that we find the endpoints of a possible simple path by sorting the k vertices of a query by depth. But how does it work to check if all other vertices are on the simple path between them?

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

      You can check it using distance. Lets say your endpoints are $$$l$$$, $$$r$$$ and you want to check if vertex $$$u$$$ lies on the path. Then $$$u$$$ must follow,

      $$$dist(l,r)=dist(l,u)+dist(u,r)$$$
    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      epsilon decribed quite an elegant method but you can also do it with binary lifting/hld:

      1. Mark all relevant ancestors of the node with the lowest depth (First endpoint).
      2. Mark all relevant ancestors of an Unmarked node with the lowest depth (Second endpoint).

      A simple path is only possible if all given nodes (except their LCA) has been marked exactly once.

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

Hi everyone , can any explain why I'm getting wrong answer 163558459 I will go crazy ;) ... The idea is to make a map for first and another for second set , and see if (the numbers duplicated in the first and the second)-> NO else it's gonna be the answer -> YES

Is this all there is in the question, or is there more?

  • »
    »
    21 месяц назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    I did exactly the same as you and we were trapped on the same stumbling block (6930th in 2nd test case). An example is that, n = 6, {1, 3}, {2, 3}, {4, 5}, {2, 5}, {4, 6}, {1, 6} leads to "NO" whereas it should actually output "YES"

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

This round is rated for me but in normal case it should be unrated. Can anyone tell me what's wrong?

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

Any hints from problem $$$F$$$ ? For any $$$b\in B$$$, I can generate $$$reach(b)\subseteq A$$$ that $$$b$$$ can reach in $$$A$$$ after a number of operations. I don't see how to do the matchings greedily though (which I am assuming is the idea)

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

    Note that a multiplication can be reversed. So it is an aequivalent problem if we divide all a[i] until all of them are odd.

    Then it is greedy, match all b[i] to the biggest possible a[j], by try/devide/try/devide/... until b[i]==0. If no match is possible then ans=NO.

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

      Thanks, AC, that's an elegant solution :).

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

      why till odd can you elaborate more, please? like a proof or something I am unable to get intuition.

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

        Because you can generate all the powers of 2 from '1' in the second array. So only the odd factor in the first array matters. After that for every b[i], keep dividing by 2 until you reach an element present in a. If b[i] becomes 0, then at least 1 element from a will always remain unmatched

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

        All multiples of a number x with powers of 2 build an aequivalence set. Because we can devide these numbers to come back to the first number, the odd one.

        This means, after reducing all numbers in a[] to that root value of their aequi-set, each number in b[] can be matched with only one given odd number in a[].

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      I am starting the solution as you mentioned, i.e. reducing all A[i] to their respective odd values. But, if I try to match each A[i] to the smallest possible B[i] my solution fails. I tried to generate a counter-test case but wasn't successful.

      Can you tell me why you tried to match B[i] -> to biggest possible A[i] instead of A[i] -> to smallest possible B[i]

      My Code
      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Actually we do not match the a[i] with the smallest b[j], but instead the b[j] with each biggest possible a[i].

        Consider we have in a[] after divisions some numbers: $$$( ...,3, 7, 15, ...)$$$

        Now see if we can match a b[j] with the 15, we can also match it with the 7, and also with the 3. But the other way it does not work. A b[j] that can be matched with 3 does not automatically match the 7 or 15.

»
21 месяц назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

All the hacked solutions from this contest are in problem C using PyPy3 or python even though they have the same logic as accepted solutions from other languages. Maybe its because of slow input or slow dictionaries in python. Anyways, python should have more time to pass.

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

    No the issue is with the hash , which leads to o(n^2)

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

      Yes, in worse case: python dictionaries use hashing, and too bad there is no such thing as a Binary Search Tree (TreeMap in java and map in c++)

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

Can anyone share the test case of C, thanks in advance!

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

Why are so many python solutions of O(n) time complexity for Problem C getting hacked ?

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

Can someone say how to solve C without hashing, bcoz my solution using dictionaries got hacked. Or is it fate of Python Users :(

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

Nuu

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

Very very bad situation for python coders..... really annoying to see same logic got hacked in python (C question)... its now time to leave codeforces... thank you codeforces community....

»
21 месяц назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Can we increase the time limit of problem C for Python? It seems like a lot of the Python solutions are getting hacked yet most of the logic is the same as other languages.

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Moment of silence for those hacked on c

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

have solved till E but for C i will loose around 100 rating .... its very unfair.... time limit should be increased for python... and Hacked solutions should be reevaluated for fairness or this contest should be unrated ...

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

    Could you please tell how you did E? thnks

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Solved it by first counting degrees of every node if any node degree is > 2 then return False ... Else also see that any kind of odd cycles are not allowed ...like (3 4) , (4 5) , (5 3) will not fit in 2 sets.... but even length cycle will fit in 2 sets like... (3 4), (4 5), (5 6), (6 3) **** set1 = (3,4) , (5,6) set2 = (4,5) , (3,6) **** so we have to check weather there exist any odd length cycle.... to check this we check if the graph is bipartite (if you dont know about bipartite graph...its kind of graph which devides the vertices into two sets so that and there will not be any odd length cycles...) To check for bipartite just run BFS with coloring ....you can see my code here **My solution : 163566318 ******

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

        Thank you so much. I understood your explanation very clearly. Amazed how you thought of the same, I could never :), though I knew bipartite beforehand.

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

Was anyone able to solve F with bipartite matching?

I tried to use straight-up Dinic's as a last ditch effort and it didn't work out. Ah well.

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

can someone tell me how get the editorial of this or past contests

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

I did what appears to be something different to the norm for G2. Here is my approach.

(0. If K <= 2, obviously the path is good.)

  1. Find the LCA of adjacent pairs of nodes in the list. It is guaranteed the the LCA of all nodes will be among these values, and that it will be the value with minimum depth.

  2. A simple path visiting all nodes must pass through the LCA (possibly as an endpoint only), and there can be at most 2 simple paths extending down from the LCA (i.e. joining at the LCA).

  3. Now for all nodes other than the LCA (if it is even one of the nodes), partition them into two possible paths by taking the LCAs of the adjacent pairs, and if that LCA is the overall LCA they are on different paths, otherwise they're on the same path.

  4. Sort the two candidate paths by depth.

  5. For each pair of adjacent nodes, check the LCA — if this is a simple path ordered by depth, then the LCA must be the node with lower depth. If not, the answer is NO.

  6. If all these conditions are satisfied, the answer is YES.

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

    I did almost the same, but a bit simpler:

    • your second point
    • sort points by depth in reverse order. If there is more than two points with same depth, no
    • let's build these two paths: next vertex u connects to path p iff lca(u, p) == u
    • handle case when you can connect vertex to both paths (it must be last vertex)
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what graph topic was problem E?

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

    If you treat each index as a node and create an edge between nodes with common numbers (including possible self-edges), then a partition is possible IFF you can black-white colour the graph such that no adjacent nodes are the same colour.

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

It doesn't make sense to penalize correct Python submissions with efficient time-complexity. I mean, one cannot use Python in Codeforces unless we write our own hashing function and map class? It's absurd. And if this continues, I expect all Python users to migrate to another platform.

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

In problem C last sample testcase

testcase

why is 1 3 answer as NO? Its clear that we can go from 1 to 3 while going from 1->2->4

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

    Because of unordered map.

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

    Just by using the normal map and you will get Accepted

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

    I also used unordered_map in c++ but my code got ACCEPTED. Can you point out the reason? My submission https://codeforces.com/contest/1702/submission/163500607

    Failed in System Testing

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Already answered in icy's comment. Hashes(outputs of hash function) are bound to collide unless they are randomly distributed.

      In short, It is possible to have all hashes collide deliberately if the hash function is known.

      e.g.
      key: "foo", val: 123 -> HashFunc("foo") -> hash: 0xdeadbeef 
      key: "bar", val: 567 -> HashFunc("bar") -> hash: 0xdeadbeef -> collision!
      key: "baz", val: 890 -> HashFunc("baz") -> hash: 0xdeadbeef -> collision!
      

      Upon collision, the unordered_map iterate buckets for the hash and this results in O(n^2) at the end.

      This does not happens in STL map, a red-black tree, that guarantees O(logn).

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

People who ask for increased time limit for python because of hashhack annoy me even more than falling for this hack. That's so stupid when it comes from people above gray

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

if you like this contest print "YES" otherwise print "NO"

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

Solutions to the interesting problems:

Problem F

Say we have our two multisets $$$a$$$ and $$$b$$$.

Firstly, notice that we can keep dividing elements in $$$a$$$ until they are odd and likewise keep dividing elements in $$$b$$$ until they are odd. This doesn't change our answer. Now we can simplify the problem and only consider the operation in which you divide elements in $$$b$$$ by two (there is no point in multiplying them by two anymore...).

  • If the largest element in $$$a$$$ is equal to the largest element in $$$b$$$, then we know that we can remove the largest elements in $$$a$$$ and $$$b$$$ without changing our answer. Then recurse downards.
  • If the largest element in $$$a$$$ is smaller than the largest element in $$$b$$$, then halve the largest element in $$$b$$$. Then recurse downwards.
  • If the largest element in $$$a$$$ exceeds the largest element in $$$b$$$, then we can proceed and we can print "No" by default.

Problem G

Find the "diameter" of the path. Basically, for any path we have these two "leftmost" and "rightmost" vertices which sort of define the path and then a bunch of points between those vertices. We can find the diameter of the path by first finding the deepest node and then finding the node that is farthest from the deepest node (similar to how you find diameter of a tree...). Call these points $$$x, y$$$. Then, the rest of the problem reduces to figuring out if the other points lie between $$$x$$$ and $$$y$$$, which is a standard problem.

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

My submisson: 163602507 Problem E. Does anyone know of a case that went wrong?

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

It's now 5h before the final standings and why it says the round is unrated for me?

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

    It's said that one must attend at least 5 contests and submit at least 1 problem in each contest before he or she is able to attend rated div.3

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

In E,
The observation that I got to was that each number can be paired with at most two othet numbers. Also , to appropriatly divide them in two sets, there shou should not be any cycle of odd length, but I got WA again and again. Where did i go wrong?

Edit : Submission https://codeforces.com/contest/1702/submission/163572445

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

    Everything is OK, except one mistake in implementation. In string 16, what is "len(a) > 2 or len(b) > 2"? a and b are not initialized here. Instead of this, you should write "len(i) > 2" and you will get OK.

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

      I had it in above line but I didn't know how did it came here.

      Thanks man,
      You killed my Imposter Syndrome today

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

Would the datas which were used to hack others' codes successfully be tested for everybody after the HACK is closed? I was trying to hack someone's code but I submitted a wrong data, but I'm sure his code will lead to Time Limit Exceeded. lol, then I hope others' hacking datas would hack this bro's code.

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

I am always dreaming of AK the div3

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

Contest Must Be Unrated ... as many python coders unnecessary got hacked... it will be unfair to them...

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

    Can you explain how did it happen?

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

    That's an interesting usage of "unnecessary". I think you define an "unnecessary" hack as one that you do not want to see.

    However, in real life the defintion is more simple: If your solution can be hacked, then it will be hacked. So it is your responsibility to provide an unhackable solution.

    I think that might be sometimes more hard in Python than C++, but nevertheless, you are free to choose. And in this case, why you do not have a template implementing a not-hashcode based structure usable as a map? Or use one with a custom hash code?

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

The tasks were very interesting

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

My approach for problem E (Without using Graphs/tree/dfs/dsu)

Travel in all pairs and check for ith pair

If you can't put the ith pair in set 1 and set 2 both then : NO

If both numbers in pair is same then:NO

Else If we can't put ith pair in set 1 then put in set2

Else If we can't put ith pair in set 2 then put in set1

THE MOST IMPORTANT : If we can put ith pair in set1 and set 2 both then Leave that pair for now.

If all the remaining pairs can be placed in set 1 or set 2, put 1 pair of those remaining pairs in set 1 or set 2 and repeat this process again and again until all pairs are placed in set 1 or set 2

CODE?
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I had a question about the sentence” If we can put ith pair in set1 and set 2 both then Leave that pair for now.” Why I can’t choose any set and add the ith pair in. Can you make a case for why this way isn’t correct? Thanks

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

      such as (1,2)(6,4)(3,4)(6,5)(1,5)(2,3)

      if you choose (1,2)(6,4) into first set, then WA

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

      i have done the same before, but i got WA on test 3 . think about that {(1,2),(3,4),(2,3)} (i know ai,bi<=n .but for understanding take this example)

      if you put first pair in set 1 , second pair in set 2 then you will get NO because you will not be able to put 3rd in any set. but correct answer is yes.

      so we try to put all pairs that can't put in one set in second set. after doing that we will put 1 pair from remaining in any set.

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

    sad to say, seems to get tle on some cases. suppose input is (1,2) (3,4) ... (n-1,n) (1,2)(3,4) ... (n-1,n) every pair can fit in both sets, and if you choose (1,2) into the first set, the only step your method can do is add another (1,2) into the second set, and have to loop again and again.

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      constraints: ai,bi<=n i think that we will never get such cases

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

        i don't think the case break the constraint let n = 100

        first 50 pair are (1,2) (3,4) ... (99,100) last 50 pair are (1,2) (3,4) ... (99,100)

        isn't it

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

          you are right , for your test case time complexity is O(n*n), that leads to tle for sure.

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

Why can't my code?
Why is this question E used Kruskal? Can you look at my code?thanks. linK:https://codeforc.es/contest/1702/submission/163631990

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

    I'm not sure that Kruskal is needed, I think any valid set of nodes either needs to be a path or an even cycle.

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

Your code here... void helper(){ int n, m, k; cin>>n; vector<pair<int, int>> arr(n); cin>>arr; //cout<<arr<<endl; unordered_set<int> a, b; for(int i = 0; i<n; i++){ if(a.find(arr[i].first) == a.end() && a.find(arr[i].second) == a.end() && arr[i].first != arr[i].second){ a.insert(arr[i].first); a.insert(arr[i].second); } else{ if(b.find(arr[i].first) == b.end() && b.find(arr[i].second) == b.end() && arr[i].first != arr[i].second){ b.insert(arr[i].first); b.insert(arr[i].second); } else{ cout<<"NO"<<endl; return; } } } cout<<"YES"<<endl; }

why does this code show wa on some cases?? what is wrong with this idea ?? Question E dominoes

whole solution link 163531383

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

Why use unordered_map in problem C will TLE but map will not ?

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

What is the algorithm used in E as i tried to solved it using greedy approach but getting wrong answer on test 2 my solution-> https://codeforces.com/contest/1702/submission/163556344

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

Hi everyone, I want to ask about pE the input after n contains 2*n lines, and each line has two numbers. Is that means in legal cases all the numbers from 1~n only appear two times? Thanks!

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Why aren't they starting system testing?

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

My rating hasn't changed yet, is there a problem with my account or it is just a general case?

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

    It's normal. Ratings will be updated today but may be not in the morning.

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

    General case, also hacks are opened for more than 12 hours as of now. This is not what they claimed in the announcement.

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

      Hacks after the 12 hour mark don't affect system tests. Successful hacks after the designated time are there to strengthen tests for practice.

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

I think having test cases which gives TLE on using unordered map should be avoided (happened in C for this contest). The question should get accepted based on the concept used and not on the data structure.

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

    Lol... competitive programming is meant to increase understanding of data structures. You should learn from this incident the difference between ordered map and unordered map.

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

      I think getting the right logic is more important. If it is meant for understanding the data structures, I would rather practice on leetcode or gfg than codeforces. Everybody knows the difference between the two data structures, we can even use unordered map with a custom hash function but the question is of the greedy concept and not the unordered map / ordered map

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

        As a competitive programmer, you're expected to think about the worst case complexity while writing logic. And the testers seem to have the same opinion too. There are questions where you get TLE because you used cin cout without the fast I/O modifications, or because you forgot to pass vector as a reference to a function. You're expected to know this in cp. You might find the information on GFG and LC but you actually get to see its impact when you're solving such questions.

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

          Yeah I agree with you on the point of analysing the worst case complexity, but I was saying something different here. The question is not dedicated to using unordered map / or any other data structure. The question can be done using other data structures as well without getting a TLE. The question is based on how programmer applies the greedy approach to get the right answer. Its like when you do everything right in a maths question and applying the right concept to solve it but did some calculation error at the end to get an incorrect final answer. Btw it is not happening with me for the first time xD. It was just like while trying to do the question as quickly as possible, I didn't noticed that I was using an unordered map with integer key which has a pretty high probability of giving a collision. Anyways, whatever done cant be undone, was just sharing my views

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

            Well you cracked the logic right? The only thing that you lost is rating. As long as that's not a concern, this shouldn't bother you. If it is a concern, you'll remember it the next time you see a similar question. Win-win for you, cheers!

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

I noticed that many people are trying hard to get a rating. But sometimes, you just need to enjoy the round. I passed the first 4 tasks, read 5 and 6, and realized: I can pass them, but why take them? I have freed up time, and I can spend this time on really worthwhile tasks: G1 and G2. They seemed interesting on first reading. And so I even passed one of them. In general, the round is very cool, especially G1 and G2.

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

is 805 insecure?! Why so many hacks lol.

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

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

Can anybody explain why my submission 163494875 of Problem 1702C - Train and Queries failed on SysTest? I got robbed of a 3 digit rank sadly. I have always used maps and sets which have a complexity of logarithmic order. I can't understand the reason.

Thanks in advance :')

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

    ++
    I got TLE on test 44 in the final tests and I don't know why, this is my solution.

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

    You don't have to store all positions of the occurrences of a number, the first pos and last pos would be enough. Consider the following case:

    1 4 6 1 3 1 1 8 9 3

    Queries:

    1 3

    3 1

    Here you just wanna know when the 1 first appeared (index 0) and when the 3 last appeared (index 9). You do not care about any other pos. Since index of b > index of a .:. ans = Yes

    Consider the second query, here 3 appeared first at index 4 and 1 appeared last at index 6, therefore this is also a yes.

    Think of making a map that has the number as its key, and pair of integers as its value (first_pos, last_pos). and just see if last_pos(b) > first_pos(a), if so print YES otherwise print NO.

    Hope that helped :)

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

      I know this solution. I was asking about the problem in my code. Thanks anyway, I got it.

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

how to solve problem E with DSU? like tourist

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

Damn one of my solutions was hacked. First time I managed to solve 4 problems

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

    Sad :( At least you've learned not to use map instead of unordered_map next time.

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

      why would map be better in this situation?

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

        As I have understood, the hashing function of unordered_map is not as good as the one in map. It causes collision when big random numbers are stored in it, so to avoid this collision, the time complexity goes from O(1) -> O(n) which is way too bad, as it cause tle.

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

          you're a bit wrong std::map has no hash function at all — it's based on the red-black trees, which gives you a guaranteed(!) O(log(n)) complexity, but unordered_map is based on hashing, and, as a lot of people know, what is the hash function inside of it, unordered_map can be easily hacked. Of, course, you can determine your own hash function to avoid hacks (read this https://codeforces.com/blog/entry/62393), but it still can be blown up somehow

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

I tried to solve E using some intuition.

Firstly if there is a number which frequency is greater than 2 then the answer is NO. Secondly if a domino contains two equal number then the answer is NO. Thirdly if there is a number X, then surely there are exactly two dominos where the number X is written.

Our goal is to divide such two dominos where X is common. Now we assume that we can divide these two dominos then there will be X common number and another two or one number. Ex: (1 2) (1 3) (2 4) (3 4) if we put (1 2) in one and (1 3) in other then X = 1 and other two numbers are 2 & 3. or (1 2) (1 2) if we put (1 2) in one and (1 2) in other then X = 1 and other one number is 2.

Now if the division is correct then rest of numbers must not written on same domino. If so then the answer is NO. ex: (1 2) (1 3) (2 3) (4 5) (5 6) (5 6) here if we put (1 2) in a set and (1 3) in other set then (2 3) must be written on two separate dominos, but (2 3) is written on same domino so we can not divide them.

But the solution is now working and I could not find any counter case so far.

My solution getting WA in TC:4 : Solution

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

    try this 6 (1 3) (2 3) (4 5) (2 5) (4, 6) (1 6) (the answer is YES)

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

      getting YES

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

        hm.. seems like there is no testcase which kills your solution with n <= 10 — i tried to stress test and found nothing i will increase n to 20 and try again

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

        i've found it! n =28

        19 5 7 20 17 1 13 23 13 20 26 11 10 26 12 27 27 17 1 25 16 19 23 22 8 16 3 15 8 7 21 18 15 28 14 25 12 18 4 2 3 24 21 28 2 4 10 24 9 6 22 5 9 6 14 11

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

        or, if it will be better for you, i can attach this: your solution yields yes, but the correct one yields no

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

Когда будут именения рейтинга?

»
21 месяц назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

When will the editorial be uploaded?

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

Where should I complain about my problem (C) in a contest(Div 3 #805) being mistakenly marked as time limit exceeded in the system testing period. Other peoples having code of the exact same(or even more) time complexity has been passed. :'(

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

    Never ever use an unordered map. Sure, its average time complexity is O(1) but the worst time complexity is O(n). Because of that creators (or hackers) make special tests trying to reach the worst time complexity, and your solution fails. Always use a map.

»
21 месяц назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

How long does it take to increase the rating???

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

How long does it take to increase the rating?

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

F is an original question! Link: https://atcoder.jp/contests/abc254/tasks/abc254_h

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

In a general div 1 or div 2 contest the change is rating occur just after because of no hacking round in them. While in div 3 contest there is a 12 hour hacking round and after that there is a 3-4 hour system testing, and within a day the rating got update but why is it taking soo much time in this contest? Can somebody please mention the reasons behind this.

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

If somebody solved E using DSU, pls share your code.

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Here
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    See tourist's code

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

Argh..... Not got the rating yet,how much more would you like to delay

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

How can we get to know that the contest has become unrated? Is there any announcement or they just don't update the rating ?

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

I m expecting to become specialist in this contest but as the ratings haven't been updated yet and so i eligible for next competition that is div4 will i be able to participate in it or not after the rating changes have been reflected?

p.s. some1 said something about this contest not being rated!!! that will be really cruel!!!ratings just show up w8 is agonizing

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

    Round has become unrated for everyone, you can check under the contests section, apply the filter as only unrated then you will see it there, I guess they made it unrated because F and G both were exactly found on atcoder and codechef , so a lot of people might have copied it, and also these are the last problems so solving them really matters a lot to the ratings. Also soon the editorial might get posted, saying the same about the contest

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

Why isn't it rated for me though i have 953 rating?

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

When will be rating changed? I have to register in Div. 4

»
21 месяц назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
**how are these two ratings calculated**

pic

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

Can anyone how to solve E using disjoint set union?

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

Why is greedy solution not working for E?

»
21 месяц назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please help me understand this solution to problem E? I know that checking for bipartiteness does the trick, but this solution seems new and interesting (no offense intended)

The thing that I understood (not concretely) are (and please correct me if I'm wrong):

  1. The nodes x and x+n represent the same node
  2. If a node in (1...n) is connected to a node in (1+n....2n) [either directly or indirectly] then the number of edges must be odd
  3. If x is connected to x+n then there is a cycle (starting from x and ending at x, because of point 1)

I don't understand why:

  1. Take 2 * n size of dsu, (obviously, I understand that doing dsu.find_set(x) == dsu.find_set(x) is useless)
  2. Connecting x to y+n (is it to make the number of edges between nodes odd? because If a node in (1...n) is connected to a node in (1+n....2n) then the number of edges must be odd)
  3. Connecting both (x to y+n) and (y to x+n) (is it because to make it undirected),

I am unable to concretely understand the idea behind it. Can someone please help me out here?

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

    Forget the +n, it is confusing, and doesn't add anything to the reasoning. Just pretend there exist two nodes, k and k'.

    Note first that there are no nodes with degree > 2.

    For any edge u,v, we connect u -> v' and v -> u'.

    Suppose there existed a cycle say 1 -> 2 -> 3 ->...n -> 1.

    For any edge i,j there exists i -> j' and j -> i'.

    Therefore, the following paths exist

    1 -> 2' -> 3 -> 4' ... odd -> even'

    1' -> 2 -> 3 -> 4' .. odd' -> even

    Note that every even element in the first cycle is even'. Therefore, if the cycle is odd, 1 and 1' exist in the same path, otherwise they don't.

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

Автокомментарий: текст был обновлен пользователем Gol_D (предыдущая версия, новая версия, сравнить).

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

About me using an LCA standard board to change, I hope to re-examine, I have no need to write G2, G1 first, and I submitted the same code for both questions, G1 did not check G2 but checked again, which is incredible I only 2000 people, in order to write this problem spent a lot of time, in order to score can be written from front to back, I looked at the code and found that the so-called check is the same, in addition to the board is almost the rest of the basic difference This is unacceptable LCA board should be the same on the whole network Ah Administrators are expected to re-examine

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

Can anyone of you please give a case for these submission?(problem E) https://codeforces.com/contest/1702/submission/163518238 And anyone please tell me what is that case( 2nd test ,6930th token )of problem E. Lot of people got WA in that case.

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

why this code is giving WA for question 1702 E. Split Into Two Sets :-

include <bits/stdc++.h>

using namespace std;

bool allVisited(vector &visited) { for(auto it:visited) { if(it==0) return false; } return true; }

void solve1(int n,vector<pair<int,int>> &v, vector &taken, vector &visited) { for(int i=0;i<n;i++) { if(!taken[i]) { if(!visited[v[i].first] && !visited[v[i].second]) { visited[v[i].first]=1; visited[v[i].second]=1;

taken[i]=1;
        }
    }
}

}

int main() { int t; cin>>t;

while(t--)
{
    int n;
    cin>>n;

    vector<pair<int,int>> v(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i].first;
        cin>>v[i].second;
    }

    vector<int> taken(n,0),visited(n+1,0);
    visited[0]=1;

    solve1(n,v,taken,visited);
    if(!allVisited(visited)) 
    {
        cout<<"NO\n";
        continue;
    }

    for(int i=0;i<=n;i++) visited[i]=0;
    visited[0]=1;

    solve1(n,v,taken,visited);
    if(!allVisited(visited)) cout<<"NO\n";
    else cout<<"YES\n";
}

}

kindly help me detect the edge case or anything else i am missing out in this code...