DeshiBasara's blog

ICM, Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)
By DeshiBasara, 8 years ago, In English

Hello, Codeforces!

I would like to invite you all to the International Coding Marathon 2017, under the banner of Technex'17, which will take place on Thursday 23rd February 2017, 20:05 IST. The contest will be held as a combined Div.1+Div.2 round which will be rated for participants from both divisions. The prizes for the event have been sponsored by D. E. Shaw & Co..

The Indian Institute of Technology (BHU) Varanasi, India is proud to present the 78th edition of its widely renowned techno-management festival, Technex'17, to be held from 24th to 26th February 2017. Offering a myriad of diverse events across fields such as programming, robotics, and aero-modelling, it witnesses enthusiastic participation from all across India and abroad.

The problemset has been prepared by me(DeshiBasara), vikhs_96, Prateek1996 and ishankarora. We would like to express our heartiest thanks to KAN for his constant help in preparing the contest and MikeMirzayanov for the amazing Codeforces and Polygon platforms. We also thank ashmelev and winger for their invaluable help in testing the problems.

UPD1: The start time of the contest has been delayed by 10 minutes.

UPD2: The scoring is 500-1000-1500-2000-2250-3000-3250.

UPD3: Thanks to all those who participated and heartiest congratulations to all the winners. The winners, who are eligible for prizes, will soon be contacted regarding the same.

Overall top 10:
1. ainta
2. tourist
3. LHiC
4. halyavin
5. jcvb
6. mnbvmar
7. uwi
8. jqdai0815
9. Syloviaely
10. Radewoosh

Indian top 5:
1. rajat1603
2. Baba
3. akulsareen
4. sampriti
5. PrashantM

Some of the problems were not up to the expectations. There were some issues with the site too. We deeply regret the inconvenience caused.

UPD4: The editorial for the round has been uploaded.

Prizes

Prizes worth INR 100,000 up for grabs!

Overall 1st place: INR 35,000. Overall 2nd place: INR 25,000. Overall 3rd place: INR 15,000.

1st place in India: INR 10,000. 2nd place in India: INR 6,000. 3rd place in India: INR 4,000.

1st place in IIT (BHU) Varanasi: INR 4,000. 1st place among IIT (BHU) Varanasi freshmen: INR 1,000

Participants will have 2 hours to solve 7 problems. The scoring distribution will be announced soon.

Good luck everyone! Hope to see you on the leaderboard.

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

Comments Comments (314)
| Write comment?
»
8 years ago, # |
  Vote: I like it +106 Vote: I do not like it

Congratulations everyone on the 4th century of contests here on Codeforces :) :)

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

I thought "What is INTERNAT? Is it a typo of INTERNET?" and it took me a while to understand that it is actually "INTERNATIONAL".

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

7 problems 2 hours! Hope A B will be for all.

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

Wish ALL high rating.

:)

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

Lately there are to many contests from India. Soon codeforces will become an Indian contest webcite :)

Anyway, I hope all the red and yellow coders rating increases. All the dumb ones may suck.

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

    I don't think you are Indian — you even don't know spelling of website?. Don't try to defame a country or a website. Hope you get a break from your miserable commenting life.

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

    so what the F should u do?

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

What happens if the 1st place in India get top 3 overall? Does he get both of the prize?

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

    In such a situation, he will get the prize for top 3 overall. The India topper prize will be given to the next Indian in the ranklist.

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

Am I the only one who didn't know what this currency is??? And how much is it in Dollars :D

I know I won't get any prize, but I was just wondering :3

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

    The currency mentioned is INR (Indian Rupee). 1 USD = 66.98 INR (As of today) INR 35000 = 522 USD, INR 25000 = 373 USD, INR 15000 = 223 USD

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

      Thanks, Now I knew that the currency in India is Rupee :D

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

I hope that this time we will see at least two tasks with level >=Div1C and that there will be no tasks worth 2000 points that are a good fit for Div1A :P (yes, I am regarding to last contest).

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

    IMHO problem D,E,F in last contest are good fit for div1B and are much harder than usual div1A. Maybe div1B is just as easy as div1A to red coders :D

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

    I'm a simple man. I'll be happy if the round won't become unrated because of the issues with the server.

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

    G says "do some complicated digit DP". F says "do centroid decomposition". E looked nice at first, but after you find g(n) = n it's pure implementation. Stopped reading problems here. I think the problems are fine, but it suits better for a d2-only round. I don't say the problems are too easy — F and G are time-consuming and it's hard to solve everything in 2 hours. But there should be problems that require non-trivial idea.

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

      Well, for me it is the first time when I wrote centroid decomposition. Now it is not just crazy idea that is only needed for problems that I can't solve anyway.

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

        Yes, I didn't say the problems are easy. If the purpose of this problem is to introduce centroid decomposition, shouldn't it be used in educational rounds?

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

        You don't need to break down by finding centroid of trees. Just the center of diameter will work as well I guess.

        Edit: Something like this: 23787939

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

        The centroid decomposition part of F is just Round 190 C (link: http://mirror.codeforces.com/problemset/problem/321/C)

        BTW, I don't think "center of diameter" algorithm is correct for arbitrary graph, but maybe it's correct for problem F because the polygon partition graph is somehow special.

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

      Absolutely agree, and you haven't seen D, it's the worst today, I guess (I've seen it hundreds of times).

      Actually I suddenly find these contests very useful for my training to the finals but it was definitely not interesting to solve most of the last rounds.

      → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -60 Vote: I do not like it

Is it Rated?

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

    The contest will be held as a combined Div.1+Div.2 round which will be rated for participants from both divisions.

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

Is this just a single event? If so, why is it called a marathon when it's just 2 hours?

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

    Because Codeforces users run very fast.

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

    From the second paragraph I understood that this contest is a part of a bigger event.

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

Does anyone has GATEWAY TIMEOUT errors?

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

    I do

    BTW, nice way to check whether a site is down link

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

I hate postponing :D

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

I am doing contest from office , now you guys postponed it i have to go late by then :/

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

Waiting for a long time, but it is postponed. :( :(

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

Any writer's girlfriend missed the registration?

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

I have short.

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

Rating prediction for this contest could be found here (after contest begins)

Extensions:

About CF-Predictor

Good luck & high rating to everyone!

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

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

      This happened because I use free (low performance) server to calculate rating changes. Once a few minutes it does "standings request" to codeforces and then calculate prediction. So prediction always late for couple minutes. Yesterday, delay was up to 7 minutes.

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

    Gives me a wrong rank

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

Queue :(

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

Seems like Unrated Contest :(
15 minutes still no verdict! should I leave this problem or not?! Not sure it will pass :( Please Make this Unrated. So many suffered from this —

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

never ending loading...

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

Is it just me or this contest is too lag to do any hacking?

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

Is Codeforces server on AWS ? If not, then I think it's time to move on AWS.

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

I am getting long loading times as well. not sure if there is a problem with my browser or with Codeforces.

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

Can't access ɔopǝɟoɹɔǝs˙ɔoɯ

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

It has been more than 20 minutes that I cannot open any of the contest pages...

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

If You are reading my comment,i have jumped off the roof (Connection TimeOut)

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

Endless loading drove me to play hearthstone in order to keep a good mind.

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

THIS TIME WE DON'T even NEED ANY REASON TO DO CONTEST UNRATED.

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

I think after such an incident there should be a announcement clearly stating further action like extending contest time/contest being unrated/no changes . Although, its done in most cases, not yet in this one though. EDIT: It seems they heard me.xD

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

ямар аймар гацдаг юм бэ хха болилоо нтр

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

My grandma runs faster than CF.

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

They said in a clarification "It was down for only a few minutes"
Is it only me who couldn't able to access the site whole time?

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

    it was down for ~30 mins for me.

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

    The site seemed to play Hide and Seek with me :P

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

    if few minutes count for 20% of the contest then yes .

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

    30+ mins for me

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

    Lets pray and hope that this round will be unrated :(

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

    Most of the time it was down for me.

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

    It was down for me for about 20 to 25 minutes and even when it was up it was slow AF.

    Still could be worse...

    :)

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

    It was down at least 30 mins for me too.

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

    I believe it was down for 15 minutes. I submitted C and got WA on pretests and just after 15 — 16 minutes, I was able to submit again and got pretest passed.

    Sometimes people exaggerate because it was not a good contest for them.

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

      Nope.. Actually it was down for 30+ minutes. It was playing hide and seek >:(

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

"Extended by 10 minutes"? I had to wait more than 40 minutes to send C again, it means 250 points lost... Codeforces is a great platform but please fix that high availability.

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

The website was down for more than 20 minutes and earlier the queue was big..I submitted B for 700 but got only 500....please make this ****unrated****

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

Why is my 3rd hacking attempt still waiting while my 5th attempt has been judged? And someone else hacked that solution later and succeeded, while mine, which was earlier is still waiting.

my hack attempt: 303111

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

How come I submit for 700+ and get 600+? I suppose I'm not the only one encountering this.

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

Codeforces servers were slow for the contest.Lost lot of time because of this.

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

What a weak PP of problem C.So sad:(

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

Can anyone give a hint on how to solve D?

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

    use DSU

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

      How? I first thought DSU, but couldn't see how even and odds can be handled

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

        Of course if we only care a switch need to be toggled odd number of times or even number of times.

        If a door is locked,it means one of the switches which control it need to be toggled odd number of times while the other even.The situation that a door is unlocked is similar.

        We can check if it's ok using weighted DSU

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

          I still don't get it. We don't know which switch will be toggled how many times. For example, if door A has switch B and C, such that door A is initially closed, then B+C is odd, but we don't know whether B is odd or C is odd. How did you handle this?

          Sorry if my question is stupid, I don't know how to apply this concept with weighted dsu very well.

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

            Maybe that's because my English is really bad.

            It means when we use DSU we record the relationship of a point with its father.I don't know its name in English exactly.

            We needn't know exactly whether A or B is odd.We only need to know the sum of them is odd or even.If we need the sum is odd while we need the sum is even,the answer is NO.At any other situation,we can always get a solution to make all the door unlocked.

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

      Why does DSU work? If we're doing regular 2-SAT we have to build directed edges from >y and >x right (this is the case that the doors are locked)? But in this case DSU makes these bidirectional edges, which I assume is incorrect? It code it and it actually works for some reason, but I have no idea why.

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

        In this problem,all the edges are bidirectional.So we can use DSU.

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

    I think that it is 2sat problem. I solved it using DSU.

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

    for each room , let its 2 switches be a , b. Now if that room is off then a and b must be different else they must be same. So just make a graph and check for bipartite.

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

    If all rooms are opened then answer is YES. Else, there must be at least one room that is locked, try first switch and second switch to make this opened with something like dfs.

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

      isn't this 2^n?

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

        You should just try first room that is closed.

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

          I don't get it. so for each room that is closed, you have 2 choice. so you recursively do this. How is this not 2^n?

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

            Notice that if I have a valid solution, I can toggle all switches and the solution remains valid. So set Switch 1 to 0. This will decide the values of all switches which are connected to 1. (Using the doors as 'edges' of the graph).

            Do this for each connected component once. Complexity O(N)

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

            nvm, it is wrong. There can be multiple connected compunds:(

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

    I think 2-SAT

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

    Its basically a slightly modified version of this problem

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

    Hey, I wrote hint-by-hint solutions here: https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72

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

Asking for answer modulo 1e9+7 when it's quite small is evil. :(

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

    Actually I didn't even check if I passed the pretest because the internet is too slow. Then I found I didn't modulo 1e9+7 when I submitted F. I left the bug there for half an hour :P

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

      Well, at least it was in the pretests

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

      I did the exactly same thing. Fortunately, I saw the line asking for modulo in less than 10 minutes after submitting (of course I couldn't see that the solution actually got WA, because 10 minutes is way to fast for one to get the score)

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

    Actually, I also was a victim of that, but I think it was necessary. Otherwise it would be strong suggestion that result is small which was probably a big hint in this problem.

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

B hack?

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

Lol ! I was hacked twice in problem C one hack for K = 1. and one hack for K = — 1 :D

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

    I wrote for 1 but missed for -1 :P

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

      Lol I have no idea how didn't I see the modulus in the problem statement :D But that was fun , I was waiting for the second hack :D

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

        same here totally missed that mod in constraints

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

    I covered k = 1, but forgot k =  - 1 and hacked people with these two cases. Nobody hacked mine lol

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

    Lucky!

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

codeforces really needs to scale up to handle more users.

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

What was pretest 4 problem D?

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

Could someone give me a hint for problem C please?

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

    Prefix sum + map for frequency

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

      i used unordered_map and i got tle. i know that unordered_map is teoretically a lot better, can you help me with an explanation please?

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

        Same for me :'(

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

          Count me in too :( I attempted C before B and now my C failed due to this and B got less points anyway.

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

        me too..

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

        Unordered map isn't a ordered container.You'll have to calculate lower/upper bound in this problem.

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

          Depends on the solution. I only need to check for inclusion in a set.

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

        unordered_map's is constant time lookup in the best case, but the worst case is linear lookup if there are many hash collisions. It is possible to generate test cases against unordered_map. I also used unordered_map and got TLE. After failing systest and changing to map, it got AC. Should've known this earlier :(

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

    Hey, I wrote hint-by-hint solution to problem C here: https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72

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

Thanks

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

Steps to solve problem E:

1.f(n) = φ(n),it it obvious.

2.Open aops.com ,search for g(n) and find that g(n) = n.

3.It is obvious that φ(...φ(n)) is quickly decreasing.

That's all,find Fk(n).

Very original to combine all 3 steps, like.

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

    Or google phi-phi-phi on hackerearth instead.

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

    I open www.baidu.com in step 2 :D

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

Great round, very nice problems!

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

Wanted to submit C in last 2 minutes but nevermind codeforces servers didn't wanted me to gain ratings :/

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

I was waiting for submitting B more than 30 minutes. The server was totally down. Please make it unrated. MikeMirzayanov

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

Is there any nice way to solve F?

I could see that the dual graph of the planar graph described would be a tree and that we should do centroid decomposition on it but I had no clue as to how to actually implement anything.

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

    I can probably help with implementation after converting polygon to graph. You can decompose tree using center instead of centroid using BFS-like idea (and DFS to find center). I've done something similar here: 23787939

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

    IMO, the most challenging part of this problem was building the graph (tree ;) The idea I used was:

    The most important fact I used to build this tree clean was that the id of each region is determined by the two nodes with bigger id on the border of the region.

    Put the nodes of the polygon in a line in order 1, 2, ..., n Then put the diagonals as segments on this line (u, v) (where u < v) Notice that if two segments have non zero intersection, one is completely inside the other. If we include the segment (1,n) we can say that each diagonal denotes the region that is inmediatly above it. The DIRECT including relation might be interpreted as a parent-child in a tree, Order this segments by start in increasing in order and break ties by length (in decreasing order). This order is the preorder of the tree, so you only need to rebuild the original tree from the preorder.

    The rest of the problem, is using centroid decomposition, similar problem where the tree is given can be found here on codeforces.

    My solution. 24937275

    Good luck

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

I want to hack someone in the last minute, but CF lags and forbids me to do so :( (Quite sure his solution is wrong)

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

**15 MINUTES LONG QUEUE ANF AFTER THAT 45 MINUTES OF SERVER DOWN **

** I JUST REMEMBERED PRINCIPLE OF MUTUAL EXCLUSION**

** 1 HOUR SITE RELATED PROBLEM EXISTED AND IN RETURN WE GOT 10 MINUTES._wOWO_

I JUST REMEMBERED LAW OF EQUIPARTITION OF ENERGY **
→ Reply
»
8 years ago, # |
  Vote: I like it -41 Vote: I do not like it

Let's vote: Strawpoll.

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

    Those polls always get biased results. People who are fine with the status quo will scroll past the poll while those who want the round to be unrated will vote.

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

When you missed E because of slow Internet connection... I would have a sleepless night if that solution got AC...

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

Is it just me or will unordered_map TLE on C? Somehow when I test my solution on a large case for C it doesn't seem to be able to close to running in time whereas changing it to map makes it work almost instantly. Not sure why this is happening (I didn't try to construct cases to fail unordered_map solution)

24923074 (n = 100000, k =  - 2, ai = 229)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    ans+=ma[a[j]-tmp];

    I think first checking whether an item exists in the map could speed up as it won't store anything in map incase no such value exists.

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

    I tried to construct cases to fail unordered_map.

    Generator

    It takes about 4 seconds.

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

      Why it TLs unordered_map in GCC (24943025), but in VS2010 it is AC (24943348)?

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

        Because hash maps implementations are different. GCC uses libstdc++ library while Visual Studio uses Microsoft STL.

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

    That can give MLE, but I am not sure. If you want to get some element from the map, better to do if (map.find(element) != map.end()) instead of just taking map[element]

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

Ty CF. If you didn't crash I could have had F. :'(

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

It would be nice, if problemset could be loaded as pdf by clicking just one button near the button "Complete problemset". When contest lagged today, I already solved E and sent it(although forgot to make %MOD operation and knew verdict only after 20mins) and wanted to open F, but I couldn't do this for the next 20 minutes. If problemset was downloaded at the start, problem could be read during this hard laggs.

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

    You can click on Complete Problemset and then print the file to pdf.

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

I hacked one person with this test 5 8 0 0 0 0 0

He calculates all power till 50,then push them to set and forget about overflow. And i found that 8^21 = 0.

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

I accidentally resubmitted C twice instead of once due to network issue 24941488 24941490 What can I do? This is really sad.

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

Any hints on how to solve F? The only solution I thought of is build a tree and then find center of the tree, color it, remove it from the graph and recursively color the remaining set of trees but that doesn't look like an easy solution to implement.

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

    Not the center but the centroid. The other part is correct.

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

    It's F. It doesn't need to be easy to implement.

    Most of the solution is unfortunately copypasting. First, you should divide a planar graph into "walls" and then you perform centroid decomposition on it. Both functions can be copypasted from a library, if you have one. I didn't have :c

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

    My approach: Sort the walls based on their "length". Now the wall with minimum length and the boundary between two endpoints form a region. Let W denote the wall and R1 denote the region. Remove R1 and now W is a new boundary edge. Then mark R1 on W. When you finally remove some region R2 containing boundary edge W, build an edge between R1 and R2.

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

Has anyone this bug? I hope that this submission will be taken into account.

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

The problems take time but the ideas were straightforward. Maybe only E wasn't since you needed to write something down before conclusions, unlike F which was screaming "build this fkin tree and run CD".

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

    Actually E is pretty known(that sum of phi (d) is N — 1 for d | N) so neither E was much of a problem

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

      Oh, if this is well known, then yeah, boring problemset.

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

There were some serious technical problems with the website in this contest.

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

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

Why do I get TL 13 in C? (code)

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

    I've wasted more than an hour trying to pass test 13. In the end I got to know that set/hashset count works in linear time.

    Used map and everything will be fine :(

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

E — let's add a random function which is well known to be an identity function

F = http://mirror.codeforces.com/contest/321/problem/C + duality on planar graphs

great problemset...

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

    I've finished the code for F 3 minutes after the contest ended. However, I had some trouble in building the graph (well the tree), especially because it was hard for my to determine the polygons. How did you do this part? I've hardly managed to come up with some strange recursive function and some strange disjoint data set to find out the polygons.

    Ohh and about the fact that F didn't bring anything new, let alone E, I agree. I also hated that most of the scoreboard was decided based on hacks. In my room there were 4 or 5 hacks in total. I found 3 of them by myself and CF was moving so slowly that someone else got them before I could even type the numbers...

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

      My method:

      build initial graph from i to i — 1 as well as from 1 to n

      build additional edges as input, two-wayed

      build the graph from largest valued polygon:

      first, identify the largest element that still has an edge left

choose the closest edge to walk, where the distance is defined as the "non-input" edges needed to walk from u to v, i.e. u,u-1,...,v

delete that edge, mark it too. (when an edge is marked twice you add it into the tree)

define lastdist = dist(first vertex, second vertex)

while we didn't return to largest element

     find the furthest vertex from itself, that does not exceed or equal n &mdash; lastdist

     delete the edge, do marking

      Ya and this problem is too original and standard... (and boring)

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

      I agree, hacks will play a big role in the standings. It's the sort of thing I always do when finding components in a planar graph. For every node, sort the edges by their angle. In this problem, that's just sorting them by their index.

      Now, let's say we will traverse each component in CCW order. Find a previously unused (directed) edge and then in each step choose the edge that creates the smallest directed angle with the previous one, this can be done with a simple lower_bound. When you return to the starting node, you found a component.

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

Savage of a contest

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

hogloid, I hate your -1 :D

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

I couldn't open the site for over 30 minutes. I think it should be unrated.

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

How to solve C?

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

    I wrote hint-by-hint solutions here: https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it 
    let  p[] - unique power of k's ' which absolute value less than 10^15
    k = 1.  p[] = {1}
    k = -1 .  p[] = {-1, 1}
    k = 2  . p[] = {1, 2, 4, 8, ..., 2^60}
  and etc.

now.  sum(i) = a[0] + a[1] + .. + a[i]
    we need number of that intervals which  a[h] + a[h+1] + ... + a[i] = k^x 
   but  a[h] + a[h+1] + ... + a[i] = sum(i) - sum(h-1)
    so  if we know sum(i)  and k^x  --> sum(h-1) = sum(i) - k^x
    need calculate number of h,  0<= h < i and sum(h-1) == sum(i) - k^x
    there assume sum(-1) = 0.
 
let   freq[ sum(i) ] -- number of  h, where  0<=h < i,  and sum(i) == sum(h).

    so ans(i) = freq[ sum(i ) - power(k,x)] ,  where x >= 0 and k^x < 10^15.
    
     answer = sum(ans(i), i = 0..n-1)
   
//let coded:
vector<long long> p;
if (k == 1) p.push_back(1); 
else if (k == -1) p.push_back(1), p.push_back(-1);
else {
   long long ky = 1;
   while( ky < (long long)1.0E+16 && ky > - (long long)1.0E+16 ){
          p.push_back(ky); ky *= k;
   }
}
map<long long , int> freq;
freq[0] = 1;
long long sum = 0, ans = 0;
for(int i = 0; i < n; ++i){
     sum += a[i];
    for(int j = 0; j < p.size(); ++j)  ans += freq.count(sum - p[j]) ? freq[sum-p[j]] : 0 ;

    ++ p[ sum ] ; 
}

 cout << ans << endl;
    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

#FIXCF

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

How to understand F?

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

have waited for "codeforces.com/contest/776/submit" for over 30min

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

Couldn't do anything for 20 minutes after I finished F. I hadn't even read G then. Although I'm not sure if I can finish G in contest time, still feel a little bit upset :(

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

I strongly recommend to hold such a kind of contest in Div2 only...

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

    This has prevented lots of black coders winning a div2 contest =)

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

My D will fail because I assumed there is only one connected component :(

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

In task C, the current winner mnbvmar has:

int s = 1;
while (abs(s) < 1e16) {
      diffs.push_back(s);
      s *= K;
    }

Looks like it's going to fail?

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

    Seems like a lot of people did miss the k = 1 or k =  - 1 case, so we could probably expect some changes in the leaderboard.

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

    you missed the first part ? 

    if (abs(K) == 1) {
    diffs.push_back(K);
    if (K == -1) { diffs.push_back(1); }
  } else {
    int s = 1;
    while (abs(s) < 1e16) {
      diffs.push_back(s);
      s *= K;
    }
  }
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      He is using int and multiplying by K until 1e16.

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

        You forgot this:

        #define LL long long
#define int LL
        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it -35 Vote: I do not like it

          This should be considered code obfuscation. Obfuscating the code just for the purpose of reducing other contestants' points for incorrect hacks.

          The reason for this, is that this define is among code which is not considered the actual solution. You should not be reading somebody's template code in order to understand the solution.

          Also if that code is considered the actual part of the solution then all the macros and functions should be used in the program. If they are not used — it means that this is unnecessary code, which makes it harder to read and understand the solution.

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

            Go away. I am sick and tired of explaining why this is huge bullshit.

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

              No it's not. Making solutions unnecessary complicated is a bad practice in general — you should have known that.

              It is also against the rules which says that there can be no more than x% of unused code. That rule is usually violated by some templated code and nobody complains about it as everybody just skips that and reads the "real" solution. If you are required to read the template code in order to understand the solution that rule should apply.

              You are explaining something which can't be explained. Not a big surprise that you are sick and tired of that. If you see the int, it should be an int. If it was some sort of custom type like INT or INT64 etc., it could be justified. Such thing at least indicates, that you should go and check that type. It is not possible to deduce that int is long long, without carefully reading the whole templated code.

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

                I care about getting ACs instead of WAs because of overflow and I don't give a single %^&* about people unsuccessfully hacking my code, I do not have any intention in misleading people (even though it may mislead somebody, but I don't care about it). End of topic.

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

                  Your intentions do not matter. What matters is % of unused code. That rule is usually relaxed by the fact that you put a bunch of templated code, which is not used in your solution.

                  I also said few times already, that changing existing type to something else, requires reading the whole source code — which does mean that your templated stuff, should be considered a core part of it. Because of that, you should reduce your template and includes only to the things which are really used in your solution.

                  Everything which is not used, should be counted against the % of not used code.

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

                  There is no such rule on CF. Haven't you seen codes with 1000 lines of template codes at last pages of sort by solution size submissions. Such a rule exist on TC.

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

            This is not code obfuscation. It is to avoid unnecessary WA caused by overflow.

            When you hack, you're supposed to know the language specific, in this case you should know that #define int lnog long is possible in C++.

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

        oh I didn't read that..

        EDIT : oh turns out it is fine....

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

    Tricky: define int LL

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

RIP solutions of Those who handled k = 1 but not k = -1 case in C.

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

After a long time there comes a contest in which i could do both A and B....Hoping to get rejected in system testing....

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

Codeforces can you please stop allowing contests from Indian Problemsetters? Especially contests with blue problemsetters...

If you really want to have these shitty contests, make them Div 2 only please.

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

    You are kidding, right? The problem was with the servers. Don't target people who were not responsible for making this contest what it was.

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

      I think he meant the problem quality was not good enough for div1 contestants.

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

    Racist...

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

      Last 2 contests have been by indian blue problemsetters, and the problem quality is utter SHIT.

      If you don't believe me go check the comments under the last contest, and you'll see I'm not wrong.

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

        You can't draw such conclusions from 2 contests. Having two shitty contests in a row is in no way justification to ban an entire country from problemsetting.

        Furthermore, I'm willing to bet that the problem has less to do with India and more to do with blue. The way those contests were set up also makes me believe they received less coordination from KAN and the Codeforces team than the average round (since they were created for some sort of festivals, not regular rounds). I might be wrong on this obviously.

        "Utter shit" is also definitely exaggerating. The problem quality was below average, but I've seen way, way worse.

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

What were you missing, people who got WA #3 on F?

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

C was given on geeks for geeks just needed minor changes, and the long queue otherwise the contest was good.

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

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

About 30 minutes I could not do anything on CodeForces :(

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

Problem G:

Why are there no sample case whose digit is more than 4? Sample case should contain "essential" case I think, and in this problem, the main part is DP on digit, but all sample cases don't require that!

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

next time you host a contest for Div1 and Div2 combined, please make sure that the site doesn't get down in the middle of the contest

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

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

Super fast System Testing. Came late but came strong...

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

I have a dream, that one day codeforces will be stable and fast

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

Please add problems to practice section.

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

Is this contest ranked? The site did not work most of the time!!!

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

TLE on test 101 in problem C :(

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

C — unordered_map: TLE. map, set: AC. seriously?

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

    yes, because element accessing complexity is linear and logarithmic respectively.

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

      I think you are not right, because how i know, unordered_map make this for constant, not linear

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

        Then what is the reason behind TLE for using unordered_map ??

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

        In the worst case — linear.

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

        No, paradox1 is correct in the worst case. unordered_map uses a hash function to determine where to store the value. On random data, you can expect that there will be not too many collisions (that is, different values that hash to the same integer) and you would expect each lookup to be (roughly) O(1). However, if there are a lot of collisions, then each lookup can be as bad as linear. Test cases can be constructed (for example, here) to try to make each lookup linear. On the other hand, map is guaranteed O(log n) in the worst case.

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it -11 Vote: I do not like it

    Similar thing happened to me yesterday in a contest.

    scanf/printf: TLE

    cin/cout: AC

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

    unordered_map is not suitable for a small number of elements (which in this case is 10^5) as it works on hashing..(Probing slows it down.. due to collisions)...

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

Nice problems!

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

Can someone be generous enough to tell me how to decide whether to use normal map or unordered map ????

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

    Hash your number by xoring with a random number when using unordered_map.

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

      How can I generate "really" random numbers?

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

        You don't need to? just use rand so that neither a hacker nor system test can guess the salt value.

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

        It's never "truly" random. We can generate pseudo-random numbers using rand() function in C++, which will do the job the same way in practice.

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

    Always use map =)

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

A hint for the next contests: Open all problem pages at first minute, at least you will be able to read the others problems and dont feel useless when the site crashs completely :(

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

What is WA in D on test 55, jqdai0815 also had this problem? :(

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

    When it's unlocked, you need to add edges between a and b.

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

    I guess D was supposed to be solved with SCC, (at least I did it that way). This method does not yield any corner cases.

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

When you see second sample of problem A:

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

what is the solution of problem c. Thanks in advanced.

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

    I used prefix sum, and binary search.

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

      Can you please tell me the idea of running binary search on prefix sum in detail.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1. calculate prefix sum in array D
        2. keep a map<long long, vector>, and for each element(E) in D, keep all indices (i) such that D[i] = E in the map[E].
        3. for the current power of k (pk), iterate through D with current index i, we have to look for D[i]+pk, because we want their differense to be pk.
        4. recall that map[d+pk] contains such indices, but we need the ones bigger than i, here the binary search comes to help.
        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Store all the numbers that should be found (k^0, k^1, ..., k^j) in the array (note that max number that can be found is 10^9 * 10^5 = 10^14). The size of this array is logarithmic (note that you should probbably treat k=1 and k=-1 as a special case and form the array manually).

    In order to find the ranges with sum x you can use the prefix sums. For each prefix sum p[i] you should find the amount of sums p[j] such that p[i] - p[j] = x. It can be done using a map.

    My code: link

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

http://mirror.codeforces.com/contest/776/submission/24923436

http://mirror.codeforces.com/contest/776/submission/24943032

wtf :/

please re-evaluate my submission :/

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

    966 is extremely close to 1000 so its just a matter of fluctuation.

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

Blue at last ,after a long wait .....

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

I got TLE for using unodered_map. But when I used "map" instead of "unordered_map" it passed.
with map 24943858
with unordered_map24939864
Can anyone please explain..

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

Had +17 in prev round, now -17 lmao.

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

Where is editorial?

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

"I'm fucked up,I'm black and blue"...

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

Problem:C -Mollys Chemical Hey, I am getting TLE on 13th tcase. While most of the solutions are based on similar logic. My time complexity is O(N*60*log(N)). Solution:http://mirror.codeforces.com/contest/776/submission/24941529

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

    Time complexity for multiset count(x) is O(lg n + (number of xs in the multiset))

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

    Search of a lot of similar values in multiset can be linear. Use map<ll, int> instead.

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

in Problem D

"You need to tell Sherlock, if there exists a way to unlock all doors at the same time."

So this doesn't mean that I need to find a way to toggle the switches so that the last move will toggle all the doors from locked to unlocked, and now they are all opened at the same time !!?

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

Wow. I waited for 20 minutes after making a submission, without being able to find out whether it got accepted or not or even read other problem statements. After that, I just went home, as it was clear the contest was going to be unrated and there's no point in waiting for Codeforces to work again. Now it turns out the contest is rated and my last submission got WA on E because I forgot the %mod operation.

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

#roadtoyellow

There's nothing really tricky in that, just add "unordered_" in C, change "sw" to "doors" in D and forget "+1" when sorting array in F :P. And before that, screw up similarly 6 previous contests.

Now I need to screw up few more contests as dreamoon_love_AA did to pretend I did everything on purpose :P.

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

    If only getting yellow is as easy from down here :(

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

    Actually I don't get it. Was wondering what you meant that adding "unordered" solves C — I used unordered map and it did not work. After reading this post (and looking on your solutions) I submitted it with normal map, and it passed... Perhaps there is some rule of thumb when use unordered_map, and when to use map? Isn't it actually a flaw of the tests? The programs should not fail due to small multiplicative constant, should they?

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

      He meant adding unordered gave him TLE — see his submissions. Also, its not multiplicative constant but O(n) worst case time for unordered map vs O(logn) for map.

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

        I know. Perhaps did not state it clearly enough. What I am asking is "Why is it so?". Appears stupid.

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

        Ah, and the complexity is constant on average and we perform many queries, so it should be faster.

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

          Complexity is constant on average in an ideal world(perfect hash functions, random data), but you can construct test-case against stl's implementation knowing the inbuilt hash function and clever test data.

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

            Ok, give me a test which makes a randomized quick-sort quadratic please...

            Anyways I believe the tasks should not be about using the correct implementation of map, but rather about a the Mathematical problem.

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

            Sorry, the difference is quite big.

            Then the question is not about the test but rather why the unordered map performs so horribly bad here?

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

      I wanted to explain how one can screw up contest in three simple steps. Adding unordered was simple trick to magically transform AC into TLE.

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

    Let's guess who will be Sorry_Swistakk.

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

      Haha :D. With my current performance anyone will do ;p.

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

Why this contest is rated? Is it because we have 10 more minutes to deal with the previous 30 minutes' trouble??

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

    Even then, it doesn't make sense. Those users who started working on a problem shortly before Codeforces stopped working, were almost completely unaffected. Whereas other users couldn't do anything during that time. 10 extra minutes for everyone won't fix the disadvantage some participants were already placed in.

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

      At this point I just try to open all the stataements asap. I mean, it doesn't excuse the lags but it helps in case they actually happen.

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

Deleted

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

D was a nice problem !!

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

Editorial??

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

Can anyone tell me why my problem C got TLE when I use unordered_map, but got accepted after I change unordered_map to map, and nothing else? Does it have constant as huge as O(logn)?????

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

    There is anti-hash test for C++ apparently. Ironically enough in Java it is the other way around, HashMap (unordered_map) is fast enough, and TreeMap (map) is too slow.

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

How to prove that phi(phi(...(phi(n))) will become 1 fast enough?

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

    If n can be divided by 2, then we have phi(n)<=n/2, otherwise we will find phi(n) be divded by 2 if n>1.

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

    phi(even) number is atmost half of it. so in 2 steps a number decreases by atleast half of itself. there you go.. O(log N). EDIT : I did not see the others comment before me :P

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

    Note that, for n>2, phi(n) is always even. So, after the first step we will always have even numbers (except the last 1). For even numbers, phi(n)<=n/2 (because all even numbers below n are not coprime with n). So, at every step phi(n) reduces by at least half, which leads to log(n) time.

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

    Thanks guys, I've got it. Sorry for such a stupid question :)

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

D is almost the same as this one if we consider switches as nodes and doors as edges.

And in F, the coloring part is exactly the same as this one.

Such old ideas can hardly surprise me :(

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

    In problem F it wasn't trivial to come up with an easy implementation to build the tree. The coloring part is common by now, therefore I think the complexity wasn't so low.

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

    If somebody wants link for similar to D one where they can submit themselves, this is link.

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

B:failed system test on test 4 ... does the pretest have only 3 test cases?:||

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

The harder version of problem E was already used on Codeforces in our with riadwaw contest: http://mirror.codeforces.com/contest/396/problem/E. (One can say that today's E had a different idea, but no, it does not have an idea).

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

I think we should avoid problems with output Yes/No and small number of pretests. I saw really mad solutions in my room. To be honest they were completely bonkers and those solutions passed pretests. Unfortunately I didn't have the courage to hack them. For me they were equivalent to:

(rand()&1) ? puts("Yes") : puts("No").

On the other hand my solution in which I used n instead of m in one place passed pretests too, which costs me many points.

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

Could anyone explain solution of problem D?

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

How to get Prizes? I didn't receive any message.

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

    We will send you the money in a few weeks. Sorry for the inconvenience caused.

    → Reply