hogloid's blog

Codeforces Round #286
By hogloid, 10 years ago, In English

Hello Codeforces!

evima, yosupo and I would like you to participate in Codeforces Round #286. It will be held on Sunday, January 18th at 16:00 MSK. Please note that this round starts on unusual time.

Great thanks to Zlobober who helped us prepare this round, Delinur who translated statements into Russian and MikeMirzayanov who created Codeforces and polygon.

This is the 3rd time(following #162 and #263) for me, and the 1st time for evima and yosupo to prepare a Codeforces Round.

Scores of the problems will be

500-1000-1750-1750-2500 for Div.1, and

500-1000-1500-2000-2750 for Div.2.

In this round, you'll help a man named Mr. kitayuta. I hope he will participate :)

The system tests are now over! The top-5 are as follows:

Div.1:

1.ilyakor

2.kcm1700

3.LayCurse

4.RomaWhite

5.TankEngineer

Div.2:

1.Konijntje

2.cpcpc

3.zgzjsxshycxksxhsh

4.Ronnie007

5.sha384

Also, special congrats on Petr, who solved problem E in Div.1, which anyone else could not solve.

Here are the editorials

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

Comments Comments (214)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

Will there be Appleman again in this problemset? We all really loved this hero last time... Especially guys from Russia:)

Upd. Oh, i see now... So sad, we all miss Appleman. Hope to see him in your next round.

→ Reply
»
10 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Oh, great! The 'unusual time' is suitable for Chinese coders ;-)

→ Reply
»
10 years ago, # |
  Vote: I like it +38 Vote: I do not like it

This is the 3rd time(following #162 and #263) for me

Hope round #364 will be yours, too. :D

→ Reply
»
10 years ago, # |
  Vote: I like it +35 Vote: I do not like it

"this round starts on unusual time" = start time is 5:00 am here. :(

Seems I can't participate Chinese and Japanese contests anymore..

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    En.. If it is the 'usual time', it will be 00:00 ~ 02:00 in China ..

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    Maybe all competitive programmers should live in the same longitude :| Where is reasonable?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Maybe Arctic Pole / Antarctic Pole? It don't have a longitude (or say, have any longitude).

      → Reply
»
10 years ago, # |
  Vote: I like it -64 Vote: I do not like it

hello dis like me pls

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Score distribution already published. Thanks!

→ Reply
»
10 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Mr. Kitayuta has registered to the contest.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Facebook HackerCup is running right now... I thought this would be delayed to after Hackercup or something...

→ Reply
»
10 years ago, # |
  Vote: I like it -34 Vote: I do not like it

I can't join this round cause i have English class...

Why you don't define a specified time for contests? So we can planning for them...

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Maybe someone else would have an English class at another time :D

    But it's clear that this is for the problemsetters' convenience.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      I think this round has unusual timing because the usual would have clashed with codechef cook off, too less space between them

      → Reply
»
10 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Lets just hope this contest goes fine and rated. :)

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

Codeforces just changed it's logo to default. Codeforces changed it's logo to christmas.

→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I think It was so hard; no right submissions for E. 1 right submissions for D. 33 right submissions for C. Wasn't it?

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I'm solved Div1 D, but I'm too scared to submit it :D

→ Reply
»
10 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Tried to hack 10^8 complexity solution, but unsuccessful attempt, code runs in 540 ms, is that possible??

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, of course

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Codeforces is very fast you can use about 5*10^8 operations in 1sec.You probably talk about problem B (dfs-O(n^2)).You can't find tescase where you use 10^8 operations beacuse m(number of edges) is so small.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in second cf server can do more than 10^8 operations i think

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    10^8 is very fast. Sometimes even fast 10^9 works

    → Reply
»
10 years ago, # |
  Vote: I like it +28 Vote: I do not like it

What was the solution of A? :)

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +47 Vote: I do not like it

    Normal DP with F(i, j), where i is current position and j current jump length, but notice that j won't vary that much (~250).

    Edit: I came up with this in the last minutes. T_T

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you know that j won't vary?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If it changes more then 300 there has to be more then 30000 positions :)

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Not a formal proof, but this was my thought: Assume you have i = 0, and j = 1 and you increase the length after every jump. At approximately j = 250, you will jump over the 30000 mark.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can somebody tell me why this code got TLE? I used the same approach but recursive :)

        http://mirror.codeforces.com/contest/505/submission/9462104

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          AFAIU from your solution, you are caching only answers when jump length < 400. So if initial jump length was big (like 1000) you are calculating answers (for same input values) many times.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks for going through my code :) Will try to correct it tomorrow.

            → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had to do something wrong, probably everyone in DIV1 tried this, but for last test case the cache had almost 5M states...

      My code on ideone (but RE, because stack size is small)...

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +35 Vote: I do not like it

    Imagine the game is finished, and your final jump length equal to j. It can be proven, that |j - d| is . That's why you can write dynamic programming dp[position][|j-d|].

    UPD. The simple thought that can help you prove the fact. Imagine you start from the very start, and you have d=1. You cannot finish with large d, because almost equal to n.

    UPD2. Fix a mistake, thanks Svyat.

    → Reply
»
10 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Tasks beautiful, but very difficult, IMHO.

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

i couldn't even solve A. Shame on me :(

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Don't worry, 1364 registered for DIV1 and only 362 solved problem A :-D

    We all will be kicked out of the division :-D

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain to me how to solve DIV2 C ?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Argh, you could have been a little more generous with the time limit of div2c, a n^2 solution with unordered_map didn't pass, but could do any input on my machine in < 3s.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody here tell me why this code gets MLE?

#include <bits/stdc++.h>
using namespace std;

const int N = 1e2 + 5;

int parent[N][N];

int find(int c, int v) {
    if (parent[c][v] == -1)
        return v;
    return parent[c][v] = find(c, parent[c][v]);
}

void unite(int c, int u, int v) {
    parent[c][find(c, u)] = find(c, v);
}

int main() {
    memset(parent, -1, sizeof parent);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        unite(c, a, b);
    }
    int q;
    cin >> q;
    while (q--) {
        int u, v, ans = 0;
        cin >> u >> v;
        for (int i = 1; i <= 100; ++i)
            if (find(i, u) == find(i, v))
                ++ans;
        cout << ans << '\n';
    }
}
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Infinite reccursion. You don't initialize values of parent with parent[c][i] = i
    And in find:
    if(parent[c][v] =  = v)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I implement it using this approach:

      init:

      parent[c][i] = 1

      and in find:

      if(parent[c][v]==-1)

      initially parent of all vertices is -1 then in find (parent of a vertex with parent -1), is itself.

      sorry for typos, I'm writing with auto-correction using a phone!

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It will fail with this testcase:

    4 4 1 2 1 1 3 1 2 3 1 2 4 1 0

    You do not check if they are already in same component and the recursion never ends.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thx. I thought not ending of recursion causes Runtime Error instead of Memory Limit Exceeded.

      → Reply
»
10 years ago, # |
  Vote: I like it +268 Vote: I do not like it

My thoughts while trying to solve Div1.A and Div1.C (it's 2 MB gif).

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A good contest.I only submit div A & B... Maybe My rating will decrease!

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Why is it that during each and every Codeforces contest, you can't access the site when you need it the most? In the first 30 minutes, I could view other's solutions. But after that whenever I tried opening someone's solution, it just gave me a blank screen. It didn't work even after refreshing the page multiple times. So I couldn't even TRY to hack a solution!

→ Reply
»
10 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Heh. I never expected that there will be a time when someone with rating 2484 will ask about it, but — how to solve A :D? D was the easiest one on this contest xD.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    Imagine easy dp with [coordinate][lastJumpLen] state. Replace second argument with difference between the first jump's length and last jump's length. You know that it won't exceed 300.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that B was much easier.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      B was still hard, took me something like 15-30 minutes (just coming up with solution) and D was straightforward for me :P.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Solution of A

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Petr try so hard to solve E instead of other problems? It lands him in 117th :/

→ Reply
»
10 years ago, # |
  Vote: I like it +77 Vote: I do not like it

Codeforces needs to at least have one approachable problem in Div1.. otherwise the majority of participants will not submit, meaning those who eventually do solve a problem will have a low ranking..

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    D was easy :>. Only one in that contest :D

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    Hmmm... you're totally right. After 0,5h of contest when I haven't got any idea how to solve any of those problems I considered not submitting anything : p.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I though, that once I'm registered, I'm competing — I expected my rating to be changed, even when I had no submition... On TC once I open the problem, my rating would be changed... But in fact the one who solved problem and ended at the end, his rating change is worse then mine, I think this is unfair...

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems! Has someone any idea for Div2-C instead of TLE naive recursion + memoization?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to approach Div1 D, it is an extension of Div2 B with larger constraints..

Div2 B could be solved by making m graphs, but how to approach the same problem if m is as large as 10^5?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain the idea of div1C solution?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    Didn't submit (edit: Accepted ), but here's what I thought during the contest:

    You want to simulate to see if a certain max_height is possible, then you can use binary search to get final answer. Hit the bamboos from the last day to the first day. Every bamboo i has to be hit before you get to a certain day hit_by[i] on the reverse simulation -- this means that even if you use all hammers possible on bamboo i before hit_by[i] you will not decrease height of bamboo enough, so you need to hit it at least once on a day after hit_by[i].

    I haven't proven it formally, but I think greedily hitting the bamboo with the largest hit_by works.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hm, I didn't get your idea. Can you explain the meaning of hit_by[i]? Why can you go from the end to the beginning? I mean, when you decide to do something in the very end, and then cut some bamboos before that moment, your final decision now possibly becomes wrong. Have I missed something?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        hit_by[i] means: I have simulated some hits at the end so far. If I hit only bamboo i for the first hit_by[i] days and then hit at the end according to the simulation, I will be able to get bamboo i to a height smaller than max_height. But if I only hit bamboo i for the first hit_by[i]-1 days (other than simulated hits), I won't be able to get bamboo i low enough. This means I definitely have to hit bamboo i at hit_by[i] or after.

        I don't understand why going from the end to the beginning would change the answer. When you do a cut the only thing that changes is the new target (I wanted less than max_height height by day m, now I want less than P height by day Q). If you go in the forward direction, then it's complicated because it's true that a cut affects a lot of other things.

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    My solution is based on the idea that it's optimal to hit a tree when its height is less than P at most once per tree. If this is true, then that hit should be at the first moment when (tree's height)  ≥  (tree's final height if left unchecked — target height) % P.

    I don't have a proof for that, though, so we'll see what happens in systests...

    → Reply
»
10 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Well, we feel sorry that the problems were too difficult. Actually, we felt all of the tasks were a bit more difficult in comparison with other problems of the same scores, but I hadn't expected that there were such a few submissions&accepts.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I think such difficulty is good, AS LONG AS there is at least one problem that 75% of participants can solve (and it is the first problem :P)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Median of times I need to came up with solutions to B problems is probably less than a minute and here I didn't have any idea how to solve A and B took me something like 30 mins xD. Though I like hard problems, so this contest was really fun for me, because problems were interesting and that's what really counts :)!

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I think we're all waiting for Editorial :)

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Hard problem's have benefits . Solve hard problem to learn a new something :)

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

just to know ... why it gives me time excess (something like that) when i open a solution to hack and then i can open it another time!!

→ Reply
»
10 years ago, # |
  Vote: I like it +76 Vote: I do not like it

1500-1500-2500-1000-2500

→ Reply
»
10 years ago, # |
  Vote: I like it +97 Vote: I do not like it

ENOUGH TO ENDURE!

I have strong disire to view code highlighting in hacks. I'm so tired to recognize 1's and l's.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Does the following algorithm for Div1B work:

find the number of connected components (assuming each edge is bidirectional); let it be a

find the number of such connected components that have a cycle (with directed edges this time); let it be b

Our answer is (n — a + b)

I tried this, so either this algorithm is wrong or I'm bad at implementation :P

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    The same algorithm passed pretests here.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      may you explain the analysis for this problem?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +39 Vote: I do not like it

        For a connected component with n vertices (if we consider the edge is undirected), the answer maybe n-1 or n. If the component doesn't contain any circle, then we can have a "line" that go through all the vertices making a graph that satisfy our condition (the order of vertices the line go through is in the toposort array) And if the component has a circle, what happen now? We can not make a toposort, then the answer can not be n-1, in this situation we just simply make a big "circle" that go through all the vertices (or we add an extra edge that go from the last element to the first element in the toposort array), then we will need n edges.

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Will it work on the next testcase?:

      7 8
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7

      The testcase looks like: <><>

      We still need here 8 edges, but we don't have directed loops here. Or it's possible somehow to come up with only 7 edges here?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Just consider topological sort, and connect neighboring vertices (here, 1->2, 2->3, 3->4, 4->5, 5->6, 6->7).

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        I guess correct answer is six: just connect i-th vertex to (i+1)-th: 1 → 2 → 3 → ... → 7

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Wouldn't the answer to that be 6? 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        answer is 6:
        1 2
        2 3
        3 4
        4 5
        5 6
        6 7

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Right answer can't be more than N, because we can make one loop with N edges, where from each vertex you can reach any other

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The algorithm is right

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider this case

    4 4 1 3 1 4 2 3 2 4

    a = 1 b = 0 Answer = 4 — 1 + 0 = 3

    If my understanding of the problems I right, answer should be 4.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      No, the answer is 3; you make the edges 1 → 2, 2 → 3, 3 → 4.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Right, thanks. From the start i was thinking of given m edges, remove as many as possible without disturbing connectivity. Screwed it!

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It should work.

    If you have a component that contains a cycle, you need to make at least one resulting cycle, so you need at least as many edges as the number of vertices in that component. It's clearly optimal to put all vertices on one cycle.

    If there's no cycle, you need at least (number of vertices)-1 edges; a DAG can be transformed into a path without failing any rules, and a path has the required number of edges.

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

Can someone tell me one thing, please? What is the point of having one extremely easy problem and one easy problem and 3 almost unsolvable problems for Div2 participants. Then you have list where 60th participant solved A and B, as same as someone who is 800+.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This often happens, especially in Topcoder SRM.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think, that you both are talking about different divisions, so I have to disagree, in TC DIV2 easy and medium are not so difficult and also hard is soleable...

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hacks are decisive here.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

Next competition is only div 2,maybe I solve something :)

→ Reply
»
10 years ago, # |
  Vote: I like it +30 Vote: I do not like it

What's wrong with system testing?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I opened results before system testing and saw this

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Pending system testing...................?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, let's start system testing! I want to see these red->purple and green->gray xD

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks you! Nice contest :D

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think system testing is deterioration

→ Reply
»
10 years ago, # |
  Vote: I like it +28 Vote: I do not like it

What's going on? 45 minutes has passed since the contest has finished!

I guess the rating updates will be fast as (because) the system testing is slow!

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think Codeforces is broken. Take a look at "Pay attention" area...

UPD: Already fixed.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It often happens when contest ends.

    → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The unusually long wait for the programs to pass the system tests is adding to the anxiety, especially for those expecting a rise in ratings after the contest

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve problem D of Div. 1? Why many people say that it's easy? Thanks a lot.

→ Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Second hour just began...

→ Reply
»
10 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Anybody else read Problem B statement wrongly? I thought only "edges" on input are allowed to make teleportation graph...

→ Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

So it has begun.

→ Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

The system testing is delayed due to verifying test cases(not a technical reason or trouble in the judge server). We feel really sorry about this.

The problems are so hard, even round author can't solve them.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The round author should have thought about it when he decided to be the round author. :) They have to be sorry anyway, it's a long delay.

    → Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I resubmitted D a couple of times because I saw I went over the memory limit (259900KB, but still Pretests Passed). 9463550

But it looks like my fears were unfounded, because the same submission, using even more memory on system tests, still got Accepted. 9465410

Oops.

→ Reply
»
10 years ago, # |
  Vote: I like it +62 Vote: I do not like it

rng_58 , It doesn't matter what is your rating (or rank)! we will always be your fan!!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    I guess he had a bet against Petr, which he lost!

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +70 Vote: I do not like it

    I decided to change my strategy and chose a problem that looked the most interesting for me. I enjoyed this round even though I solved no problems (but if you try to solve boring problems and fail a round it's quite frustrating). Maybe I will keep this strategy for a while.

    → Reply
»
10 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I will start crying now...

Test: #12 ... verdict: WRONG_ANSWER
Input
1 30000
30000
Output
0
Answer
1
→ Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The ratings are back to the last ones???

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Mmm, guys, what has happened to ratings?

→ Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

WTF , I had +55 but now it is +50 , why ???

→ Reply
»
10 years ago, # |
  Vote: I like it +237 Vote: I do not like it

It seems that i've just set a new record for shortest period of being IGM (~20 minutes, i guess :) )

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell what's wrong with my DFS for Div.2 B? Each node has a vector of pairs <color, endnode> and then it just tries to DFS through all the colors, but I can't figure out why it doesnt work. :/ http://mirror.codeforces.com/contest/505/submission/9461069

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know what your algorithm does but here is a simpler way:

    for every possible color see if there is an x-to-y path with that color only (x and y are query vertices).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I tried to figure out a path from the start vertex to the end vertex by just recursively checking the neighbour nodes of the following vertex and if the edge color was the same then continue searching until the end. However for some reason my implementation is not correct.

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I just can't understand how the rating works.. rng_58, whose rating was 2782, got -107. But Antoniuk (whose rating was 2244), and -imc- (whose rating was 2256) both got -102. All of them got 0 points in this round. How could this be possible?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    It is ovious even for me=). rng_58 have higher rating then Antoniuk and dragonic, so his rating dropped down most. Antoniuk and dragonic have same decreasing, beacause of rounding, rating calculates in double then rounds to int. Read about Elo rating. Sorry for my bad english.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You may be right. Thanks for your comment, I'll read about the ratings :D

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    There exist some threshold — you can't lose more than X points, no matter how bad you perform. I don't know how value of X for given user in given contest is calculated, but usually it is around 100 points (or a bit more).

    When you are violet — it is really hard to hit this limit; for red users it is much easier (placing somewhere in the middle of the standings is enough), and for top-users it is even easier — tourist once got -135 for 21st place.

    And also — look how dreamoon_love_AA was getting -110..-120 for placing last :)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was just suspicious because I got -111 last round, for only solving B. (my rank was 366/610) I think the reason is that the problems of this round were really hard than the last round's problems..

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this algorithm work for div 2 D?

  • Find strongly connected components,
  • Turn each SCC to a cycle and keep the remaining edges.
→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No. The correct algorithm is above somewhere. (look for Div1-B instead of Div2-D)

    → Reply
»
10 years ago, # |
← Rev. 7   Vote: I like it +2 Vote: I do not like it

Many Accepted codes of Div-1 A/Div-2 C crushes for this input:

1 1 30000

Is the input invalid? Or, judge data is weak?

This Accepted Code Crashes for the above input.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's invalid, because there are 30'000 islands in total, not 300'000.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry for my mistake, it was actually 3*10^4. I have updated the input now and have added a link of a acctepted code that fails this test case.

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    My prog return 1.

    I guess this is correct answer.

    UPD: Sorry, didn't notice 3*10^5, not 3*10^4

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      i actually meant 3*10^4. but, somehow miss-typed 3*10^5. Sorry for my mistake... i have updated the input now. :) and, i have also added a link that fails this test-case.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Test case #18 is exactly yours.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i don't get it... why this code would crush in my system while it works fine on Codeforces??

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Just a guess: undefined behaviour.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        f ends up recursing roughly 30,000 times; my guess is you got a stack overflow.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i guess too that it is caused by stack overflow. But, don't you think, PC got more space than virtual judge for stack memory? although, i am not sure which one got more space for running a program!! :(

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Codeforces sets a huge stack size.

            → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Stack size != total RAM size, at least in Windows (not sure about *nix). Actual stack size defined during program compilation. And, for example VS compiler by default sets it to some not-that-big value (1 Mb, I assume). And on Codeforces it is set to 128 Mb at least.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              that helps a lot.... didn't know that compiler allocates this little space :)

              → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div1-A/Div2-C, Could someone help me figure out why does 9462290 TLE at test 5 but 9467397 gets AC? The only difference is I change the memoization from a map to an array keeping the difference with d.

Shouldn't the two essentially be the same ?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    std::map has O(log n) access time, not O(1). AFAIU std::unordered_map has sort-of-O(1) access time, but with bad constant. I also failed to solve this problem with unordered_map, but got AC with plain array.

    BTW, my array solution works 5x times faster than yours, probably because I also use array for gems variable (and you use map).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know that a map has O(logn) but that should still make within the time limit, right ?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As we can see, it shouldn't :(

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          I guess map is actually slow and I should be more cautious using it then. It seems to have a very large constant factor and does allocations for each object hence its slowness.

          I found this:

          std::map has similar characteristics to std::set: it uses a single allocation per pair inserted into the map, it offers log(n) lookup with an extremely large constant factor, imposes a space penalty of 3 pointers per pair in the map, etc. __ std::map is most useful when your keys or values are very large, if you need to iterate over the collection in sorted order, or if you need stable iterators into the map (i.e. they don’t get invalidated if an insertion or deletion of another element takes place)

          source: http://llvm.org/docs/ProgrammersManual.html

          EDIT: Hmm I just tried changing my code in Java to use a HashMap which has O(1) 9467938 but it also gets TLE at test 5..

          → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for posting this, I'm practically in the exact same situation. My solution is here: http://mirror.codeforces.com/contest/505/submission/9467923 and theoretically its complexity is at most around 30000*500 operations, which should be acceptable. However, since these operations are on maps, it appears the very large constant factor does its tricks. I expected my solution to either barely pass or just barely get TLE, but it turns out it takes ages to produce a solution, tens of seconds on my machine. Honestly, I'm pretty shocked at how slow the operations on maps are in this case. I guess this is a good lesson for me on how well modern processors can handle contiguous data (vector) vs. not-so-contiguous (map).

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So do I. Even I changed map to unordered_map, still got TLE.

    A tough lesson, QAQ~

    → Reply
»
10 years ago, # |
  Vote: I like it +25 Vote: I do not like it

2 years ago Coder noticed that Petr and tourist couldn't solve C which was also E for div2 and made this comment: http://mirror.codeforces.com/blog/entry/5586#comment-108611

What to say today about Petr and rng_58 :)?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Imagine both of them only solving A and B in div2 and placing 800th

    → Reply
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Meh. It's good to have basic knowledge about STL...

This got TLE and used 198MB: 9459485

And this easily passes all tests using 23MB: 9469360

The only difference is changing 

res += (pars[c][u] == pars[c][v]);

to

if (pars[c].find(v) != pars[c].end() && pars[c][u] == pars[c][v]) {
    res++;
}
→ Reply
»
10 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Finally, after 93 contest I'm in div1 I'm so happy!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I pass Div1 A and D both through brute force. So lucky and maybe the test cases must be more careful.

→ Reply
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Where is the editioral?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 5   Vote: I like it +7 Vote: I do not like it

    It is currently being written. The first part (all problems except Div1C(2E) and Div1E) will be ready within approximately 4 hours. Thank you for your patience.

    Edit: sorry, I had to insert one word into the sentence above.

    Edit2: The first part has been published here. It actually took 8 hours after I posted this, sorry for being late.

    Edit3: Added Div1C(2E) and the problem setters' codes.

    Edit4: Added Div1E. I am sorry to have kept you waiting.

    → Reply
»
10 years ago, # |
  Vote: I like it -7 Vote: I do not like it

When will the editorial be out?

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

problemset was tough but very nice , problems required more thinking instead of coding that means quality contest.

Congratz to authors !!!

→ Reply
»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I can't open editorials

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Why my solution get WA on test 10? I can't see anything wrong in my solution...

My solution

Please help me!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

excuse me, for this easy sample : 6 7 1 2 2 3 3 1 3 4 4 5 5 6 6 4 the output is 6, it is not 7, why ?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me and explain why my solution is failing for Div1 Problem A. My Solution id is : 9666602

→ Reply