text:
This article was originally written for tmp.0ut volume 2 and is available here: https://tmpout.sh/2/4.html. Due to the unique (read: badass) format of the zine, it is replicated here as plaintext.

# Errata

• In the section Stable interfaces aren't, “and on a kernel older than 4.17” should read “and on a kernel newer than 4.16”

# Article

*** Looking up your article...

:~$head alex.ascii ,,,... ...,........ .*//(((((((/(((((((((####((/*,. .,*/(//(//(((#%%###(##%%%##(#%%%%%#####(*.. .***/((//((##/###(#%&&&&%%%&%%%&&%#%%%%&&&&%%%%#/,. .,**/(/((##%#(((###%%%%%%&@@&&&&&&&&&&&&&@@&&&&&&&&&%(. ..*///#((#(((#%%%##%%%%&&&&&&@@@&&&&&&%%%&%&&&@@@@@@@&&%#*. ,*(/(((((((((###%%%%%%%&%%%&&%%%%%#%###((/////((##%&@@@@&&&%%(*. .*/(/(##(########%#%%%%%%###%%####((((///**********//(((#&&@@@&&&%(, .*/((##############(((////(/*******,,,,,*,,*,,,,*****/////((#%@@&&&%#(*. ,/(/(((####%#(((///**,,,,,,,,,,,,,,,,,,,,,*,,,,,*********//////((&@&&%%&%/. ,/((#((((##(((/**,,,,.....,,,,,,,,,,,,,,,,,,,,,,*************////(%&&%%%%%(. ,*/((##/(##(*...,........,,,,,,,,,,,,,,,,,,,,**,,,*************///(%&&%%%%%/. .*(##(((((#%(,.. .. .......,,,,,,,,,,,,,,,,,,,,,,,,,***********////(#%&&%#%%%(, ,/(((//(##&#*,. ....,,,,,,,.,..,,,...,,,,,,**************/////(#%&%%%%%%%#*. ,(##(###%&%#*. .,*/(#%###((/*,,..,,,..,,*/((##%%%###%%####((////((#%%&%%##%%%#, ,(##(###&%&%#, ,////**,,,,*/(/////*,,,,,,,**/((##%%&%&&&&%%&&%&%#(///(%&&%%&%%%%%#*. ,(%%%#####(%(..*,,**/////*/////*/,**,.,,***/(* .*/(((#(((///*/((#%%#(((%@@%&&&&&%%#((/, ,(###((/. ,,,,///(/*....,///*//(/,.,,,/((.*((/(*,/(##/,,,*((**//((((((%@&&&&@@&%(,. ./((((((%,,,**** /*/##(/,/*.,,***/(.. ...,(*//(#(,.,,**(((**/(((%&@&@@@@&@%*. ./((##%&.,,*, . .//./(//,..**.,**/(*//*,*/(/(#((/,,,***//*,*((###%@@@@@@&&%* ,(##%&(.,,..,,,. . .,.. /.,,**//#(./*,,*,,,.,.,*********,////((&@@@@@@@&&#. ,(##%. ,. . . *. .,**/((*.****,,,,,........,,,,**////#&@@@@@&&&(, .*/* ............... .. ....,**//((/,*/*****,,,,,,,,,**////////&@&&&&&%, ,. ........,,,.............,**//(//*/**,***,,,,,,,*//////////%&%#/*. .. ..........,,,,,,*///**///****,***////***//*/*/////(%(*. .. ........,.,*((#/**//##&#////*,,,,,,,*************///(#(*. .. .......,,,,..,*/*,,,****/(((((/*,,,,,,,,,********/////(((/*, ... . .............,*(((/(//////(####//***,,,,*,,,,*****/////((#/,. .,............,*///(##(///(///((((##%%#((///*,,,********////((##*. ,,,........*/(((#(/**,,,*,,,,,,*//#%%%%%%%##(/******////((((###*. ,.,,,,,.,.*(((((/**//(((/,,,/**/(/(((((#%%%%%%#(//*//((((((###. .,,,,,.,,,(/****/#&#//***,,,,,*//*/(#%%##((((#%#(//(((((((((#( .,,****,,,,,,,,,...,,..,,,,*******////((///**//(#(((((#((((##* ,**,***,,*,,,.........,,,,********///******///*/(((#((((####. ,****,,,,,***,,.....,*///(((((((((//****//(((/(((###(###%%/. .****,,,*/((/*,,....,*//(#((//****/*///(######(((#(##%%&%(. ,*//**/((#((/*****//*//////////(#(##%%%%&%####%#&%&&%/, *##########((**//////(/((/(/#(##%%&&%&&&&%&&&&&&&#, ,#%%&%%%###(((((((//((((((###%%%&&&&&@@&@@@&&&%(, ,/#%&%%%#(##(#(#((########%#%%&&@&@@@@&@&&%#*. .*(%&&%%###(####%#%%###&%&&&@@@@@&&&&%%%#/, .,*(%&&%%%%&%&&&&&&&&&@@@@@&&&&%&%(*. .,*(##%%&%%%&%&&%%%%#((///*,. . ~~[every Boring Problem Found in eBPF] by @FridayOrtiz~~ > /WHOIS @FridayOrtiz *** @FridayOrtiz https://ortiz.sh/contact/ > /LIST *** eBPF, BPF, Linux Kernel, guide, tips +-#- Introduction -#- | | About six months ago I started a new job and dove into adding Berkeley Packet | Filters (BPF) as a telemetry source for our Linux endpoint security agent. This | work culminated in the release of three open source libraries ([0], [1], [2]). | This isn't about that, though. This is about the issues we ran into while | implementing BPF as defenders, and how defenders can use BPF in their | environments (although attackers should find useful tips in here too). I went | through every PR, Jira ticket, and message from the past six months to put | together this list of BPF gotchas and their solutions. I hope it helps | defenders, developers, and researchers ramp up with BPF faster than I did. | | Note: I'm going to use BPF to mean extended BPF (eBPF), since that's the | official name. Not to be confused with the old classic BPF (cBPF). I'm also | going to assume you're *loosely* familiar with BPF, enough to be considering | whether or not to deploy it in your environment. +- +-#- Why even use BPF? -#- | | You may be wondering, "if you're filling an article with caveats about BPF, why | should I even bother trying to use it?" Great question, straw man. There are a | number of things BPF is really, really, good at that you should consider. | | - **You can get visibility (almost) anywhere you want.** If there's a specific | code path within the kernel (or userspace) that you know will be executed during | an attack, you can put yourself there. If there's a payload value in a packet | you need to see before it hits your iptables rules, you can do that. Want to | modify or block syscall args? You can do that too. | | - **You can reinstrument dynamically.** Change your mind about what you want to | inspect? Change it while it's running. You can either swap out the entire | program (although that might not be possible in the future with signed BPF | programs[4]) or modify behavior by updating BPF maps from userspace. | | - **It's safe!** You can do all these things with a Linux Kernel Module (LKM), | sure, but the BPF Virtual Machine (BPF-VM) and verifier ensure (or at least | try really hard to ensure[17]) that you can't panic or break the kernel. | | - **It's container aware, or at least it can be**. Instrumentation alternatives | like auditd tend to struggle in containerized environments, returning values | that only make sense in certain namespaces, or losing track of things entirely. | BPF, on the other hand, can give you information in whatever context you want | (as long as you program it that way). | | - **It's fast.** Do as much work as possible in the BPF program before sending | information up to userspace, and you can avoid expensive context switching or | race-prone data enrichment. | | - **It's atomic (sort of).** BPF programs generally aren't preemptable (there | are exceptions[5]). This applies to tail calls as well, so you can set up some | fairly complex logic in your instrumentation without worrying too much about | reentrancy. +- +-#- The problem with BPF. -#- | | From this writer's perspective, there are two main problems with BPF: 1) it's | now being used in ways it was never designed for (i.e., it's evolving naturally | over time) and 2) there's a large overlap in maintainers of the Linux kernel's | BPF subsystem and userspace BPF tooling. | | The following are concrete issues stemming from (1): | | - BPF isn't really CO-RE (Compile Once - Run Everywhere), it's more CE-RO | (Compile Everywhere - Run Once). A lot of userspace tooling "achieves" CO-RE in | practice by compiling on the host machine. New true CO-RE features are... new. | Chances are you need to support a kernel that doesn't have them. End-of-life | doesn't mean much when the host is running a business-critical function and the | suits see too much risk in upgrading it. And loading a full toolchain to | compile BPF programs on the host is often a no-go too. | | - The toolchains and libraries are designed around bpftrace-like use cases. | That is, one-off tooling for diagnosing specific problems. Brendan Gregg's | book[7] is a great resource for this. Now that BPF for long-running daemons is | gaining popularity, the maintainers are working hard adding features to support | this (like the aforementioned true CO-RE). Unfortunately, again, these features | probably won't exist on the kernels you need to support. | | - There are many different types of BPF programs (which we'll cover), that all | have varying load and run semantics. Depending on whether you want to run a | kprobe or a TC classifier, you'll have to use entirely different methods to do | so. And while you're writing them, the helpers available to you can vary | wildly. And the documentation is incomplete, scattered, and often out of date, | because... | | | And here are some specific examples of issues stemming from (2): | | - Because of the overlap, documentation of the pure BPF interface(s) (there's a | plethora, we'll cover that) is lacking. The people that maintain it write the | userspace tooling, so they don't need in-depth documentation. Seriously, go | check out the BPF manpage for whatever distro you're on. Chances are it's | missing a ton of helpers and there's more than one "TODO: fill this out" that's | been sitting there for years. Why not use their userspace tooling? Well... | | - Their userspace tooling is a magic labyrinth. In order to get close to CO-RE in | a backwards compatible way, it's filled with kludges you probably don't need. | Ideally, you'd interface directly with the underlying syscalls and use only | what you need. But doing that is undocumented. And, because of the | documentation issues, there's really no community drive to simplify these | libraries. Because these libraries cover (until recently, see (1)) the majority | of historical use cases, there's no drive to improve the documentation. Even if | you did, you'd have to backport and patch your documentation to cover all the | little idiosyncrasies across kernel versions, and boy are there a lot of those. +- +-#- Implementation Issues -#- | | While working with BPF we ran into a number of implementation specific problems | that lead to us building and publishing those three ([0], [1], [2]) BPF tools. | If you're a defender, or work in security, and you're considering getting | started with BPF here's a list of things you'll probably want to know. | Presented in somewhat logical order. | | +-**- The verifier sucks, but the alternatives are worse. -**- | | | | -...- Problem -...- | | | | You will run into lots of problems with the verifier. For example, what's the | | difference in the following two code snippets? | | | | c | | u32 *p = 1; | | u32 i = *p; | |  | | | | c | | u32 *p = 1; | | u32 i = NULL; | | __builtin_memcpy(&i, p, sizeof(u32)); | |  | | | | I'll tell you: the first one fails the verifier, the second one does not. But | | only sometimes, except when it works. Which depends on the kernel version. | | Maybe. I mean, they should compile to the same thing, right? Apparently not, | | and subtle differences can completely throw the verifier off. | | | | The real problem with the verifier is that it's getting better all the time. As | | BPF use cases settle out, the maintainers are changing the BPF verifier to | | better support them. That means on older kernel versions, without these | | patches, you'll have to perform strange workarounds to get your code working | | with older verifiers. | | | | A few more verifier problems you'll likely encounter supporting a wide range of | | kernel versions: | | | | - The verifier hates looping. But, sometimes, it also hates loop unrolling. If | | clang generates enough jumps and gotos, even if you tell it to unroll | | everything, the verifier might (depending on version) fail it anyway. The | | verifier needs to be able to keep track of all branches and ensure a maximum | | depth limit. If it can't (whether it's because you're looping or because the | | verifier can't keep up) your program will fail to verify. | | | | - In older kernel versions (but not newer ones) variable reads and writes are a | | big no-no. All offsets must be known at compile time. That means you can't do | | things like set some_array[variable_index] = some_value. This, plus the | | aversion to loops, makes it nearly impossible to read strings from memory on | | kernels without the read_str family of helpers. The kernel's own qstr | | involves variable memory access—and good luck finding (or setting) the null | | terminator on your own. | | | | - Everything that might be a pointer must be null checked. If you don't, the | | verifier will refuse to load your program even if it's safe. This makes it hard | | to work with programs that might expect a null value. The convention that most | | pleases the verifier is to return immediately after a failed null check, and | | getting around this is tricky and involves trial and error. | | | | There are alternatives to the kernel verifier, such as PREVAIL[8], but they | | have their own set of issues. For what it's worth, PREVAIL is an impressive | | project and Microsoft will be basing their Windows BPF verifier off of it. But, | | unfortunately, it doesn't match the expected behavior of kernel verifier. Just | | because something passes PREVAIL doesn't mean it will pass the kernel verifier. | | Just because something fails PREVAIL doesn't mean it will fail the kernel | | verifier (even though it probably should). | | | | -...- Solution -...- | | | | **Run early, run often, run everywhere.** Your development environment should | | make it as easy as possible to test your code on all the kernels you need to | | support (or as close to a representative sample as you can get). The only way | | to know if the kernel verifier will accept your program is to run it through | | the kernel verifier, the real kernel verifier, on the specific kernel you're | | targeting. Note that this means the distro-specific kernel, with all their | | modifications and backports. For example, the older Enterprise Linux (red hat, | | centos, and so on) kernels (2.x and 3.x) have backported BPF features that | | might surprise you, since they don't line up with mainline kernel version | | numbers. The only way to know what's supported is to try it. | | | | **Enable logging.** This one comes with a caveat. You need to provide the | | verifier with a large buffer of memory to write its verification logs into. If | | you don't give it enough space it will fail verification, even if the program | | would otherwise pass. If your programs are complex, then make sure your buffer | | is large enough (but not too large, or loading will take forever) and be sure | | to turn off verifier logs in production to avoid issues with programs failing | | to load when you know they should. | | | | **The error messages you get will seem cryptic at first.** The BPF verifier | | uses a lot of terminology and has a lot of restrictions that are undocumented | | (of course) that you'll learn with time. If you get stuck, the BPF Compiler | | Collection (BCC) GitHub repo's issue tracker[9] is a great resource. You can | | probably find a Brendan Gregg ticket that goes over at least the broad class of | | error you're getting. | +- | | +-**- BPF doesn't really exist. -**- | | | | -...- Problem -...- | | | | BPF is really just an instruction set, for which the Linux kernel provides a | | VM, verifier, and some helper functions. You run your programs inside this | | execution context, and call the helper functions to extend the VM's | | capabilities. When you write a BPF program, what you're really writing is a | | kprobe, or a uprobe, or an eXpress Data Path (XDP) classifier, or a Traffic | | Control (TC) classifier, or one of the many other types of kernelspace programs | | that have been offloaded to the BPF subsystem. There's a ton of BPF program | | types and more are being added all the time, for a variety of use cases. It | | turns out being able to safely execute code in the kernel enables a ton of | | interesting and helpful functionality. Unfortunately, every program type has | | its own way to load, run, and clean up after it, most of which is entirely | | undocumented. | | | | On certain distros, the tools you'll need to load these programs might not be | | enabled by default. For example, some distros don't automatically mount | | debugfs, which you'll need to load kprobes on older kernels. | | | | When you do figure out how to load your program, the ABI for defining programs | | is entirely based on undocumented, implicit, convention. For example, you'll | | see a lot of SEC("kprobe/my_kprobe") to tell the loader that you're loading a | | kprobe. | | | | c | | /* helper macro to place programs, maps, license in | | * different sections in elf_bpf file. Section names | | * are interpreted by elf_bpf loader | | */ | | #define SEC(NAME) __attribute__((section(NAME), used)) | |  | | | | This is actually entirely unnecessary, on the syscall level, and is merely a | | common convention. As you can see in the above snippet, it's just a macro to | | set the section name in the compiled ELF executable. There's nothing | | BPF-specific about it. So you not only have to know the requirements of the | | program type you're trying to load, but also the conventions used by the tools | | that load and run it. | | | | -...- Solution -...- | | | | Figure out what you want your program to do first. Do you want visibility into | | the kernel? Then you'll probably want a kprobe or tracepoint. Do you want to | | drop inbound packets? You probably want XDP. Do you want to build detections on | | outbound traffic? You might want TC, or you might want a kprobe in the kernel | | network stack. Figure this out, then figure out what you're going to need to | | run it the way you want to run it (one off? daemon?). When we made oxidebpf | | we had to optimize for stability in the features we needed most (e.g., kprobes) | | over coverage of all the different BPF program types. | | | | If you can't find libraries to suit your needs for your chosen program type, | | you'll probably have to write it yourself (or contribute it to an open source | | project). Because everything is poorly documented, you'll have to dig through a | | lot of source code to put together the real set of necessary functionality. The | | official-ish libraries like libbpf and libbcc tend to work the best, but | | there's issues there (that we'll get to). | | | | I highly recommend using bpftool for debugging while developing. It provides | | the easiest-to-use view into what programs and maps are loaded and where. It | | lets you visualize data in maps, dump programs, and more. The only problem with | | bpftool is that it's never in the same package. Some distros and repos let | | you install it with a yum install bpftool. Others require you apt-get | | install linux-oem-tools. Sometimes you need to apt-get install | | linux-oem-tools-uname -r. It depends. Whatever you're running, though, | | you'll probably want this tool installed. | +- | | +-**- I hope you find constraints fun. -**- | | | | -...- Problem -...- | | | | Are you one of the dozen or so people unreasonably upset that 0x10c[10] was | | never released? Me too! I find working within constraints challenging and | | enjoyable. And let me tell you, BPF programs have a lot of constraints. | | | | You get 512 bytes of stack space for your program, half a kilobyte. This | | doesn't appear to be something that has or will ever change. It's also unclear | | if this applies to tail calls. Some documentation implies that tail calls use | | the same stack space, so you're limited to 512 bytes total, but in practice it | | seems to be 512 bytes per program. And clang probably won't be able to help | | you. BPF programs, for whatever reason, don't like to reclaim stack space. Your | | variables will get hoisted and instantiated at the start of execution. If you | | want to do things like dump syscall arguments or pt_regs, especially when | | working with strings, you'll find yourself running out of stack space very | | quickly. | | | | There's a practical instruction limit of about 4096 instructions. The | | instruction limit in the past was set (as far as I can tell) based on what the | | verifier could verify before declaring "this has gone on too long, I can't | | verify this won't halt, so I'm failing it." You can get more instructions by | | manipulating the verifier, and doing other tricks you'll find in the mailing | | lists, if you really want to put in the effort. Newer verifiers let you get | | upwards of 1,000,000 instructions, but that'll only help you if you're | | supporting newer kernels. | | | | -...- Solution -...- | | | | To work around the instruction limit, you can use tail calls. Tail calls are | | the closest BPF has to a true function call. You transfer flow over to | | whichever program you call into. You can chain tail calls like this together up | | to 33 times. There are some caveats, which we'll get to later. | | | | There are a few tricks you can use to work around the stack limit. One trick is | | to explicitly reuse stack space. For example, reusing variables or | | instantiating a struct of bytes to act as your scratch space and manually | | reusing offsets within it. Another trick is to build your own stack with maps. | | On some kernel versions you can request a struct from a map and get a pointer | | to it. If the requested struct doesn't exist (e.g., the array map at the | | requested index was empty) you'll still get back a pointer to an empty struct | | that you can manipulate. Other kernel versions require this map-struct to be | | copied to the stack before being modified, so your mileage may vary. | | | | With all that said, I want to offer some practical advice. If the information | | you're retrieving is too big to ever fit on the stack, you should just send it | | out as you read it. Create a messaging type and pipeline for chunking and | | rebuilding data in userspace, copy as much as you can to the stack, and then | | send it up through a map. This will run on a wider range of kernel versions, | | and you won't have to worry about if your host kernel allows directly | | manipulating and emitting map memory. You can reconstruct it in userspace at | | will. This is what companies like Google are doing for their BPF telemetry. | +- | | +-**- The good stuff is GPL. -**- | | | | -...- Problem -...- | | | | All the useful helper functions (like perf_event_output[6]) are exported as | | GPL-only. If you want your program to do anything useful, you're going to have | | to license it under GPL. That makes it hard to make proprietary programs based | | on BPF. If your program is only internal, and never distributed, you're fine. | | But if you start distributing your programs (to customers, friends, wherever) | | you need to publish it under GPL. | | | | -...- Solution -...- | | | | Short answer: Make the world a better place, release your BPF code and tools. | | | | Long answer: BPF is still a niche and complex discipline, so open sourcing your | | tooling doesn't reduce competitive effectiveness for a business. From an | | individual perspective, open sourcing your tooling gets your name out there and | | makes you more valuable as an employee. From an employer perspective, the more | | accessible BPF becomes the easier it will be to hire people to build and | | maintain it. From the community perspective, we can all learn from each other | | by working in the open. Perhaps you have an interesting use case that the | | maintainers of other libraries would want to know about, or could offer advice | | on. Everybody wins. | +- | | +-**- By default, you get the default. -**- | | | | Alternatively, BPF is only good with containers if you tell it to be. | | | | -...- Problem -...- | | | | Be careful with the assumptions you make about the information you retrieve | | from a BPF program. If you grab the retcode of a fork call, it's going to | | give you the retcode of the fork call: the pid in the namespace of the | | calling process. Maybe this is what you wanted, or maybe you really wanted the | | pid of the child process un-namespaced. Maybe you ask the BPF program to gather | | the pid (with the get_pid_tgid helper). You take the upper 32 bits, | | corresponding to the pid, but nothing lines up. Well, you're executing in | | kernelspace which means the pid you probably want is actually the tgid, and | | what you got was a tid. Unless you wanted a tid, in which case you should | | get the pid. The kernelspace understanding of a pid is not the same as the | | userspace understanding of a pid. If you want to identify a file, you | | probably want the inode number and device number, a file descriptor won't be as | | useful. | | | | -...- Solution -...- | | | | If you want your program to retrieve information, think about what information | | you need to retrieve. Make sure you know where that information exists (what | | structs, where they live in memory, and how to get there) and then find a place | | (assuming you're launching a kprobe) in the kernel you can attach your program | | as close to that information as possible. For example, if you really need the | | root namespace pid of the child process of fork, you probably want to hook | | somewhere in the path of the new child process so you can grab the pid from | | the task_struct. | | | | Be aware that this location might change between kernel versions, or the | | information may take a different form. You may have to choose a less optimal | | probe point that is available on more systems. Or you may have to change the | | information you're gathering to something else that exists on all the kernels | | you support. That leads us to the next two issues. | +- | | +-**- CO-RE (probably) won't help you. -**- | | | | -...- Problem -...- | | | | The maintainers are constantly adding feature to help BPF developers compile | | once-run everywhere their BPF programs. Unfortunately, you'll likely find | | yourself trying to target kernel versions that don't have these features. Or, | | if you do, since these features are added in piecemeal, it may not have all the | | CO-RE features you expect. | | | | For example, the BTF feature makes it possible to reference struct members | | directly, even if they've been compiled in a randomized layout, across | | different kernel versions, and without recompiling. This feature was added in | | April of 2018[11]. You will probably need to write code for kernels from before | | April 2018. This means something like current->real_parent->pid is not | | guaranteed to work without recompiling for (or on) the host. | | | | -...- Solution -...- | | | | There's really no way around this one. It's what we're doing, Microsoft is | | doing it too for their Linux machines, and I'm sure there are others. First, | | you determine the offsets of struct members for your desired kernel version and | | then you load them dynamically into your BPF program at runtime. For example, | | this code snippet from [12] shows how we read struct offsets from a map and use | | that in our bpf_probe_read to retrieve values. | | | | c | | static __always_inline int read_value( | | void *base, u64 offset, void *dest, size_t dest_size | | ) | | { | | /* null check the base pointer first */ | | if (!base) | | return -1; | | | | u64 _offset = (u64)bpf_map_lookup_elem(&offsets, &offset); | | if (_offset) | | { | | return bpf_probe_read(dest, dest_size, base + *(u32 *)_offset); | | } | | return -1; | | } | |  | | | | To actually find these offset values in the first place, we built the | | linux-kernel-component-cloud-builder, or LKCCB, which builds hundreds if | | not thousands of kernel modules with debug enabled for all our target kernel | | versions and extracts structure offset information from the LKM's DWARF debug | | info[1]. | +- | | +-**- Stable interfaces aren't. -**- | | | | -...- Problem -...- | | | | You'll often find, when working with the kernel, that there aren't as many | | stable interfaces as you thought there'd be. Even syscalls, which are supposed | | to be a big part of the stable user interface, aren't necessarily stable. | | | | For example, if you somehow traveled back in time and wanted to monitor process | | forks, you'd probe the fork syscall. That'd work fine for a bit, until | | clone is introduced. If you stopped paying attention, you'd lose your data | | altogether when glibc (and everything with it) switched fork() to be a | | wrapper around clone(). | | | | Maybe you want to get the arguments of a syscall. Should be easy, you're given | | pt_regs, just access the registers that hold the arguments! Except if you're | | on x86_64, and on a kernel older than 4.17, you'll probably be given the | | pt_regs of the syscall wrapper function, that in turn calls the real syscall | | function. And of course, it all shuffles around if you need to add aarch64 | | support, which has its own set of calling conventions. | | | | Sometimes a symbol that's marked as being exported can't be attached to, almost | | inexplicably. Usually this is due to GCC inlining the function, and the symbol | | being renamed to something like symbol_name.part.1213. Trying to bind | | symbol_name won't work. | | | | -...- Solution -...- | | | | For different architectures you can probably get away with macros that | | conditionally compile depending on what architecture you're targeting, and then | | building one copy per architecture. For the syscall wrappers, you can do | | something similar but build targeting different kernel versions. In practice, | | you may find you need many variants and copies of a single program, all with | | slight differences, to support different kernels and architectures. | | | | For the symbol name problem, it comes back to run early and run often. It's | | often worth spinning up a VM of a few of the kernels you're targeting and | | double checking that the locations you're hooking are indeed in | | /proc/kallsyms. Sometimes you'll find the functions you were looking at don't | | exist in different versions, or have been renamed and relocated. I recommend | | getting comfortable with Bootlin's Elixir cross referencer (but you still need | | to run and see, because distros do their own backports which won't match what's | | in the mainline cross referencer). | +- | | +-**- Running BPF programs as intended involves magic. -**- | | | | -...- Problem -...- | | | | If you use libbcc, libbpf, bpftrace, or any other other high level BPF tools | | you'll quickly notice that they do a lot of magic for you. BCC (the python | | interface) will more or less rewrite your programs for you so they work on your | | host system. You'll end up getting error messages on code that the library | | wrote for you. They also help you get around CO-RE limitations by compiling on | | the host, and using different tricks and kludges to get the same program code | | to operate in many environments as cleanly as possible. This doesn't help a ton | | when you need to build and distribute actual raw BPF programs in their own ELF | | file. | | | | These libraries are also pretty convoluted. There's a lot of overlap in | | maintainers between these libraries and the people working on BPF in the | | kernel, so documenting the interactions isn't a priority. But you don't | | actually need all the stuff these libraries are doing. After a while, | | especially with the rewriting, you'll find yourself wanting to write and load | | pure BPF C code. Here's a snippet of a map I put together when trying to figure | | out what syscalls were actually being made when libbpf loaded a program. | | | |  | | KProbe | | |-> bpf_attach_kprobe() | | |-> bpf_attach_probe() | | |-> bpf_try_perf_event_open_with_probe() | | |-> bpf_find_probe_type() | | |-> bpf_get_retprobe_bit() | | |-> syscall(__NR_perf_event_open) | | |-> create_probe_event() | | |-> enter_mount_ns() | | |-> setns() | | |-> exit_mount_ns() | | |-> setns() | | |-> bpf_attach_tracing_event() | | |-> ioctl( PERF_EVENT_IOC_SET_BPF ) | | |-> ioctl( PERF_EVENT_IOC_ENABLE ) | | |-> bpf_close_perf_event_fd() | | |-> ioctl( PERF_EVENT_IOC_DISABLE ) | |  | | | | These libraries are also GPL, which means your userspace program would end up | | being licensed under GPL and not just your BPF programs. As great as this is | | for users, if you work for a company that likes to make money you might not be | | allowed to touch GPL. It might even be in your contract. | | | | -...- Solution -...- | | | | If you're writing complex BPF programs for security, you'll probably want to | | write it in C without the "help" of something like BCC. You'll also want a bit | | more control and transparency when loading and attaching your programs. In my | | experience, libbpf wasn't great at cleaning up after itself and it got | | frustrating. | | | | Use a clean, simple, library built from the ground up for loading BPF in your | | language of choice. For Rust, aya[16] is a good one, and I worked on | | oxidebpf[0]. Golang also has some good options. One common theme of these | | projects is the amount of effort that went into reverse engineering the | | undocumented program loading logic and reimplementing it. Take advantage of | | that work and use it to load your programs. They're also permissively licensed! | +- | | +-**- Speed kills. -**- | | | | -...- Problem -...- | | | | After getting into BPF, you may benchmark a few of your programs and be | | surprised at how much faster BPF is than what you've been using before, like | | audit. This makes it very tempting to trace and probe more than you probably | | should. For example, if you want to trace socket closes you may be tempted to | | put a kprobe on the close syscall. This syscall is called all the time, and | | probing it will slow your system down unnecessarily. Most of the messages will | | be discarded since you only care about sockets. There are plenty of other | | interesting areas that can't be reasonably instrumented due to the performance | | impact. | | | | -...- Solution -...- | | | | Trace only what you need, and scope it down as much as possible. Going back to | | the close example, you'd be better off probing somewhere downstream where the | | individual tcp_close or udp_close functions are called. | | | |  | | struct proto tcp_prot = { | | // ... | | .close = tcp_close, | | // ... | | }; | | EXPORT_SYMBOL(tcp_prot); | | | | struct proto udp_prot = { | | // ... | | .close = udp_lib_close, | | // ... | | }; | | EXPORT_SYMBOL(udp_prot); | |  | | | | Brendan Gregg's book[7], again, has a great table that shows the overall | | performance impact of tracing different points in the kernel. You could also | | just reason intuitively about how often you think each area you want to probe | | is exercised. The more commonly a code path is executed, the more expensive it | | will be to probe it. | | | | Even after doing your best to scope down and optimize your BPF programs, you'll | | probably want to run benchmarks as you tweak things to see what performs best | | in your target environment. Flamegraphs[13] are a great way to see where most | | of your overhead is coming from, especially if combined with a benchmarker like | | UnixBench[14]. The results may surprise you. | | | | I'd also recommend processing BPF events in batches. You'll probably be sending | | out a lot of information through maps that needs to be read from userspace. If | | you're getting information that's too big for the stack, the information will | | be sent in chunks that need to be reconstructed in userspace. It's definitely | | possible to loop a blocking poll+read on the perfmap or BPF ring buffer, but | | doing so will result in significant overhead. You're much better off letting | | the buffers fill a bit, and processing them in batches (batch process, don't | | stream process). Doing that netted me significant performance gains in | | benchmarks for the BPF programs I write at work. | +- | | +-**- Don't Panic. -**- | | | | -...- Problem -...- | | | | BPF programs will generally live as long as something holds a file descriptor | | that points to them. However, sometimes you need to manually clean up after | | them (such as when using debugfs). If your userspace program crashes or | | panics things may not get cleaned up properly. This can lead to all sorts of | | problems when you restart your probes, such as receiving duplicate events. | | | | If you're building short lived, one off, tools this is less of a concern. But | | if you're managing several probes as part of a long-lived monitoring daemon | | then this is something you need to be careful with. | | | | -...- Solution -...- | | | | Make sure you design the userspace component of the BPF program to keep your | | programs alive for as long as you'll need them. Gracefully handle all errors in | | the thread that keeps your BPF programs alive and make sure you clean up after | | yourself in the event of failure or shutdown. Keep in mind that many older BPF | | tools are built around short-lived programs, meant for things like bpftrace | | or production debugging. | +- | | +-**- Know your limits. -**- | | | | -...- Problem -...- | | | | Your program will have instructions and will probably use maps. These take up | | space, which the BPF syscall will handily memlock for you. On many distros, | | this is fine. On others, however, the default memlock ulimit is quite low[15]. | | See the following output of ulimit -l on various distributions. | | | |  | | [email protected]:~$ ulimit -l
| | 65536
| | [[email protected] ~]\$ ulimit -l
| | 64
| | [email protected]:~> ulimit -l
| | 64
| |
| |
| | If you can't memlock enough memory to fit your instructions and maps, you'll
| | get rejected with cryptic verifier error messages.
| |
| | -...- Solution -...-
| |
| | Calculate the amount of memory your programs and maps will need, and check the
| | memlock limits on your target systems. You may be fine, or you may need to
| | raise it first. Some libraries (like the one we wrote![0]) can try to take care
| | of this for you.
| +-
|
| +-**- Tail calls aren't guaranteed. -**-
| |
| | -...- Problem -...-
| |
| | Think of tail calls like the BPF equivalent of execve, except less powerful.
| | It'll start running a new probe, with the original context argument, and
| | replace everything you were previously doing. You can't provide it with custom
| | arguments, and the tail call needs to pass the verifier independently. This
| | means if you want to communicate between tail calls you'll need to use maps.
| | You're also limited to chaining 33 tail calls in a single execution, after that
| | the tail call execution will simply fall through.
| |
| | You can't call into another program with a tail call directly, either. You need
| | to reference an index in a tail call program map (a type of BPF map) which
| | needs to be set from userspace. For example, if you want to tail call from
| | prog_a() into prog_b(), you'll need to load prog_a() and prog_b()
| | first. At this point if prog_a() fires, the tail call into prog_b() will
| | fizzle. Then, from userspace, you need to update a map to say "prog_b() is at
| | index 5, if anyone tries to tail call into index 5, send them to prog_b()."
| | Tracking and maintaining all these indexes can be cumbersome.
| |
| | And there's not always a guarantee that the tail call will fire. You could
| | reach an execution limit, or a memory limit, or some other weird verifier edge
| | case that prevents the tail call from firing. Your programs need to handle this
| | gracefully.
| |
| | -...- Solution -...-
| |
| | First, you'll have to write your tail calls as though they were independent
| | programs. Think of designing each one to grab a different bit of information
| | you're looking for. If you find yourself re-calculating the same things in each
| | program or otherwise need to communicate across calls, store and retrieve
| | information from a map.
| |
| | For managing indexes, use an enum for your tail calls and reference that from
| | your userspace application. For example, have an enum tail_calls { PROBE_A,
| | the program map from userspace. The file descriptor for probe_a() goes at
| | index PROBE_A, and so on. If you want to call into probe_a(), you get there
| | by asking for PROBE_A with bpf_tail_call(ctx, &tail_call_table, PROBE_A);.
| |
| | Your program should also have a plan for what happens if the tail call doesn't
| | go off. Do you want to send up an error? Ignore it? Send up a message that
| | execution was completed? Something else? For example, if you're using recursive
| | tail calls to read a string value you may want to return a message that says
| | you hit your tail call limit before you finished reading the string.
| +-
|
| +-**- You can't just return what you want. -**-
| |
| | Alternatively, you're on your own with error handling.
| |
| | -...- Problem -...-
| |
| | This one was a problem that we didn't even realize we had because it was so
| | subtle. In C it's pretty customary to return 0 on success and -1 (or some
| | other negative error code) in the event of a failure. The actual returned value
| | is usually written to a buffer or some other pointer given as a function
| | parameter. You check the return code for success or failure and take actions
| | appropriately (in theory). While writing BPF programs in C, especially kprobes,
| | you might be tempted to follow this pattern. After all, it makes sense. The
| | actual value you return is sent out through perf or written into a map so
| | userspace can grab it, so the return value of the probe itself should be 0 to
| | indicate success or -1 to indicate failure, right?  Just like every other C
| | program? Wrong! For program types other than kprobes (remember, BPF is just an
| | execution environment) it's more obvious that the return codes have special
| | meaning.  For example, XDP programs have explicit return codes to drop, pass,
| | or re-process packets.
| |
| | For kprobes, return 0; means "I'm done with this kprobe, you can move on."
| | You indicate that you want to keep the probe hanging around with _literally any
| | other return code_ (including return -1;).  That's probably not what you
| | want. Take a look at this function from the kprobe handler in [18]:
| |
| | c
| | /* Kprobe profile handler */
| | static int
| | kprobe_perf_func(struct trace_kprobe *tk, struct pt_regs *regs)
| | {
| | 	// ...
| | 	if (bpf_prog_array_valid(call)) {
| | 		// ...
| | 		ret = trace_call_bpf(call, regs);
| |		// ...
| | 		if (!ret)
| | 			return 0;
| | 	}
| |
| | 		return 0;
| |
| | 	dsize = __get_data_size(&tk->tp, regs);
| | 	__size = sizeof(*entry) + tk->tp.size + dsize;
| | 	size = ALIGN(__size + sizeof(u32), sizeof(u64));
| | 	size -= sizeof(u32);
| |
| | 	entry = perf_trace_buf_alloc(size, NULL, &rctx);
| | 	if (!entry)
| | 		return 0;
| |
| | 	entry->ip = (unsigned long)tk->rp.kp.addr;
| | 	memset(&entry[1], 0, dsize);
| | 	store_trace_args(&entry[1], &tk->tp, regs, sizeof(*entry), dsize);
| | 	perf_trace_buf_submit(entry, size, rctx, call->event.type, 1, regs,
| | 	return 0;
| | }
| |
| |
| | There's two things you should notice in that snippet. The line ret =
| | trace_call_bpf(call, regs); and if (!ret) return 0;. That means if
| | trace_call_bpf() returns _anything but 0_ (including -1) we go through
| | the remainder of the function, buffer allocation, trace argument storage, and
| | so on. We can grab the internals of that function at [19]:
| |
| |
| | c
| | /**
| |  * trace_call_bpf - invoke BPF program
| |  * @call: tracepoint event
| |  * @ctx: opaque context pointer
| |  *
| |  * kprobe handlers execute BPF programs via this helper.
| |  * Can be used from static tracepoints in the future.
| |  *
| |  * Return: BPF programs always return an integer which is interpreted by
| |  * kprobe handler as:
| |  * 0 - return from kprobe (event is filtered out)
| |  * 1 - store kprobe event into ring buffer
| |  * Other values are reserved and currently alias to 1
| |  */
| | unsigned int trace_call_bpf(struct trace_event_call *call, void *ctx)
| | {
| | 	unsigned int ret;
| |
| | 	// ...
| |
| | 	/*
| |      * ...
| | 	 */
| | 	ret = BPF_PROG_RUN_ARRAY(call->prog_array, ctx, bpf_prog_run);
| |
| | 	// ...
| |
| | 	return ret;
| | }
| |
| |
| | As you can see, this is the function that actually invokes the kprobe. It gets
| | ret, which it returns, from BPF_PROG_RUN_ARRAY() which, as you might
| | expect, runs the BPF program. The documentation on this function is also pretty
| | explicit, which is nice. When we return 0, we've returned from the kprobe and
| | don't need to keep any details about it hanging around. When we return 1
| | (which anything besides 0 aliases to) we store information about the kprobe
| | in a ringbuffer for later.
| |
| | -...- Solution -...-
| |
| | The solution here is to always return 0; in your kprobes, unless you have an
| | explicit need to return 1;. If you want to know if your kprobe failed or is
| | in some incomplete state, you'll need to architect your message-passing to
| | handle that case. For example, you might want to include a success code flag in
| | the struct(s) you pass through a perfmap which you can check for failure. Or
| | you might want to build your system around a best-effort event reconstruction
| | for more complicated returns involving multiple messages. In any case, you'll
| | have to engineer your error checking and handling independently of the BPF VM
| | system. Those return codes are reserved, you gotta make your own.
| +-
+-

+-#- Wow, that looks hard. Can you summarize it for me? -#-
|
| Certainly! BPF is really good at getting visibility (almost) anywhere in the
| entire system, it allows dynamic reinstrumentation, can be made container
| aware, is faster than alternatives, and is (usually) safe to run as long as you
| can load it. Consider using BPF if any of the following apply to you:
|
| - You have the in-house resources and expertise to build and maintain a
| long-lived BPF telemetry source.
|
| - You only want to use BPF for live debugging or other short-lived, one off, use
| cases such as bpftrace.
|
| - You're lucky enough to only have to support a single kernel version.
|
| - You don't really care if the project succeeds, you just want to get experience
| with BPF (this might legitimately apply in R&D orgs).
|
| If you don't have the resources and need to support a wide range of kernels,
| you might be better off looking for an alternative (there are many free and
| open source options thanks to GPL), or paying someone else to build it for you.
|
| Long running BPF programs for security are a relatively new use case. The
| tooling around this use case is getting better all the time, but there's still
| a lot to consider before diving in.
+-

+------[references]--------------------------------------------------------------------------+
|  [0]: [https://github.com/redcanaryco/oxidebpf]                                            |
|  [1]: Will go public Soon(TM) at                                                           |
|       [https://github.com/redcanaryco/linux-kernel-cloud-component-builder]                |
|  [2]: [https://github.com/redcanaryco/redcanary-ebpf-sensor]                               |
|  [4]: [https://lwn.net/Articles/870269/]                                                   |
|  [5]: [https://lwn.net/Articles/812503/]                                                   |
|  [6]: [https://elixir.bootlin.com/linux/latest/source/kernel/trace/bpf_trace.c#L646]       |
|  [7]: [https://www.brendangregg.com/bpf-performance-tools-book.html]                       |
|  [8]: [https://github.com/vbpf/ebpf-verifier]                                              |
|  [9]: [https://github.com/iovisor/bcc/issues]                                              |
| [10]: [https://en.wikipedia.org/wiki/0x10c]                                                |
| [11]: [https://lwn.net/Articles/752047/]                                                   |
| [12]: [https://github.com/redcanaryco/redcanary-ebpf-sensor/blob/main/src/programs.c#L393] |
| [13]: [https://github.com/brendangregg/FlameGraph/]                                        |
| [14]: [https://github.com/kdlucas/byte-unixbench]                                          |
| [15]: [https://linux.die.net/man/5/limits.conf]                                            |
| [16]: [https://github.com/aya-rs/aya]                                                      |
| [17]: [https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=BPF]                               |
| [18]: [https://elixir.bootlin.com/linux/latest/source/kernel/trace/trace_kprobe.c#L1568]   |
| [19]: [https://elixir.bootlin.com/linux/latest/source/kernel/trace/bpf_trace.c#L95]        |
+--------------------------------------------------------------------------------------------+


text:
# Complex algebra problem (roots)

1. Aug 12, 2015

### Remixex

1. The problem statement, all variables and given/known data
First off i wasn't sure if i should put this in precalc or here so i just tossed a coin

I must find the roots of the expression z^4 +4=0 (which i've seen repeatedly on the internet)
Use it to factorize z^4 +4 into quadratic factors with real coefficients
The answer is (z^2 + 2z + 2)(z^2 - 2z + 2)

2. Relevant equations
Just the one given on the top

3. The attempt at a solution
Ok so, the question is quite basic as i've seen people pull it off in 10 mins, BUT after 3 semesters of dealing with only real numbers i forgot about complex ones, and now that i took complex analysis i'm in trouble D:
First off i had to search Euler's identity, that's how lost i was
I managed to establish that the magnitude of Z (r) is sqrt(2), i also got to the point where phi is -pi/4 +k*pi/2
so the 4 roots would be given by the sqrt(2) * e^i*phi given k takes the values within (0,1,2,3)
This is where i die i have no idea how to turn those into the final equation, i know the 4 solutions are
(+/-)1 (+/-)i, and from there is just polynomial algebra, but i don't know how to get there, Am i supposed to be able to deduct this as obvious from my last step?
Thanks in advance, i firmly believe there are no such thing as dumb questions, but given this is something I'm supposed to manage, it's quite the candidate :D

2. Aug 12, 2015

### Ray Vickson

You can write $-1$ as
$$-1 = e^{i \pi} = e^{3 i \pi} = e^{-i \pi} = e^{-3 i \pi},$$
so the four 4th roots of $-1$ are obtained by taking 1/4 of the argument of each of the above. That is, the four roots $r_1,r_2,r_3,r_4$ are
$$r_1 = e^{i \pi/4} = (1+i)/ \sqrt{2}, \; r_2 = e^{i 3 \pi/4} = (-1 + i)/ \sqrt{2} \\ r_3 = e^{-i \pi/4} = (1-i)/ \sqrt{2}, \; r_4 = e^{-i 3 \pi/4} = (-1-i)/ \sqrt{2}$$
From these you can determine the four 4th roots of $-4$.

Note that $e^{i \theta} = \cos(\theta) + i \sin(\theta)$, so we can easily write the four roots in $a + ib$ form, just using elementary geometry/trigonometry.

format: plain


text:
# Uniform regularity for the Navier-Stokes equation with Navier boundary condition - Mathematics > Analysis of PDEs

Abstract: We prove that there exists an interval of time which is uniform in thevanishing viscosity limit and for which the Navier-Stokes equation with Navierboundary condition has a strong solution. This solution is uniformly bounded ina conormal Sobolev space and has only one normal derivative bounded in$L^\infty$. This allows to get the vanishing viscosity limit to theincompressible Euler system from a strong compactness argument.


text:
# Lessons 1–5Self Assessment 1

For each statement, rate your understanding according to the continuum, and then provide evidence for your rating.

I understand and can do it accurately.I understand most of the time, but I’m still working on it.I don’t understand this yet.
I can

graph a quadratic function in the form: .

Evidence Rating

I can

write the equation of a quadratic function, given the graph of a parabola.

Evidence Rating

I can

determine if a trinomial is a perfect square.

Evidence Rating

I can

complete the square to convert a quadratic function to vertex form.

Evidence Rating

## Next steps

My plan for mastering this content is…

# Lessons 6–10Self Assessment 2

For each statement, rate your understanding according to the continuum, and then provide evidence for your rating.

I understand and can do it accurately.I understand most of the time, but I’m still working on it.I don’t understand this yet.
I can

factor a trinomial.

Evidence Rating

I can

factor an expression in the form: .

Evidence Rating

I can

graph a quadratic function in the form: .

Evidence Rating

I can

be efficient and accurate in converting from one quadratic form to another in order to have the form that is most useful for finding what I need.

Evidence Rating

## Next steps

My plan for mastering this content is…


text:
#### Bilkent University Topology Seminars

Cohomology of Infinite Groups Realizing Fusion Systems
Muhammed Said Gündoğan
Bilkent University, Turkey
Özet : Given a fusion system F defined on a p-group S, there exist infinite group models, constructed by Leary and Stancu, and Robinson, that realize F. We study these models when F is a fusion system of a finite group G. In this talk we mention our result which relates the cohomology of an infinite group model π to the cohomology of the group G. Also, we mention a family of examples for which the cohomology of the infinite group obtained using the Robinson model is different than the cohomology of the fusion system. This is a joint work with Ergün Yalçın.
 Tarih : 01.04.2019 Saat : 13:40 Yer : Bilkent Matematik Bölümü Seminer Odası SA - 141 Dil : English


text:
# IOP HEPP Particle Physics 2009

6-8 April 2009
University of Oxford
Europe/London timezone

## Spin correlation in top quark pair produciton at ATLAS

7 Apr 2009, 11:30
15m
Martin Wood Lecture Theatre (University of Oxford)

### Speaker

The high mass and large width of the top quark corresponds to a Standard Model prediction for a lifetime shorter than the timescale for strong interactions, implying that the top quark decays before hadronisation. Therefore, properties such as the spin correlation in the $t\bar{t}$ system are transferred to the decay products. In this talk I will discuss the possibility of measuring this correlation with early ATLAS data.


text:
### mohammedehab2002's blog

By mohammedehab2002, 8 months ago, ,

Hi!

I'm back with not one, not two, but three contests, although I have no promises about when to expect them....

The first of them, codeforces round #563, will take place on Jun/03/2019 17:05 (Moscow time). It's rated for the second division, but, as usual, first division participants can take part out of competition.

I'm the problemsetter of the round. I'd like to thank KAN for coordinating the round (and his patience .. try coordinating ~20 problems), arsijo for helping with the preparation, Um_nik, opukittpceno_hhr, Aleks5d, Rifai, pllk, ulna, Ivan19981305, and PrianishnikovaRina for testing the round, and MikeMirzayanov for the great codeforces and polygon platforms.

In this round, you'll be given 6 problems and 2 hours to solve them.

UPD: I decided to drop the 3 seconds rule. The scoring distribution is 500-1000-1500-1750-2500-2500. That means you should probably read both E and F :D

Good luck & Have fun!

UPD: here's the editorial.

UPD: congratulations to the winners!

Div.1+Div.2:-

Div.2:-

See you in the second round :D

• +466

 » 8 months ago, # | ← Rev. 2 →   +24 Trying to make enough money to afford MIT. I see you. Only a few ten thousand dollars left np
•  » » 8 months ago, # ^ |   +2 Dude, application fees :3 But first things first, how dare you say her name!
•  » » » 8 months ago, # ^ | ← Rev. 2 →   -40 I have stalked her long enough to at least be allowed to do so. Fight me.
•  » » » » 8 months ago, # ^ |   +6 I don't get it. Some internal joke?
•  » » » » » 8 months ago, # ^ |   +10 Alphatrance I think they're referring to this meme xD
•  » » » » » » 8 months ago, # ^ | ← Rev. 6 →   -19 deleted comment
•  » » » » » » 8 months ago, # ^ |   -16 lol
•  » » » 8 months ago, # ^ |   -32 chup mc
 » 8 months ago, # |   +90 By tradition, the scoring distribution will be announced 3 seconds before the contest.So accurate!
•  » » 8 months ago, # ^ |   +3 But now rules should get changed
 » 8 months ago, # |   -13 Imagine next rounds you would actually use high precision clocks to measure the interval of announcing score distributions... ;)
•  » » 8 months ago, # ^ |   -8 Maybe even high-precision randoms!
 » 8 months ago, # |   -7 The time is good for Chinese.
•  » » 8 months ago, # ^ |   +2 Oh,No.The best time is before 8 p.m, so that they can go to bed earlier.
•  » » 8 months ago, # ^ |   -26 code with girlfriend wonderfully
 » 8 months ago, # |   +2 i m very excited about the new contest
•  » » 8 months ago, # ^ |   -8 Yeah1.
 » 8 months ago, # | ← Rev. 2 →   -23 4 contests in the next 7 days, great.
•  » » 8 months ago, # ^ |   -25 4(2)
 » 8 months ago, # |   0 Looking forward to more fun XOR questions
 » 8 months ago, # |   -23 Upvoted for creating 3 contests simultaneously (Great job!).Downvoted for not capitalize "Codeforces" and "Polygon".
•  » » 8 months ago, # ^ |   +44 How did you vote twice??
 » 8 months ago, # |   +10 It seems that another competition season has comeSo many contests these days :)
 » 8 months ago, # |   +11 mohammedehab2002 previous rounds all problem names start with "Mahmoud"(round #396), "Ehab"(round #525) and "Mahmoud and Ehab"(round #473). Guess which start is next ??
•  » » 8 months ago, # ^ |   +13 To get all the combination, Ehab and Mahmoud is the last one to start with :)
•  » » 8 months ago, # ^ |   +21 the next start is an empty string
•  » » » 8 months ago, # ^ |   -8 HaHaHa
•  » » » 8 months ago, # ^ |   +16 John cena problems
•  » » 8 months ago, # ^ |   -14 or maybe concatenated version MahmoudEhab:)
 » 8 months ago, # |   -22 up to which rating second division?
•  » » 8 months ago, # ^ | ← Rev. 3 →   +8 Upto 2099, but if div1 and div2 rounds are held simultaneously people who are rated greater than equal to 1900 must participate in div1
 » 8 months ago, # |   -8 Wait, sorry guys I am new here. Do you have to start at that exact time? Or is there a contest window where we can choose to do it?
•  » » 8 months ago, # ^ |   +6 You need to register before the contest starts. Registration's usually open till 5 minutes prior to the start of a contest. Some contests support extra reg which opens 10 minutes after the contest start and continues for 20 minutes.
•  » » » 8 months ago, # ^ |   -8 I did register, but do you have to start at that exact time? Thanks,
•  » » » » 8 months ago, # ^ |   -20 You can start the contest any time, only registration's the key. Though the quicker you solve a problem the more points you receive for it.
•  » » 8 months ago, # ^ |   +41 There's no window, the contest starts at the same time for everyone.
 » 8 months ago, # |   -8 Let's get ready to rumblllllllleeeeeeeeeeeeeeeeeeee!!!!!!!!!!!!!!
•  » » 8 months ago, # ^ |   -8 cute !!
 » 8 months ago, # |   -8 Hope this round not unrated and no accident
 » 8 months ago, # |   -6 Do we have a hacking phase?
•  » » 8 months ago, # ^ |   0 No
•  » » » 8 months ago, # ^ |   +14 No u
 » 8 months ago, # |   +15 Scoring distribution shall be announced 3 seconds before contestI decided to drop the 3 seconds rule. The scoring distribution is 500-1000-1500-1750-2500-2500.Rules are made to be broken here. xD
 » 8 months ago, # |   +8 You really like GCD and prime numbers ! (WOW!)
•  » » 8 months ago, # ^ |   0 The description of the topic is short and concise。
 » 8 months ago, # | ← Rev. 2 →   -12 Apparently, it wasn't.
•  » » 8 months ago, # ^ |   +18 if only query d at beginning and query s on LCA then will get FST  /\ /\ \ /\ \ \ /\ \ \ \ but I have no idea to solve it correctly now : /
 » 8 months ago, # |   +1 How To solve problem D ?
•  » » 8 months ago, # ^ |   0 Think in terms of prefix xors.
•  » » 8 months ago, # ^ |   +4 Instead of directly construct the array, just construct the prefix xor version of the array S1, S2,..., Sn. So the condition that no subseg has the xor equals to 0 or x is the same as the array S is distinct and there is no pair in S that xor of them is x. So iterate from 1 -> 2^n-1, if x^i also belongs to the given range [1, 2^n) then just pick one, or else pick both.To construct the answer array A from S, use : Ai = Si^S(i-1).
•  » » » 8 months ago, # ^ |   0 What is prefix xor ? And why prefix xor array changes the condition?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +16 First observation, if there is no number x restricted. You can simply construct something like 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1... This pattern is optimal because at every i-th number where i is 2^x, you cannot add any new number using numbers in range [1..2^x), any new addition will cause XOR to be 0. Hence, you will need to add 2^x every time you are at the 2^x-th number (1, 2, 4, 8, 16, ...).Now, what about the restricted number? Well you can simply take the biggest 2^x that forms x. e.g. if x is 5, restricted number will be 4. Now, you can simply skip the restricted number when you want to form the sequence. (Why biggest? To minimize the largest number in the sequence) e.g. x = 5 1 2 1 8 1 2 1 16 1 2 1 8 1 2 1, if at any time the number has exceed 2^n, just stop adding new sequences.
•  » » » 8 months ago, # ^ |   +1 Nice approach. Here is my code implementing this: https://codeforces.com/contest/1174/submission/55059114 .
•  » » 8 months ago, # ^ |   0 What can be pretest 7?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 I thought of something like 4 5. Answer should be longer than 1 2 1 8, ... But I initially only answered 1 2 1 which is a wrong answer
•  » » 8 months ago, # ^ | ← Rev. 3 →   +20 I will explain the complete solution of D. Hint 1Suppose you calculate accumulate xor sequence. If $a =${$1,3,1$}, accumulate xor is {$0, 0 \ xor \ 1, 0 \ xor \ 1 \ xor \ 3, 0 \ xor \ 1 \ xor \ 3 \ xor \ 1$} $=$ {$0,1,2,3$}.Suppose the problem is not "There is no subsegment which xor is $0$ or $x$", but "There is no subsegment which xor is $0$". In this problem, the only condition that the sequence should satisfy is that "All values of accumulate xor is different". For example, sequence {$1,3,1$} satisfy the condition because accumulate xor is {$0,1,2,3$} and it's all different, but sequence {$2,1,1$} does not satisfy the condition.So, it means if $x$ is greater than or equal to $2^{N}$, you should output the sequence which is length $N−1$: {$0 \ xor \ 1, 1 \ xor \ 2, 2 \ xor \ 3, ..., (N−2) \ xor \ (N−1)$}. Hint 2So what about the pattern of $x < 2^{N}$? Let's think about some cases. If $N=3$ and $x=4$, one of the optimal accumulate xor sequence is {$0,1,2,3$}. If $N=3$ and $x=2$, one of the optimal accumulate xor sequence is {$0,1,4,5$}. If $N=3$ and $x=1$, one of the optimal accumulate xor sequence is {$0,2,4,6$}. Seems like the maximal length of accumulate xor sequence seems to be $2^{N}−1$. That is true but why? In this case, two condition must be satisfy to not include a subsegment of $0$ and $x$: 1. All of the values in accumulate xor sequence is different. 2. Both $0$ and $0 \ xor x$ should not be in accumulate xor sequence. Same for $1$ and $1 \ xor x$, ... $2^{N}−1$ and $2^{N}−1 \ xor \ x$.So, you should choose the value $i$ which is $0 \leq i < 2^{N}$ and $i < (i \ xor \ x)$. For example, if $N=3$ and $x=7$, you should choose the value {$0,1,2,3$}.Finally, you should restore the sequence from accumulate xor sequence. In the example of $N=3, x=7$, one of the possible answer = {$0 \ xor \ 1, 1 \ xor \ 2, 2 \ xor \ 3$} = {$1,3,1$}. Source CodeMy Solution of problem D
 » 8 months ago, # |   0 I found B to be harder than C and D maybe because I was approaching it wrong way.
 » 8 months ago, # |   0 How to solve B? And why does it get TLE 55041556 ?
•  » » 8 months ago, # ^ |   +3 To be honest, B is so simple. If we have both odd and even numbers, then the sorted array is the answer, or else just print the original array. Correct me if I'm wrong
•  » » » 8 months ago, # ^ |   0 Maybe i dont understand you but what about this test: 3 2 3 2 1 (n = 5)
•  » » » » 8 months ago, # ^ |   0 Oh. Why 1 will be at the first place? We can swap only odd and even numbers, isnt?
•  » » » » 8 months ago, # ^ |   0 It is 1 2 2 3 3. Because both odd and even exist, we can easily prove that using the allowed operation could sort the array, and obviously the lexicographically smallest array.
•  » » » » 8 months ago, # ^ |   +11 "You can perform the following operation on it as many times as you want:". Of course i again solve another problem (( .
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 You could swap the array as: 3 2 3 2 1 -> 2 3 3 2 1 -> 1 3 3 2 2 -> 1 2 3 3 2 -> 1 2 2 3 3 -> swap can be performed as many times needed
•  » » 8 months ago, # ^ |   0 if the input contains both odd and even numbers the result will always be a sorted array.
•  » » 8 months ago, # ^ |   0 You need to notice that, if there are only odd or only even numbers you can not make any swap. Otherwise you can sort the whole array.
•  » » 8 months ago, # ^ |   +3 If we have at least one odd and another even number, we will be able to reorder the whole array (swap two odd numbers or two even numbers). For example, if you wanna swap two odd numbers o1 and o2, with an even number e, you can do:swap o1 and e, swap e and o2, swap e and o1.And the position of o1 and o2 was swapped as a result.
 » 8 months ago, # |   +6 Hints for F please.
•  » » 8 months ago, # ^ |   +18 Firstly, ask the distance from 1. Now find the centroid of the current tree and check if it is an ancestor by checking if dist(root,centroid)+dist(x,centroid) == dist(root,x) , if that holds true, query the next node on the path and make it the root and now distance from root is dist(x,centroid)-1. otherwise, you can delete the subtree rooted at the centroid and everything else remains the same.
•  » » » 8 months ago, # ^ |   0 how to find centroid ?
•  » » » 8 months ago, # ^ |   0 But I got WA on test 12... have you got AC like that?
•  » » » » 8 months ago, # ^ |   0 Try to optimize queries if you don't have any bugs.
•  » » » » » 8 months ago, # ^ |   0 I don't even know.. WA because of Wrong Node or WA because of too many queries
•  » » » » » » 8 months ago, # ^ |   0 You can count queries, and exit with some code if limit exceeded. You will see this code.
•  » » » » » » » 8 months ago, # ^ |   0 Man, if I knew that, I would have solved it!Thank you for the tip XD
•  » » » » » » » 8 months ago, # ^ |   0 WOW,very clever
•  » » » » 8 months ago, # ^ |   0
 » 8 months ago, # |   +2 I've seen successful hacks made. Any hints what they were about?
•  » » 8 months ago, # ^ |   +3 In my room there were submissions that checked if there is any odd numbers and sorted based on that (I found one more submission like that after the end of contest :@ ) .
•  » » 8 months ago, # ^ | ← Rev. 2 →   +3 One of the mistakes on problem A was dividing sum of the numbers by 2 for checking the answer, while the sum is odd.Sorry for bad English. :)
•  » » » 8 months ago, # ^ |   0 Your English is fine :D I understood
•  » » » » 8 months ago, # ^ |   0 Thanks :) I tried too much to write understandable.
 » 8 months ago, # |   +5 How to solve F?
 » 8 months ago, # |   +5 god damn it when I started to feel I'm halavin I failed on the fourth hack
•  » » 8 months ago, # ^ |   0 wow 3 hacks, how did you get them? was there a corner test case or something?
•  » » » 8 months ago, # ^ |   0 Who did not solve A by sorting the array for some reason they were swapping the first different element from the first half with the other half and then print the array
•  » » » » 8 months ago, # ^ |   0 nice
•  » » » » 8 months ago, # ^ |   0 Isn't there an ambiguity in Problem A? In the end, it says "They must form a reordering of a. You are allowed to not change the order". What does that mean? As per my understanding, it meant that we're allowed rotate the array(so that ordering remains same) but, can't sort it completely.
•  » » » » » 8 months ago, # ^ |   0 you are allowed to not change the order means you can leave it as it is and they must form a reordering of a means you can swap any element as many times as you want
•  » » » » » » 8 months ago, # ^ |   0 Oops, that reordering thing got me. Thanks.
 » 8 months ago, # |   0 seem too difficult for me..... the code has some question...
 » 8 months ago, # |   -12 this is the worst!
 » 8 months ago, # |   0 Hints for F? Can it be solved using LCA?
•  » » 8 months ago, # ^ |   0 it can be solved using Centroid
•  » » » 8 months ago, # ^ |   0 what is centroid decomposition, any good blogs and tutorials on it, from where u learn.
•  » » » » 8 months ago, # ^ |   0
•  » » » » » 8 months ago, # ^ |   0 Thanks! codeforces really expose u to a lot of things u can learn through ur journey of competitive programming.
 » 8 months ago, # |   +30
•  » » 8 months ago, # ^ | ← Rev. 2 →   +14 After solving (A,B,C)^zzzzzzzzzzzz 01:59:29 Successful hacking attempt
 » 8 months ago, # |   0 How to think and approach problem D?
•  » » 8 months ago, # ^ |   0 Every number has only one number that makes (A^B == X) true. The problem asks for sub segment so it's another way to tell you to think of prefix xor. The answer should be clear after that.
 » 8 months ago, # |   0 fml, my bug on F was that I'm doing return the answer if there is only one edge from the current node, which should be the back edge to the parent, but I forgot the root! Nice round, I really liked it :D
 » 8 months ago, # |   0 Any ideas for E? i see most solution use dp. can anyone explain!
•  » » 8 months ago, # ^ |   -8 For E, $a_1=p_1^{e_1}p_2^{e_2}$. then max is $1+e_1+e_2$. that's exp step down. so $a_1$ must be $2^k$ or $2^{k-1}3$ (if $\leq n$). then remain is combination count. but no time to code.. the annoying $3$.Am I right? or is there a better solution? wait for tomorrow morning:) sleep now
•  » » » 8 months ago, # ^ |   0 editorial has come
•  » » 8 months ago, # ^ | ← Rev. 3 →   +64 Actually, I didn't use DP. I used only multiplying. Seriously, I didn't use DP. My solution of problem E is as follows: --- Step 1: What is the maximal possible value of $f(p)$? Actually, the maximal possible value of $f(p)$ is as follows: $1 \leq N \leq 1$ : $max=1$ $2 \leq N \leq 3$ : $max=2$ $4 \leq N \leq 7$ : $max=3$ $8 \leq N \leq 15$ : $max=4$ $16 \leq N \leq 31$ : $max=5$ But why? Think about the sequence of {$g_1,g_2,g_3,...,g_k$} if you assume $g_1>g_2>g_3>...>g_n$. For example, if $A=$ {$4,6,2,1,5,3$}, the prefix gcd will be {$4,2,2,1,1,1$}, so $g$ will be {$4,2,1$}. Because the optimal sequence of $g$ is {$2^{k−1},2^{k−2},2^{k−3},...,4,2,1$}. Suppose $N=11$. For the sequence {$8,4,2,1,11,10,9,7,6,5,3$}, it is easy to find that $g$ is {$8,4,2,1$}. --- Step 2: How many ways are the maximal answer? Let's think about writing the value of $a_i$ which changed the prefix gcd. For example, if $g$ is {$8,4,6,5,2,3,1,7$}, the values that you will write will be {$8, 4, 6, 5$}. So what is the possible sequence of values which you will write? Suppose $N=8$. 1st value: $8$. Only $1$ way. 2nd value: $4$. Only $1$ way. 3rd value: $2, 6$. $2$ ways are possible. 4th value: $1, 3, 5, 7$. $4$ ways are possible. So the number of possible sequence of values which you will write will be $1 \times 1 \times 2 \times 4 = 8$. But, how about the other values? If sequence is {$8,4,6,5$}, you should insert other values: {$1,3,7,2$}. You should think about inserting in order of $1, 3, 7, 2$. (Insert from values which is not divisible of $2$, next not divisible for $4$, next not divisible for $8, 16, ...$ There are $1$ ways to insert $1$: Just after $5$. There are $2$ ways to insert $3$: Just after $5$, or just after $1$. There are $3$ ways to insert $7$: Just after $5$, just after $1$, or just after $3$. There are $5$ ways to insert $2$: Just after $6, 5, 1, 3$, or $7$. So for each sequence you wrote, there are $1 \times 2 \times 3 \times 5 = 30$ ways of insertion. It means there are $8 \times 30 = 240$ permutations of $N=8$ which is maximal. So, let's move on another example. Suppose $N=11$: Ways to write: $1 \times 1 \times 3 \times 6 = 18$ ways Ways to insert the other values: $1 \times 2 \times 3 \times 4 \times 5 \times 7 \times 8 = 6720$ ways So, the answer will be $18 \times 6720 = 120960$. Did you get it? :) --- Step 3: Thinking about other cases, not only $g =$ {$2^{k−1},2^{k−2},...,4,2,1$} If $N=12$, not only {$8,4,2,1$} is maximal, but also {$12,4,2,1$}, {$12,6,2,1$}, {$12,6,3,1$} is maximal. So you should brute force sequence $g$ (There are up to $O(\log N)$ ways). If you determined the sequence $g$, you can do like step 2: first calculate the number of sequence that you will write, second calculate the number of ways of insertions and finally mutiplies. Since the complexity for each $g$ is $O(N)$, so the total complexity is $O(N \log N)$. If you precount factorial and inversions, you can also solve with $O(N+\log^2 N)$. Sorry for my poor English. Code (Uploaded at 2:01 JST, 56 minutes after the contest)
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 Thanks for your great explanation ! I just have a small question: In step 2, when you were inserting values 1,3 and 7, why isn't it possible for all of the values to be inserted before 5?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 No need for further explanation. I get it now by some other way (not sure if it is different from your explanation) 1st number has only 1 option, which is 8 2nd number has only 1 option, which is 4 3rd number has 2 options, 6 & 2 (suppose we take 6) 4th number has 5 options, 1,2,3,5 & 7 (suppose we take 7) 5th number has 4 options, 1,2,3 & 5 (suppose we take 5) ... we continue like this the result = 1 * 1 * 2 * 5! = 240
•  » » » 8 months ago, # ^ |   0 Thanks
 » 8 months ago, # |   0 seems that problem B shares the same trick with problem C in Global Round 3..
•  » » 8 months ago, # ^ |   +1 what i felt and is true for most cases : if u don't know proof just input garbage and get gold.
•  » » 8 months ago, # ^ |   0 Yeah exactly same over here too!
 » 8 months ago, # |   0 I like problem E.
•  » » 8 months ago, # ^ |   0 can u explain ur approach ?
 » 8 months ago, # |   -19 Thanks for mathforces (no)
 » 8 months ago, # |   0 Tears of unskilled.
 » 8 months ago, # | ← Rev. 4 →   +19 X is 29.Apparently this tc was not there in PreTest of F.Naive Solns asking only type 2 queries will take atleast 8 queries. Extending this tc — for $n*(n+1)/2$ vertices will take $n$ queries.
 » 8 months ago, # |   0 In the problem A, it was mentioned in the problem that order of the array should not be changed! What did that line mean and how do we reorder it without changing the order? Please Help!
•  » » 8 months ago, # ^ |   +3 "You are allowed to not change the order", not "You must to not change the order"
•  » » 8 months ago, # ^ |   +6 Please read it carefully : You are allowed to not change the order. I guess u miss read it as: You are not allowed to change the order.
•  » » » 8 months ago, # ^ |   0 Oops! Thank you so much! Will surely take care from next time!
 » 8 months ago, # |   +1 $A, B$ and $C$ felt like typing test. The situation drastically changed afterward :(
 » 8 months ago, # |   -8 Very very nice contest, 10/10. Tl63 just because of using included sort. I hate this test -_-. But in general all it was good.
 » 8 months ago, # |   +3 Can someone explain how to solve this example in F?
•  » » 8 months ago, # ^ |   +3 You can use a method named "Heavy-Light Decomposition".
 » 8 months ago, # |   +11 wow I got TLE on test 63 and my rating is gone
•  » » 8 months ago, # ^ |   +15 The test 63 is the hack I used during the round, so I want to clarify a couple of points:First that seems the only test with anti Quick sort test, I can see that 150+ solutions failed this test and if it wasn't added all these solution may have been passed, I've also always see Quick sort solution pass sys test in previous rounds, so I think such test should be always added to any problem that require sorting.Also I'm not very proud with that kind of hack, because all I did is check if a java solution that uses sort for primitive array, so I want to raise attention against this.For those who still want to use primitives you can build your own sort function like the radixSort function that I use in my solutions, wich I copied from uwi code ( I hope he doesn't mind )
 » 8 months ago, # |   0 JAVA submissions have been judged on the C++ time limit for the B question. Getting a TLE for an O(nlogn) approach. However I didn't use a StringBuilder which is bad on my part but still a correct solution should pass.
•  » » 8 months ago, # ^ |   0 Yeah i notice that. Everyone using java got TLE. I did it using StringBuffer still got TLE.
•  » » 8 months ago, # ^ |   0 Problem is not time limit. Problem is the inbuilt sort in Java have worst case complexity of n^2. Hence the time limit. There is blog somewhere on the codeforces discussing this SORTING IN JAVA.
 » 8 months ago, # |   0 Hope that the rankings would be revised. Otherwise rating would take a great hit.
 » 8 months ago, # | ← Rev. 2 →   0 55036867 why using StringBuildfer was wrong and a get TLE? javaUPD: 55052153 problem was oin primitive types, only in that, i am so disappointed=(
•  » » 8 months ago, # ^ |   0 Everyone using java got TLE.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 no i see guy who didnt use stringbuilder, just sout and hes solution was accepted
•  » » 8 months ago, # ^ |   +2 Arrays.sort() for primitive data types in java uses quick sort O(n^2) while Collections.sort() uses merge sort . Quick sort can have O(n^2) complexity in worst case
•  » » » 8 months ago, # ^ | ← Rev. 4 →   0 55023792 only cuz he used wrapper he passed? nice one
•  » » » » 8 months ago, # ^ |   0 So we were supposed to know that it was going to give a TLE?
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 now we know; somedyas it will helps, but not tooday; so shitty feeling
•  » » » » » » 8 months ago, # ^ |   0 63 was the last test case. Looks like some put it there intentionally knowing all java solutions would fail. lolxD
•  » » » » » » 8 months ago, # ^ |   0 The ratings have changed. its -8 for me,no a big fall so i have no issue.
•  » » » » » » » 8 months ago, # ^ |   0 its not about rating, its about solution, we did it right, but java fucked us
•  » » » » » » » » 8 months ago, # ^ |   0 yes that is correct. I could have saved some time and did problem 3 a lot sooner. But i decided to do B first which did take some time which is now all waste.
•  » » » 8 months ago, # ^ |   0 Java uses Mergesort for user defined objects and quicksort for the rest.Using List or Array won't make a difference i guess.
•  » » » 8 months ago, # ^ |   0 So what we are not supposed to use Arrays.sort() in future contests?
•  » » » » 8 months ago, # ^ |   +1 in this particular case, we can use Integer insted of int, looks like its using another, type of sort, need to check source of class Arrays
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 what i found
•  » » » 8 months ago, # ^ |   0 Also judgement was based on 1s time limit. For java it should be 2s i guess.
•  » » » » 8 months ago, # ^ |   0 Does the TLE differ for different languages?
•  » » » » » 8 months ago, # ^ |   0 No I was mistaken. Checked previous contests and found that time limit is same for all languages. However many other platforms have extended limits for Java and Python.
•  » » 8 months ago, # ^ |   0 I also used BufferedReader, Arrays.sort(), and StringBuilder but still got a TLE :(
 » 8 months ago, # |   +3 Lmao, I was so pissed when my naive solution for F had bugs and didn't get accepted, while so many people solved it.Now I see anyway my naive solution would have got verdict Wrong answer on test 99xD.
•  » » 8 months ago, # ^ |   0
•  » » » 8 months ago, # ^ |   +10 Wow, such a great hack. Congrats!
 » 8 months ago, # |   +6 Wrong answer on test 99. Such pain in F
 » 8 months ago, # | ← Rev. 2 →   +50 Problem F
•  » » 8 months ago, # ^ |   0 But I still don't get why?
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 Clever naive soln take $O(\sqrt N)$ queries in worst test case.Worst Test Case
•  » » 8 months ago, # ^ | ← Rev. 2 →   +12
 » 8 months ago, # |   +3 I passed F in last 5 minutes. Exciting!Thanks for the round very much!
 » 8 months ago, # |   0 Sorry, does the #23 testcase from F shows "wrong answer query limit exceeded"? I made a submission with assertion but couldn't see that I was exceeding the limit. 55048680
•  » » 8 months ago, # ^ |   0 May be it's because you have a query in your main but you didn't count that ?
 » 8 months ago, # |   +3 https://codeforces.com/problemset/problem/1054/D a question similar to today's D
 » 8 months ago, # |   +4 Nice Contest.Btw a simiar (a̶n̶d̶ ̶a̶n̶ ̶e̶a̶s̶y̶ ̶v̶e̶r̶s̶i̶o̶n̶?̶) of F recently appeared in Codechef Cook Off MYS00T
 » 8 months ago, # |   +8 Problem F, a very nice tree and interactive problem! Thanks for writers.
 » 8 months ago, # |   0 Well I'm stupid and haven't debugged my F during contest, but here is my solution that should works but it got AC:First of all let's know a height of x by first type of query with vertex 1, let it be H.Let root be the lowest vertex that we know that has X in it's subtree. So let choose a type of query randomly!If we chose first type then just choose some vertex with height H in root subtree randomly and then change root!If we chose second type then just change a root!
 » 8 months ago, # |   +15 Was a randomized solution intended to pass for F?Instead of using any heavy-light/centroid decomposition, I just picked a leaf at random for the current subtree, and then asked similar queries as given in the editorial.https://codeforces.com/contest/1174/submission/55047296
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 I dont think randomized was intended. But sometimes its difficult to break randomised. Until and unless probability of failing it is high.I did saw some randomised solns and one of my friend also used randomised in F.
 » 8 months ago, # |   +9 Since editorial is not linked — EDITORIAL
 » 8 months ago, # |   -16 ^ Click here to go up! ^
•  » » 8 months ago, # ^ |   +9 what about the left of your monitor xD
•  » » » 8 months ago, # ^ |   0 The button is not there always! -_-
 » 8 months ago, # |   -15 how. to. calculate. the. contribution. ?why. the. contribution. for. me. is. negative. ? i. do. nothing. God
•  » » 8 months ago, # ^ |   0 Simply, as far as I know, the contribution points are the sum of the total votes you get in your blog posts and comments/replies divided by 5. Or maybe, it uses some logarithmic calculations.If your total votes are 100, your contribution will be (100/5) = 20. And if it's -100, your contribution will be (-100/5) = -20.Check those out:
•  » » » 8 months ago, # ^ |   0 ok. thanks.
 » 8 months ago, # |   +5 Very neat and clear problem descriptions. Thanks to the writer.
 » 8 months ago, # |   0 Isn't there an ambiguity in Problem A? In the end, it says "They must form a reordering of a. You are allowed to not change the order". As per my understanding, it meant that we're allowed rotate the array(so that ordering remains same) but, can't sort it completely.
 » 8 months ago, # | ← Rev. 2 →   +4 I think there is a time limit problem in problem 2 for java. Same logic gets accepted for C++ but TLE for java..
 » 8 months ago, # |   -8 How to solve the problem D ??
 » 8 months ago, # |   0 hello .. can any one fix this issue with the problem A in round 563 div 2 i had a working code which not getting passed the test #9 here is my code http://codeforces.com/contest/1174/submission/55111106 could any one help me with this...
 » 8 months ago, # |   0 You can change the tags of new problemsYou can put the segment tree or... next to the data structure tag


text:
# Chapter 1 - 1.6 - Other Types of Equations - 1.6 Exercises - Page 128: 9

-3i, 3i, 3, -3

#### Work Step by Step

Equation : $x^{4}-81=0$ $x^{4}-81=x^{4}-3^4=(x^2-3^2)(x^2+3^2)=(x^2-3^2)(x^2-(3i)^2)=0$ (as $i^2=-1$) Hence, $x^{4}-81=(x-3)(x+3)(x-3i(x+3i)=0$ Giving us 4 roots as 3, -3, 3i, -3i.

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
<img src="https://d5nxst8fruw4z.cloudfront.net/atrk.gif?account=iA1Pi1a8Dy00ym" style="display:none" height="1" width="1" alt="" />
You are reading an older version of this FlexBook® textbook: CK-12 Texas Instruments Algebra I Student Edition Go to the latest version.

# 12.1: Radical Transformations

Difficulty Level: At Grade Created by: CK-12

This activity is intended to supplement Algebra I, Chapter 11, Lesson 1.

## Problem 1 – The General Radical Function

Graph the equation $y = \sqrt{x}$. Once graphed, use the TRACE key to observe the coordinate values for points on the graph.

1. What is the domain and range of the function?
2. Why does the graph “stop” at the origin?
3. When is the following statement true?

The graph of the square root function is completely in the first quadrant.

$\text{Sometimes} && \text{Always} && \text{Never}$

## Problem 2 – Transformations

Start the Transformation Graphing application by pressing APPS and selecting Transfrm.

Now, press $Y=$ and enter $A \surd (X-B)+C$ into $Y_1$.

Press ZOOM and select 6:ZStandard. Notice the displayed equation. The values of $A, B$ and $C$ may be changed by using the arrow and number keys.

4. What does the graph look like when all three variables equal zero? Why?

5. Based on your exploration, when is the following statement true?

The graph of the square root function is completely in the first quadrant.

$\text{Sometimes} && \text{Always} && \text{Never}$

Continue to manipulate the values of $A, B$ and $C$ on the calculator to help answer Questions 6-16

6. Find two functions whose domain is $x \ge 3$.

7. What is the domain of the function $f(x) =4 \sqrt{x+2} - 3$ ? Check using the graph.

8. Changing which variable will create a horizontal shift?

9. Find two functions whose range is $y \ge -2$.

10. What is range of the function $f(x) =4 \sqrt{x+2}-3$ ? Check using the graph.

11. Changing which variable will create a vertical shift?

12. What is the difference between the graphs of $f(x) =4 \sqrt{x+2}-3$ and $g(x) = -4 \sqrt{x+2}-3$ ?

13. What is the difference between the graphs of $f(x) =4 \sqrt{x+2}-3$ and $g(x) = 2 \sqrt{x+2}-3$ ?

14. What effect does the variable $a$ have on the graph?

15. What is the domain of the function using the general equation $y = \sqrt{x-h}+k$ ?

16. What is the range of the function using the general equation $y = \sqrt{x-h}+k$ ?

## Extension – Cube Root Functions

Press $Y=$ and enter $A \sqrt[3]{ \ }(x-B)+C$ into $Y_1$.

Change the values of the variables $A, B$, and $C$, and observe the effects of the changes on the graph.

17. What is the domain and range of the function in terms of the general equation?

18. Describe the effects of changing each variable on the graph.

Feb 22, 2012

## Last Modified:

Oct 31, 2014
Files can only be attached to the latest version of section

# Reviews

Please wait...
Please wait...
Image Detail
Sizes: Medium | Original

TI.MAT.ENG.SE.1.Algebra-I.12.1


text:
BooksirmaCollected Volumepp. 81–91

# Monotonicity in spherical and hyperbolic triangles

• ### Himalaya Senapati

Chennai Mathematical Institute, Siruseri, India
We start by recalling Proposition 27 of Menelaus’ Spherics, a treatise on spherical geometry by Menelaus of Alexandria (1st–2nd century CE). This is a comparison theorem between the base of a spherical triangle and the great circle arc joining the midpoints of the two legs. The theorem expresses a property which later became known as Busemann's criterion for positive curvature in metric spaces. Propositions 28 and 29 that follow in the same treatise are comparison theorems of a similar sort, but comparing angles instead of edges when a spherical triangle is divided by a great circle arc joining midpoints of two sides. In this comparison of angles, Menelaus assumed one of the angles of the triangle to be at least equal to a right angle. In this chapter, we prove a monotonicity result in the lineage of Propositions 28 and 29. More precisely, we prove that in a spherical triangle $ABC$ with $CB>CA$, if the sides $CA$ and $CB$ are increased while holding the angle $C$ and the ratio $CA/CB$ constant, the angle $\widehat{CAB}$ increases monotonically. As a corollary, we prove parts of Propositions 28 and 29 of the \emph{Spherics} without any restriction on angles: the angle subtended at the base of a spherical triangle is greater than its homologue subtended at the geodesic joining the midpoints of the legs if the adjacent leg is shorter than the farther one. We then extend this result to hyperbolic geometry where we prove that the angle $\widehat{CAB}$ decreases monotonically.


text:
# Root Approximation 1

Calculus Level 2

Consider this equation

$2^x=x^2$

There are 2 trivial solutions, namely $$x=2$$ and $$x=4$$

However, the equation is known to also have a negative solution. Find the negative solution.